Geometry — বিন্দু, বাঁক ও boundary¶

Cartesian coordinate-এ orientation¶

A(0,0) থেকে B(4,0)-এর দিকে নীল তীর; C(2,3) ওপরের বাঁ পাশে। ত্রিভুজের ভূমি 4, উচ্চতা 3।

cross(A,B,C)=4×3−0×2=12>0। A থেকে B-এর দিকে এগোলে C বাঁ পাশে। Triangle-এর area abs(cross)/2=6। এখানে y ওপরের দিকে বাড়ে।

Rectangle overlap: দুই অক্ষের ছেদ¶

A-এর x range [0,3], y range [0,3]; B-এর x range [2,5], y range [1,4]।

নীল rectangle A ও সবুজ rectangle B-এর হলুদ ছেদ: x-এ 2 থেকে 3, y-এ 1 থেকে 3।

অক্ষ	common interval	দৈর্ঘ্য
x	[max(0,2), min(3,5)] = [2,3]	1
y	[max(0,1), min(3,4)] = [1,3]	2

দুই দৈর্ঘ্যই positive, তাই overlap area 2। একটি দৈর্ঘ্য 0 হলে শুধু boundary ছোঁয়; positive-area overlap নয়।

Lower convex hull: ভুল দিকে বাঁক হলে মাঝের point বাদ¶

Sorted points: P1=(0,0), P2=(2,2), P3=(4,1), P4=(6,3)।

flowchart TD
    A["h = P1, P2"] --> B["P3 এলে cross(P1,P2,P3) = -6"]
    B --> C["ডানে বাঁক: P2 pop"]
    C --> D["h = P1, P3"]
    D --> E["P4 এলে cross(P1,P3,P4) = 6"]
    E --> F["বাঁয়ে বাঁক: P4 রাখি; h = P1, P3, P4"]

বাঁ থেকে ডানে lower hull তৈরির এই convention-এ counterclockwise turn রাখি; cross <= 0 হলে pop করলে মাঝের collinear point-ও বাদ যায়। সব boundary point রাখতে চাইলে collinear নীতি আলাদা করতে হবে।

Grid movement-এর parity¶

(0,0) থেকে (2,1)-এর Manhattan distance 2+1=3। চারদিকে এক ঘর করে চললে প্রতি move-এ checkerboard-এর রং বদলায়। তাই 3 চালে পৌঁছানো যায়; 4 চালে যায় না। বাধাহীন অসীম grid-এ 5 চালে যেতে বাড়তি যাওয়া-ফেরার জোড়া যোগ করা যায়।

Vector ও square-root ছাড়া দূরত্ব তুলনা¶

A=(1,1), B=(4,5) হলে vector AB=(3,4); squared distance 25। A থেকে C=(2,7)-এর vector (1,6), squared distance 37। তাই B কাছাকাছি; 25 ও 37-এর square root বের করতে হয়নি।

Shoelace: একটি rectangle¶

Boundary order (0,0) → (2,0) → (2,1) → (0,1) → (0,0)।

ধাপ	xᵢyᵢ₊₁	yᵢxᵢ₊₁
1	0	0
2	2	0
3	2	0
4	0	0
মোট	4	0

Area abs(4−0)/2=2। Point-গুলো polygon boundary-র ক্রমে নিতে হবে; ইচ্ছেমতো সাজালে একই অর্থ থাকবে না।

দুটি segment একে অন্যকে কাটে¶

P(0,0)–Q(4,4) ও R(0,4)–S(4,0) রেখাংশ দুটি (2,2) বিন্দুতে কাটে।

P=(0,0), Q=(4,4), R=(0,4), S=(4,0)। cross(P,Q,R)=16, cross(P,Q,S)=−16: R ও S বিপরীত পাশে। আবার cross(R,S,P)=−16, cross(R,S,Q)=16: P ও Q-ও বিপরীত পাশে। তাই segment দুটি (2,2)-তে কাটে। Collinear হলে sign-test যথেষ্ট নয়, axis projection-এর overlap-ও পরীক্ষা করতে হবে।

Manhattan transform¶

u=x+y, v=x−y নাও। A=(1,2) → (u,v)=(3,−1), B=(4,0) → (4,4)। Manhattan distance 3+2=5; নতুন coordinates-এ max(abs(4−3),abs(4−(−1)))=5। এটি coordinate transform; অতিরিক্ত scale না নিয়ে একে দৈর্ঘ্য-অক্ষুণ্ণ rotation বলা ঠিক নয়।

ধারণায় ফিরি · সব সমস্যা ও অনুশীলন · মূল উৎস