Visualization Ideas — Geometry & Coordinate Math¶
Geometry-তে ছবি আঁকা optional না — এটাই পদ্ধতি। Graph paper কিনে ফেলো (বা খাতায় ছক আঁকো); প্রতিটা problem-এ অন্তত একটা ছবি না এঁকে code-এ হাত দিও না। নিচে প্রতিটা concept-এর আঁকার idea, আর শেষে 3টা worked ASCII example।
প্রতি concept-এর visualization idea¶
1. Vector = তীর¶
দুটো point dot দিয়ে আঁকো, এক থেকে আরেকটায় তীর টানো, তীরের গায়ে (dx, dy) লেখো। তিন-চারটা vector এঁকে দেখো — point বিয়োগ মানে "যাত্রার নির্দেশনা", শুরু কোথা থেকে সেটা vector ভুলে যায়।
2. Squared distance = বর্গক্ষেত্রের তুলনা¶
দুটো দূরত্বের উপর বর্গ এঁকে দেখাও: ছোট দূরত্বের বর্গও ছোট। sqrt না নিয়েও কে কাছে বলা যায় — কারণ বর্গের আকারের ক্রম দূরত্বের ক্রমের সাথে কখনো উল্টায় না।
3. Cross product sign = গাড়ির steering¶
তুমি A থেকে B-র দিকে গাড়ি চালাচ্ছ; C-তে যেতে steering বাঁয়ে ঘোরাতে হলে CCW (+), ডানে হলে CW (−), সোজা গেলে collinear (0)। তিনটা ছবি পাশাপাশি আঁকো — একই A, B কিন্তু C তিন জায়গায়।
4. Shoelace = ফিতা বাঁধা¶
Polygon-এর vertex গুলো দুই কলামে (x আর y) লেখো, আড়াআড়ি রেখা টেনে গুণফলগুলো দেখাও — জুতার ফিতার ছবিই ফুটে উঠবে। এক দিকের আড়াআড়ি যোগ, অন্য দিকের বিয়োগ — নামের রহস্য এখানেই।
5. Segment intersection = নদী পারাপার¶
PQ একটা নদী; R আর S দুই গ্রাম। দুই গ্রাম নদীর দুই পাড়ে হলে RS রাস্তা নদী পেরোবেই। কিন্তু সেটাই যথেষ্ট না — উল্টোটাও লাগবে (P, Q-ও RS-এর দুই পাশে)। দুটো ছবি আঁকো: একটাতে শুধু প্রথম শর্ত সত্য কিন্তু segment ছোট বলে কাটে না।
6. Rectangle overlap = জানালার পর্দা¶
দুটো rectangle-কে আলাদা রঙের কাচ ভাবো। x-অক্ষে তাদের ছায়া (projection) ফেলো — দুটো interval; y-অক্ষেও। দুই অক্ষেই ছায়া overlap করলে তবেই কাচ দুটো overlap। এক অক্ষে ফাঁক থাকলেই শেষ — এটাই negation trick-এর ছবি।
7. Convex hull = rubber band¶
15-20টা এলোমেলো dot আঁকো, চারপাশে rubber band-এর রেখা টানো। ভেতরের dot গুলোতে band ছোঁয় না — তারা hull-এ নেই। Monotone chain দেখাতে: বাঁ থেকে ডানে হাঁটার সময় কোনো মাঝের point "ভেতরে ডেবে গেলে" তাকে cross করে কেটে দাও — এটাই pop।
8. 45° rotation = হীরা থেকে বর্গ¶
Manhattan distance-এ "origin থেকে দূরত্ব ≤ k" অঞ্চলটা একটা হীরা (◇)। (x+y, x−y) transform-এর পরে সেই হীরাই বর্গ (□) হয়ে যায় — আর বর্গ মানে প্রতি axis আলাদা করে দেখা যায়। দুই ছবি পাশাপাশি আঁকো।
9. Grid parity = দাবার বোর্ড¶
Grid-টা সাদা-কালো রং করো (r+c) % 2 দিয়ে। প্রতিটা up/down/left/right চাল রং বদলায় — তাই জোড় সংখ্যক চালে নিজের রঙে ফেরো। শুরু আর শেষ ঘরের রং মিলিয়ে k-এর parity check — পুরো যুক্তি এক ছবিতে।
Worked ASCII example 1: orientation-এর তিন রূপ (A=(0,0), B=(4,0))¶
case 1: C = (2, 3) case 2: C = (2, −3)
y y
3 | C ● 0 | A●────────●B
2 | ↖ বাঁয়ে বাঁক −1 | ↘ ডানে বাঁক
1 | −2 |
0 | A●────────●B −3 | C ●
└──────────── x └──────────── x
val = (4−0)(3−0) − (0−0)(2−0) val = 4·(−3) − 0·2
= 12 > 0 → CCW (+1) = −12 < 0 → CW (−1)
case 3: C = (7, 0) → val = 4·0 − 0·7 = 0 → collinear, তিনজনই এক লাইনে
ছবির শিক্ষা: cross product-এর sign মানে "steering কোন দিকে" — সংখ্যাটার চেয়ে দিকটাই আসল।
Worked ASCII example 2: rectangle overlap-এর axis projection¶
A = (0, 0, 3, 3) B = (2, 1, 5, 4)
y
4 | ┌─────B────┐
3 | ┌───A─┼──┐ │
2 | │ │▒▒│ ← overlap অঞ্চল
1 | │ └──┼───────┘
0 | └────────┘
└──┴──┴──┴──┴──┴── x
0 1 2 3 4 5
x-অক্ষে ছায়া: A: [0────3] y-অক্ষে ছায়া: A: [0────3]
B: [2────5] B: [1────4]
overlap: [2,3] ✓ overlap: [1,3] ✓
দুই অক্ষেই ✓ → rectangle overlap করে।
B = (4, 0, 6, 2) হলে? x-ছায়া: A [0,3], B [4,6] — ফাঁক! → overlap নেই, y দেখারই দরকার নেই।
ছবির শিক্ষা: 2D প্রশ্ন = দুটো স্বাধীন 1D প্রশ্ন — geometry-তে dimension ভাঙাটা বারবার ফিরবে।
Worked ASCII example 3: monotone chain-এর pop (lower hull)¶
points (sorted by x): P1(0,0) P2(2,2) P3(4,1) P4(6,3)
step 1: h = [P1]
step 2: h = [P1, P2]
step 3: P3 আসছে। বাঁক P1→P2→P3:
P2●
╱ ╲ orientation(P1, P2, P3) = (2)(1) − (2)(4) = −6 < 0
╱ ●P3 ডানে বাঁক — lower hull-এর জন্য ঠিক আছে, P2 থাকল? না!
●P1 আমাদের convention-এ lower hull চায় CW বাঁক —
এখানে CW-ই, তাই P2 টিকে গেল... কিন্তু দেখো উল্টোটা:
যদি P3 = (4, 5) হতো: orientation(P1, P2, P3) = (2)(5) − (2)(4) = +2 > 0
●P3(4,5) বাঁয়ে বাঁক (CCW) — মানে P2 সীমানার নিচে নেই,
P2● সে hull-এর ভেতরে ডেবে গেছে → P2-কে pop!
╱ h = [P1] → তারপর P3 ঢুকবে → h = [P1, P3]
●P1
ছবির শিক্ষা: pop মানে "মাঝের point টা rubber band-এর ভেতরে পড়ে গেছে" — আর সেটা ধরা পড়ে শুধু cross product-এর sign-এ। নিজের convention (lower hull-এ কোন sign-এ pop) একবার ছবি এঁকে ঠিক করে নাও, তারপর আর গুলিয়ে যাবে না।
নিজে আঁকার চ্যালেঞ্জ¶
- Segment intersection-এর collinear overlap case-টা আঁকো — চারটা orientation-ই 0, কিন্তু segment দুটো আংশিক একে অপরের উপরে
(0,0), (2,0), (0,2)triangle-টা graph paper-এ এঁকে B-এর 6টা সীমানা-point চিহ্নিত করো — Pick's theorem হাতে মেলাও- 5×5 দাবার বোর্ডে
(0,0)থেকে(2,1)— ঠিক 4 চালে যাওয়া অসম্ভব কেন, রং দিয়ে দেখাও (Manhattan distance 3, parity মেলে না)