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

## Cartesian coordinate-এ orientation

![A(0,0) থেকে B(4,0)-এর দিকে নীল তীর; C(2,3) ওপরের বাঁ পাশে। ত্রিভুজের ভূমি 4, উচ্চতা 3।](diagrams/orientation.svg){ width="440" }

`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।](diagrams/rectangle-overlap.svg){ width="480" }

| অক্ষ | 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)`।

```mermaid
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) বিন্দুতে কাটে।](diagrams/segment-intersection.svg){ width="400" }

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 বলা ঠিক নয়।

[ধারণায় ফিরি](concept-notes.md) · [সব সমস্যা ও অনুশীলন](problems/README.md) · [মূল উৎস](source-map.md)