সরাসরি পর্বে যান
পর্ব ৬৩ · ৭২-এর মধ্যে · মডিউল ৮

Computational geometry — cross product, convex hull

Computational Geometry — Cross Product and Convex Hull

Taught in Bangla, this lesson treats geometry as algorithms on points and vectors. It uses dot and cross products for angles and turns, warns about floating-point epsilon, tests segment intersection, computes polygon area with the shoelace formula and Pick's theorem, checks point in polygon by ray casting, and builds convex hulls with Graham scan, Andrew's monotone chain and gift wrapping, plus lower bounds, farthest pairs and line sweep.

এই পর্বে যা শিখবেন

  • Dot product দিয়ে কোণ ও projection, আর cross product দিয়ে orientation test
  • দুটি রেখাংশ ছেদ করে কি না — একই রেখার বিশেষ ক্ষেত্রগুলোসহ
  • Shoelace সূত্রে বহুভুজের ক্ষেত্রফল, Pick-এর উপপাদ্য আর point in polygon
  • Graham scan, Andrew-এর monotone chain আর Jarvis march — সঠিকতার যুক্তি আর complexity
  • Ω(n log n) নিম্নসীমা, rotating calipers আর line sweep কোথায় কাজে লাগে

১ · জ্যামিতি যখন অ্যালগরিদম — বিন্দু আর ভেক্টর

স্কুলের জ্যামিতিতে আমরা কাগজে ছবি এঁকে প্রমাণ করি। কম্পিউটারের কাছে ছবি নেই — আছে শুধু সংখ্যা: প্রতিটি বিন্দু একটি (x, y) জোড়া। Computational geometry সেই প্রশ্নগুলোর দ্রুত আর নির্ভুল অ্যালগরিদম খোঁজে: এই দুটি রাস্তা কি একে অপরকে কাটে? এই জমির ক্ষেত্রফল কত? GPS-এর এই বিন্দুটি কোন উপজেলার সীমানার ভেতরে? এই ১০ লাখ বিন্দুকে ঘিরে সবচেয়ে ছোট বেড়া কোনটি?

ঢাকার রাস্তায় রিকশায় বসে আছেন। রিকশাওয়ালা মোড়ে এসে বাঁয়ে ঘুরলেন, নাকি ডানে, নাকি সোজা গেলেন — চোখ বন্ধ করেও শরীর টের পায়। এই পর্বের প্রায় প্রতিটি অ্যালগরিদম ঠিক এই একটি প্রশ্নই বারবার করে: “a থেকে b-তে যাওয়ার পথে, c-তে যেতে হলে বাঁয়ে ঘুরতে হবে, না ডানে?” উত্তরটি একটি গুণ আর একটি বিয়োগে পাওয়া যায় — কোনো কোণ, sin বা cos ছাড়াই।

একটি vector হলো দিক আর দৈর্ঘ্যসহ একটি সরণ: বিন্দু a থেকে b-তে যাওয়ার vector b − a = (b.x − a.x, b.y − a.y). বিন্দু আর vector একই রকম জোড়া দিয়ে লেখা হয়, তাই কোডে সাধারণত একটিই struct P { long long x, y; } দুই কাজ করে। দুটি vector যোগ-বিয়োগ করা যায়, সংখ্যা দিয়ে গুণ করা যায়, আর — সবচেয়ে গুরুত্বপূর্ণ — দুই রকম “গুণফল” আছে, যা পরের অংশের বিষয়।

মূল ধারণা

Computational geometry-র অ্যালগরিদম দুই স্তরে লেখা হয়। নিচে কয়েকটি ছোট primitive (orientation, দূরত্বের বর্গ, dot product) — প্রতিটি Θ(1) আর যতটা সম্ভব নির্ভুল। ওপরে চেনা DSA: sorting, stack, two pointer, balanced BST, divide and conquer. Primitive ভুল হলে ওপরের সুন্দর অ্যালগরিদমও ভুল উত্তর দেয়।

২ · Dot product আর cross product — কোণ, ছায়া আর মোড়

Dot product — কোণ আর projection

a = (a.x, a.y) আর b = (b.x, b.y) হলে dot product a · b = a.x·b.x + a.y·b.y. জ্যামিতিক অর্থ: a · b = |a|·|b|·cos θ, যেখানে θ দুটি vector-এর মাঝের কোণ। তাই চিহ্ন দেখেই বলা যায়: ধনাত্মক হলে θ সূক্ষ্মকোণ (< 90°), শূন্য হলে লম্ব, ঋণাত্মক হলে স্থূলকোণ। আর a · b / |b| হলো b-এর দিকে a-এর projection — b-এর রেখায় a-এর “ছায়া”-র দৈর্ঘ্য।

উদাহরণ: a = (3, 4), b = (4, 0). a · b = 12, |a| = 5, |b| = 4, cos θ = 12/20 = 0.6, তাই θ ≈ 53.13°. Projection = 12/4 = 3 — a-এর ছায়া x-অক্ষে ঠিক ৩ একক। দূরত্বের বর্গও dot product: |a − b|² = (a − b) · (a − b). বর্গমূল না নিয়ে দূরত্বের বর্গ তুলনা করলে পূর্ণসংখ্যাতেই কাজ চলে — পর্ব ৪৯-এর closest pair কোডে ঠিক এটাই করা হয়েছিল।

Cross product — চিহ্নসহ ক্ষেত্রফল

দুই মাত্রায় cross product একটি সংখ্যা: a × b = a.x·b.y − a.y·b.x = |a|·|b|·sin θ, যেখানে θ হলো a থেকে b-তে ঘড়ির কাঁটার উল্টো দিকে (counter-clockwise) ঘোরার কোণ। এর মান a আর b দিয়ে তৈরি সামান্তরিকের ক্ষেত্রফল, কিন্তু চিহ্নসহ: b যদি a-এর বাঁ দিকে থাকে তবে ধনাত্মক, ডান দিকে হলে ঋণাত্মক, একই রেখায় হলে শূন্য। ওপরের a = (3, 4), b = (4, 0)-তে a × b = 3·0 − 4·4 = −16: b আছে a-এর ডানে (ঘড়ির কাঁটার দিকে), আর সামান্তরিকের ক্ষেত্রফল ১৬ (= 5 · 4 · sin 53.13° = 20 · 0.8).

তিনটি বিন্দুর ভাষায় একে বলে orientation test:

orient(o, a, b) = (a.x − o.x)(b.y − o.y) − (a.y − o.y)(b.x − o.x)

> 0 মানে o → a → b পথে বাঁ মোড় (counter-clockwise), < 0 মানে ডান মোড় (clockwise), = 0 মানে তিনটি বিন্দু collinear — একই সরলরেখায়। আর |orient| / 2 হলো ত্রিভুজ oab-এর ক্ষেত্রফল।

হিসাবo → a → b

                

                

                    

                        
ফল

                        

                            
orient

                            
চিহ্ন

                            
মোড়

                        

                    

                

            

        

        
    
            
  1. প্রস্তুতি। o থেকে a-এর দিকে হাঁটছি — x-অক্ষ বরাবর পূর্বে। প্রশ্ন: b-তে যেতে হলে কোন দিকে ঘুরব? দুটি vector u = a − o আর v = b − o বানিয়ে u × v বের করলেই উত্তর।
    2. 
            
  2. b = (2, 3) — বাঁ মোড়। 4·3 − 0·2 = ১২ > ০. পূর্বমুখী হাঁটলে উত্তর দিক বাঁয়ে, তাই মিলে গেল। ত্রিভুজ oab-এর ভূমি ৪, উচ্চতা ৩, ক্ষেত্রফল ৬ = ১২/২ — cross product আসলে দ্বিগুণ ক্ষেত্রফল।
    3. 
            
  3. b = (2, −3) — ডান মোড়। একই আকার, কিন্তু চিহ্ন উল্টো: −১২. মান একই (ক্ষেত্রফল ৬), দিক আলাদা — এই “চিহ্নসহ ক্ষেত্রফল”-ই cross product-এর শক্তি।
    4. 
            
  4. b = (8, 0) — একই রেখা। ০. b একই রেখায়, a-এর পরে। খেয়াল করুন, orientation শুধু “একই রেখায়” বলে — b, o আর a-এর মাঝে নাকি বাইরে, তা বলে না। সেটি আলাদা পরীক্ষায় দেখতে হয় (অংশ ৪).
    5. 
            
  5. যেকোনো জায়গায় একই। o = (1, 1) হলে পুরো ছবিটা শুধু সরে গেছে; u আর v আগের মতোই, ফলও ১২. orient শুধু আপেক্ষিক অবস্থান দেখে — তাই সবসময় আগে o বিয়োগ করে নিতে হয়। (a × b সরাসরি নিলে ভুল হবে, যদি না o মূলবিন্দু হয়।)
    6. 
        

    


    
    
৩ · পূর্ণসংখ্যা না দশমিক — epsilon-এর ফাঁদ


    
জ্যামিতির সবচেয়ে বড় শত্রু অ্যালগরিদম নয়, floating point error. double সংখ্যা বাইনারিতে রাখা হয়, আর ০.১-এর মতো সাধারণ দশমিক বাইনারিতে ঠিকঠাক লেখা যায় না। ফল দেখুন: (0.1, 0.3), (0.2, 0.6), (0.3, 0.9) — গাণিতিকভাবে তিনটিই y = 3x রেখায়। কিন্তু Python বা C++-এ double দিয়ে orient হিসাব করলে আসে প্রায় 2.08e-17 — শূন্য নয়, ধনাত্মক! অ্যালগরিদম ভাববে “বাঁ মোড়”. একটি convex hull অ্যালগরিদমে এমন একটি ভুল সিদ্ধান্ত পরের সিদ্ধান্তগুলোর সাথে অসংগত হয়ে যেতে পারে — ফল ভুল hull, অসীম লুপ বা crash.


    

        

            
কোঅর্ডিনেট পূর্ণসংখ্যা

            
সব হিসাব long long-এ। orient, দূরত্বের বর্গ, shoelace — শুধু গুণ, যোগ, বিয়োগ, তাই উত্তর একদম নির্ভুল। ভাগ, বর্গমূল আর কোণ (atan2) এড়িয়ে চলুন।

            প্রথম পছন্দ
        

        

            
দশমিক বাধ্যতামূলক

            
“শূন্য কি না” না দেখে |v| < ε দেখুন — এটি epsilon comparison. ε ইনপুটের মাপের সাথে মিলিয়ে বাছতে হয়; কোনো একটি “জাদুর” ε সবখানে চলে না।

            সাবধানে
        

        

            
Overflow-এর হিসাব

            
|x|, |y| ≤ 109 হলে পার্থক্য ≤ 2·109, গুণফল ≤ 4·1018, orient ≤ 8·1018 — long long-এর সীমা প্রায় 9.22·1018-এর ঠিক ভেতরে। আরও বড় হলে __int128.

            int নয়
        

    


    

        
৩২-বিটের int দিয়ে orient লিখলে কোঅর্ডিনেট ৫০,০০০-এর কাছাকাছি হলেই গুণফল 231 ছাড়িয়ে যায় — integer overflow, আর চিহ্ন উল্টে যেতে পারে। কনটেস্টে জ্যামিতির “Wrong Answer”-এর একটি বড় অংশ এই এক লাইনের ভুল। নিয়ম: struct-এর ভেতরেই x, y-কে long long করুন।

    


    
    
৪ · দুটি রেখাংশ কি ছেদ করে?


    
মানচিত্রে দুটি রাস্তা, বা একটি গেমে দেয়াল আর গুলির পথ — দুটি রেখাংশ AB আর CD কি একে অপরকে ছোঁয়? সরলরেখার সমীকরণ বানিয়ে ছেদবিন্দু বের করা যায়, কিন্তু তাতে ভাগ লাগে, আর সমান্তরাল রেখায় শূন্য দিয়ে ভাগ। Orientation দিয়ে segment intersection-এর পরীক্ষা অনেক পরিষ্কার:

    
    
        
  • সাধারণ ক্ষেত্র: C আর D যদি AB রেখার বিপরীত দুই পাশে থাকে (d1 = orient(A, B, C) আর d2 = orient(A, B, D)-এর চিহ্ন উল্টো), এবং A আর B যদি CD রেখার বিপরীত দুই পাশে থাকে (d3, d4-এর চিহ্ন উল্টো), তাহলে দুটি রেখাংশ ঠিক একটি ভেতরের বিন্দুতে কাটে।
    • 
        
  • বিশেষ ক্ষেত্র: কোনো d শূন্য হলে সংশ্লিষ্ট বিন্দুটি অন্য রেখাংশের রেখায় আছে। তখন দেখতে হয় বিন্দুটি রেখাংশের দুই প্রান্তের মাঝে (x আর y দুটিরই সীমার ভেতরে) কি না। চারটি d-ই শূন্য হলে দুটি রেখাংশ একই রেখায় — তখন এই চারটি “ভেতরে কি না” পরীক্ষাই বলে দেয় তারা কোথাও মিলেছে (overlap) কি না।
    • 
    


    

        

            

                
X crossingA→B, C→D


4  C . . . B . .
3  . \ . / . . .
2  . . X . . . .
1  . / . \ . . .
0  A . . . D . .
   0 1 2 3 4 5 6

            

            

                
T touchingA→B, C→D


4  . . . . . . .
3  . . D . . . .
2  . . │ . . . .
1  . . │ . . . .
0  A - C - B . .
   0 1 2 3 4 5 6

            

            

                
collinear overlapA→B, C→D


4  . . . . . . .
3  . . . . . . .
2  . . . . . . .
1  . . . . . . .
0  A - C = B - D
   0 1 2 3 4 5 6

            

            

                
collinear apartA→B, C→D


4  . . . . . . .
3  . . . . . . .
2  . . . . . . .
1  . . . . . . .
0  A - B C - D .
   0 1 2 3 4 5 6

            

            

                
parallelA→B, C→D


4  . . . . . . .
3  . . . . . . .
2  . . . . . . .
1  C - - - D . .
0  A - - - B . .
   0 1 2 3 4 5 6

            

            

                
boxes overlap onlyA→B, C→D


4  . . . . . . .
3  D . . . . . .
2  . \ . . . . .
1  . B \ . . . .
0  A . . C . . .
   0 1 2 3 4 5 6

            

            

                
চারটি orientation

                

                    
AB, CD

                    
d1, d2 (C, D বনাম AB)

                    
d3, d4 (A, B বনাম CD)

                    
ফল

                

            

        

        
    
            
  1. X আকারে কাটা। d1 = ১৬, d2 = −১৬: C আর D, AB-এর দুই পাশে। d3 = −১৬, d4 = ১৬: A আর B, CD-এর দুই পাশে। দুটি শর্তই সত্য, তাই ছেদ — (2, 2)-তে, X চিহ্নিত ঘরে।
    2. 
            
  2. T আকারে ছোঁয়া। d1 = ০ — C আছে AB-এর রেখায়। C = (2, 0), আর A–B-এর x-সীমা ০ থেকে ৪, y-সীমা ০ থেকে ০ — C ভেতরে। তাই ছেদ, যদিও “বিপরীত পাশ”-এর শর্ত (d1·d2 < 0) সত্য নয়। বিশেষ ক্ষেত্র বাদ দিলে এটি হারিয়ে যেত।
    3. 
            
  3. একই রেখায়, আংশিক মিল। চারটি d-ই ০. C = (2, 0) পড়েছে A–B-এর ভেতরে, তাই ছেদ — আসলে (2, 0) থেকে (4, 0) পর্যন্ত পুরো একটি অংশ মিলে গেছে (= চিহ্ন). রাস্তার মানচিত্রে দুটি রাস্তা একই পথে চললে এমন হয়।
    4. 
            
  4. একই রেখায়, কিন্তু ফাঁক। আবার চারটি d-ই ০, কিন্তু C, D কেউ A–B-এর ভেতরে নেই, A, B-ও C–D-এর ভেতরে নেই। ছেদ নেই। শুধু “চারটিই শূন্য, তাই একই রেখা, তাই ছেদ” ভাবলে এখানে ভুল হতো।
    5. 
            
  5. সমান্তরাল। d1 = d2 = ৪: C আর D দুটিই AB-এর একই (বাঁ) পাশে। প্রথম শর্তেই ব্যর্থ — কোনো ভাগ, কোনো ঢাল, কোনো শূন্য দিয়ে ভাগের ভয় ছাড়াই।
    6. 
            
  6. শুধু বাক্স মেলে। A–B-কে ঘেরা আয়তক্ষেত্র [0,1]×[0,1] আর C–D-এর [0,3]×[0,3] একে অপরের ওপর পড়ে, কিন্তু রেখাংশ কাটে না: d1 = −৩, d2 = ৩ (বিপরীত পাশ), কিন্তু d3 = ৯, d4 = ৩ (একই পাশ). অনেকে শুধু বাক্স মিলিয়ে দেখে — এটি সেই ভুলের উদাহরণ। বাক্স-পরীক্ষা দ্রুত বাদ দেওয়ার জন্য ভালো, উত্তরের জন্য নয়।
    7. 
        

    


    
INTERSECT(A, B, C, D)                      // segments AB and CD, integer points
    d1 = sign(orient(A, B, C));  d2 = sign(orient(A, B, D))
    d3 = sign(orient(C, D, A));  d4 = sign(orient(C, D, B))
    if d1 · d2 < 0 and d3 · d4 < 0: return true          // proper crossing
    if d1 == 0 and ON_BOX(A, B, C): return true          // C lies on AB
    if d2 == 0 and ON_BOX(A, B, D): return true
    if d3 == 0 and ON_BOX(C, D, A): return true
    if d4 == 0 and ON_BOX(C, D, B): return true
    return false
ON_BOX(A, B, P): min(A.x,B.x) ≤ P.x ≤ max(A.x,B.x) and min(A.y,B.y) ≤ P.y ≤ max(A.y,B.y)


    
সময় Θ(1) — আটটি গুণ আর কয়েকটি তুলনা। সঠিকতার মূল যুক্তি: ভেতরের কোনো বিন্দুতে কাটলে রেখাংশ দুটির প্রতিটি অন্যটির রেখাকে পার হয়, তাই প্রান্তবিন্দুগুলো বিপরীত পাশে; উল্টোদিকে, দুই জোড়াই বিপরীত পাশে থাকলে মধ্যবর্তী মানের যুক্তিতে রেখাংশ দুটি অবশ্যই একটি সাধারণ বিন্দু পায়। আর কোনো প্রান্তবিন্দু অন্য রেখাংশের ওপর পড়লে সেটি সরাসরি ON_BOX ধরে ফেলে।


    

        
        
    


    
    
৫ · জমির প্লটের ক্ষেত্রফল — shoelace সূত্র আর Pick-এর উপপাদ্য


    
ভূমি অফিসের মৌজা নকশায় প্রতিটি দাগ (plot) একটি বহুভুজ. জরিপকারী কোণগুলোর কোঅর্ডিনেট মেপে আনেন — ধরুন একটি পাঁচকোনা জমির কোণ (মিটারে) A(0,0), B(30,0), C(36,22), D(12,30), E(−4,14). জমিটা অনিয়মিত; ত্রিভুজে ভাগ করে আলাদা আলাদা মাপা ঝামেলার। Shoelace সূত্র এক লাইনে উত্তর দেয়:

    
2A = Σ (xi·yi+1 − xi+1·yi),  শেষ কোণের পরে আবার প্রথম কোণ

    
কোণগুলো ঘড়ির কাঁটার উল্টো দিকে সাজানো থাকলে যোগফল ধনাত্মক, ঘড়ির দিকে হলে ঋণাত্মক — তাই এর চিহ্ন দেখে বহুভুজের দিকও বোঝা যায়। কোণগুলো দুই সারিতে লিখে আড়াআড়ি গুণ করলে জুতার ফিতার মতো নকশা হয় — সেখান থেকেই নাম। কেন কাজ করে? প্রতিটি পদ xi·yi+1 − xi+1·yi হলো মূলবিন্দু O, Pi, Pi+1 ত্রিভুজের দ্বিগুণ চিহ্নসহ ক্ষেত্রফল — অর্থাৎ O-কে কেন্দ্র ধরে cross product. বহুভুজের বাইরের অংশগুলো একবার ধনাত্মক আর একবার ঋণাত্মক হয়ে কেটে যায়, থাকে ঠিক ভেতরের অংশ। সূত্রটি যেকোনো simple polygon-এ (যার বাহুগুলো নিজেদের কাটে না) খাটে — convex হওয়ার দরকার নেই।


    

        

            

                

                    
হিসাবের খাতামিটারে



                

                

                    

                        
চলতি যোগফল

                        

                            
বাহু

                            
এই পদ

                            
যোগফল (2A)

                        

                    

                

            

        

        
    
            
  1. সাজানো কোণ। পাঁচটি কোণ ঘড়ির কাঁটার উল্টো দিকে সাজানো। প্রতিটি বাহু Pi → Pi+1-এর জন্য একটি পদ, শেষে E → A দিয়ে বৃত্ত বন্ধ। মোট পাঁচটি গুণফল-জোড়া — Θ(n).
    2. 
            
  2. A → B. A মূলবিন্দুতে, তাই পদ ০ — O, A, B ত্রিভুজের কোনো ক্ষেত্রফল নেই।
    3. 
            
  3. B → C. 30·22 − 36·0 = ৬৬০ = O, B, C ত্রিভুজের দ্বিগুণ ক্ষেত্রফল। চলতি যোগফল ৬৬০.
    4. 
            
  4. C → D. 36·30 − 12·22 = ১০৮০ − ২৬৪ = ৮১৬. যোগফল ১৪৭৬.
    5. 
            
  5. D → E. 12·14 − (−4)·30 = ১৬৮ + ১২০ = ২৮৮. ঋণাত্মক কোঅর্ডিনেটে চিহ্ন সাবধানে — এখানেই হাতের হিসাবে সবচেয়ে বেশি ভুল হয়। যোগফল ১৭৬৪.
    6. 
            
  6. E → A, আর ফল। পদ ০, যোগফল ১৭৬৪ = 2A, তাই A = ৮৮২ বর্গমিটার। ১ শতাংশ (decimal) ≈ ৪০.৪৭ বর্গমিটার, তাই জমিটি প্রায় ২১.৭৯ শতাংশ। যোগফল ধনাত্মক — কোণগুলো সত্যিই counter-clockwise ক্রমে ছিল।
    7. 
        

    


    
Pick-এর উপপাদ্য — গ্রাফ কাগজের বিন্দু গোনা

    
সব কোণ যদি পূর্ণসংখ্যার বিন্দুতে (lattice point) থাকে, তাহলে ১৮৯৯ সালে অস্ট্রীয় গণিতবিদ Georg Pick-এর প্রকাশিত একটি সুন্দর সম্পর্ক খাটে — Pick-এর উপপাদ্য:

    
A = I + B/2 − 1

    
এখানে I = বহুভুজের একদম ভেতরের lattice point-এর সংখ্যা, B = সীমানার ওপরের lattice point-এর সংখ্যা। B সহজে গোনা যায়: (x1, y1) থেকে (x2, y2) বাহুতে প্রান্তসহ lattice point gcd(|Δx|, |Δy|) + 1টি, আর প্রতিটি কোণ দুটি বাহুতে পড়ে বলে প্রতি বাহুতে শুধু gcd(|Δx|, |Δy|) যোগ করলেই মোট B. আমাদের জমিতে B = 30 + 2 + 8 + 16 + 2 = ৫৮, তাই I = 882 − 29 + 1 = ৮৫৪. কনটেস্টে প্রায়ই উল্টো প্রশ্ন আসে — “বহুভুজের ভেতরে কয়টি পূর্ণসংখ্যার বিন্দু?” — shoelace দিয়ে A, gcd দিয়ে B, তারপর Pick থেকে I, সব Θ(n log C) সময়ে (C = কোঅর্ডিনেটের মাপ, gcd-এর জন্য).


    
নিচের প্রোগ্রাম orientation-এর তিনটি ক্ষেত্র, ওপরের ছয়টি রেখাংশ-জোড়া, আর জমির ক্ষেত্রফল ও Pick — সব একসাথে যাচাই করে।


    

        

            
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <initializer_list>
#include <numeric>
#include <vector>
using namespace std;
using ll = long long;
struct P { ll x, y; };
ll cross(P o, P a, P b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); }
int sgn(ll v) { return (v > 0) - (v < 0); }       // > 0 left turn, < 0 right turn, 0 collinear
bool onSeg(P a, P b, P p) {                        // p is collinear with a-b: inside the box?
    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) && min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}
bool intersect(P a, P b, P c, P d) {
    int d1 = sgn(cross(a, b, c)), d2 = sgn(cross(a, b, d)), d3 = sgn(cross(c, d, a)), d4 = sgn(cross(c, d, b));
    if (d1 * d2 < 0 && d3 * d4 < 0) return true;  // proper crossing
    return (d1 == 0 && onSeg(a, b, c)) || (d2 == 0 && onSeg(a, b, d)) ||
           (d3 == 0 && onSeg(c, d, a)) || (d4 == 0 && onSeg(c, d, b));
}
int main() {
    const char* turn[] = {"right turn (clockwise)", "collinear", "left turn (counter-clockwise)"};
    for (P b : {P{2, 3}, P{2, -3}, P{8, 0}}) {
        ll v = cross({0, 0}, {4, 0}, b);
        printf("orient((0,0),(4,0),(%lld,%lld)) = %lld -> %s\n", b.x, b.y, v, turn[sgn(v) + 1]);
    }
    struct T { const char* name; P a, b, c, d; } tests[] = {
        {"X crossing", {0, 0}, {4, 4}, {0, 4}, {4, 0}}, {"T touching", {0, 0}, {4, 0}, {2, 0}, {2, 3}},
        {"collinear overlap", {0, 0}, {4, 0}, {2, 0}, {6, 0}}, {"collinear apart", {0, 0}, {2, 0}, {3, 0}, {5, 0}},
        {"parallel", {0, 0}, {4, 0}, {0, 1}, {4, 1}}, {"boxes overlap only", {0, 0}, {1, 1}, {3, 0}, {0, 3}}};
    for (auto& t : tests) printf("%-19s: %s\n", t.name, intersect(t.a, t.b, t.c, t.d) ? "intersect" : "no");
    vector<P> plot = {{0, 0}, {30, 0}, {36, 22}, {12, 30}, {-4, 14}};   // corners in metres, counter-clockwise
    ll s = 0, B = 0; size_t n = plot.size();
    for (size_t i = 0; i < n; ++i) {
        P a = plot[i], b = plot[(i + 1) % n];
        s += a.x * b.y - b.x * a.y;                 // shoelace term
        B += gcd(llabs(a.x - b.x), llabs(a.y - b.y));   // lattice points on this edge
    }
    printf("shoelace sum = %lld, area = %.1f m^2 = %.2f decimal\n", s, s / 2.0, s / 2.0 / 40.4686);
    printf("Pick: boundary B = %lld, interior I = A - B/2 + 1 = %lld\n", B, (s - B + 2) / 2);
}

            

                
শেষ লাইন: Pick: boundary B = 58, interior I = A - B/2 + 1 = 854. পুরো আউটপুট আর ব্যাখ্যা নিচে।

            

        

        

            
from math import gcd

def cross(o, a, b):                         # > 0 left turn, < 0 right turn, 0 collinear
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def sgn(v):
    return (v > 0) - (v < 0)

def on_seg(a, b, p):                        # p is collinear with a-b: inside the box?
    return min(a[0], b[0]) <= p[0] <= max(a[0], b[0]) and min(a[1], b[1]) <= p[1] <= max(a[1], b[1])

def intersect(a, b, c, d):
    d1, d2 = sgn(cross(a, b, c)), sgn(cross(a, b, d))
    d3, d4 = sgn(cross(c, d, a)), sgn(cross(c, d, b))
    if d1 * d2 < 0 and d3 * d4 < 0:
        return True                         # proper crossing
    return ((d1 == 0 and on_seg(a, b, c)) or (d2 == 0 and on_seg(a, b, d)) or
            (d3 == 0 and on_seg(c, d, a)) or (d4 == 0 and on_seg(c, d, b)))

turn = ["right turn (clockwise)", "collinear", "left turn (counter-clockwise)"]
for b in [(2, 3), (2, -3), (8, 0)]:
    v = cross((0, 0), (4, 0), b)
    print(f"orient((0,0),(4,0),({b[0]},{b[1]})) = {v} -> {turn[sgn(v) + 1]}")
tests = [("X crossing", (0, 0), (4, 4), (0, 4), (4, 0)), ("T touching", (0, 0), (4, 0), (2, 0), (2, 3)),
         ("collinear overlap", (0, 0), (4, 0), (2, 0), (6, 0)), ("collinear apart", (0, 0), (2, 0), (3, 0), (5, 0)),
         ("parallel", (0, 0), (4, 0), (0, 1), (4, 1)), ("boxes overlap only", (0, 0), (1, 1), (3, 0), (0, 3))]
for name, a, b, c, d in tests:
    print(f"{name:<19}: {'intersect' if intersect(a, b, c, d) else 'no'}")
plot = [(0, 0), (30, 0), (36, 22), (12, 30), (-4, 14)]     # corners in metres, counter-clockwise
n = len(plot)
s = sum(plot[i][0] * plot[(i + 1) % n][1] - plot[(i + 1) % n][0] * plot[i][1] for i in range(n))
B = sum(gcd(abs(plot[i][0] - plot[(i + 1) % n][0]), abs(plot[i][1] - plot[(i + 1) % n][1])) for i in range(n))
print(f"shoelace sum = {s}, area = {s / 2:.1f} m^2 = {s / 2 / 40.4686:.2f} decimal")
print(f"Pick: boundary B = {B}, interior I = A - B/2 + 1 = {(s - B + 2) // 2}")

            

                
আউটপুট C++-এর সাথে হুবহু এক। Python-এর int-এর আকারের কোনো সীমা নেই, তাই এখানে overflow-এর ভয় নেই — কিন্তু float ঢুকলেই অংশ ৩-এর সমস্যা ফিরে আসে।

            

        

    


    

        
দুই ভাষাতেই আউটপুট:


orient((0,0),(4,0),(2,3)) = 12 -> left turn (counter-clockwise)
orient((0,0),(4,0),(2,-3)) = -12 -> right turn (clockwise)
orient((0,0),(4,0),(8,0)) = 0 -> collinear
X crossing         : intersect
T touching         : intersect
collinear overlap  : intersect
collinear apart    : no
parallel           : no
boxes overlap only : no
shoelace sum = 1764, area = 882.0 m^2 = 21.79 decimal
Pick: boundary B = 58, interior I = A - B/2 + 1 = 854

        
প্রথম তিন লাইন orientation stepper-এর তিনটি মান, পরের ছয়টি রেখাংশের stepper-এর ছয়টি সিদ্ধান্ত, শেষ দুটি জমির হিসাব। কোডের লক্ষণীয় দিক: (১) sgn চিহ্নকে −১, ০, ১-এ নামিয়ে আনে, তাই d1 * d2 < 0-এ বড় সংখ্যার গুণে overflow হয় না — orient-এর আসল মান গুণ করলে 8·1018 × 8·1018 হতে পারত। (২) onSeg শুধু বাক্স দেখে, কারণ এটি তখনই ডাকা হয় যখন বিন্দুটি আগেই একই রেখায় প্রমাণিত। (৩) Pick-এ I = (2A − B + 2)/2 পূর্ণসংখ্যায় হিসাব করা — A নিজে ভগ্নাংশ (x.5) হলেও ঠিক থাকে। (৪) “decimal” মানে শতাংশ: ৮৮২ / ৪০.৪৬৮৬ ≈ ২১.৭৯ — এখানে দশমিক শুধু শেষে, দেখানোর জন্য।

    


    
    
৬ · বিন্দুটি কি বহুভুজের ভেতরে? — ray casting


    
একটি অ্যাপ জানতে চায় ব্যবহারকারীর GPS অবস্থান কোন ইউনিয়ন বা ওয়ার্ডের সীমানার ভেতরে। এটি point in polygon সমস্যা। সবচেয়ে প্রচলিত সমাধান ray casting: বিন্দু থেকে ডান দিকে একটি অসীম রশ্মি (ray) টানুন, আর গুনুন সেটি বহুভুজের সীমানা কতবার পার হয়। বিজোড় হলে ভেতরে, জোড় হলে বাইরে। কারণ: অনেক দূরে রশ্মির শেষ নিশ্চিতভাবে বাইরে, আর প্রতিটি পার হওয়ায় ভেতর-বাইরে অবস্থা উল্টায় — এটি Jordan curve theorem-এর সরল রূপ।


    
কঠিন অংশ: রশ্মি ঠিক একটি কোণের ওপর দিয়ে গেলে সেটি এক পার হওয়া, দুই, নাকি শূন্য? সমাধান অর্ধ-খোলা নিয়ম: একটি বাহু (P, Q)-কে তখনই গুনুন যখন (P.y > y) আর (Q.y > y)-এর একটি সত্য, অন্যটি মিথ্যা — যেন কোণগুলো রশ্মির একটু ওপরে সরানো। নিচের অবতল (concave) বহুভুজে দেখুন — কোণ V1(0,0), V2(6,0), V3(6,5), V4(3,2), V5(0,5); ওপরের দিকে V4-এ একটি খাঁজ।


    

        

            

                
বহুভুজV4(3,2)-এ খাঁজ


5  + . . . . . +
4  │ \ . . . / │
3  │ . \ . / . │
2  │ . . v . . │
1  │ . . . . . │
0  + ─ ─ ─ ─ ─ +
   0 1 2 3 4 5 6

edges: V1V2  V2V3  V3V4  V4V5  V5V1

            

            

                
Q(3,4) — খাঁজের ভেতরX = পার হওয়া


5  + . . . . . +
4  │ \ . Q - X X
3  │ . \ . / . │
2  │ . . v . . │
1  │ . . . . . │
0  + ─ ─ ─ ─ ─ +
   0 1 2 3 4 5 6

V3V4 at x = 5   (5 > 3)  count
V2V3 at x = 6   (6 > 3)  count
V4V5 at x = 1   (1 < 3)  left of Q, skip
crossings = 2  -> even -> OUTSIDE

            

            

                
R(1,1)X = পার হওয়া


5  + . . . . . +
4  │ \ . . . / │
3  │ . \ . / . │
2  │ . . v . . │
1  │ R - - - - X
0  + ─ ─ ─ ─ ─ +
   0 1 2 3 4 5 6

V2V3 at x = 6   count
V3V4, V4V5: y range 2..5, ray y = 1 not inside
crossings = 1  -> odd -> INSIDE

            

            

                
S(1,2) — রশ্মি কোণ V4-এর ওপর দিয়েঅর্ধ-খোলা নিয়ম


5  + . . . . . +
4  │ \ . . . / │
3  │ . \ . / . │
2  │ S - X - - X
1  │ . . . . . │
0  + ─ ─ ─ ─ ─ +
   0 1 2 3 4 5 6

V3V4: (5 > 2) != (2 > 2)  -> count, x = 3
V4V5: (2 > 2) != (5 > 2)  -> count, x = 3
V2V3: (0 > 2) != (5 > 2)  -> count, x = 6
V5V1: x = 0 < 1, skip
crossings = 3  -> odd -> INSIDE

            

            

                
Winding numberকতবার ঘুরে আসে


walk V1 -> V2 -> V3 -> V4 -> V5 -> V1, watch the point

R(1,1) : the boundary turns once around R   -> winding 1 -> INSIDE
Q(3,4) : the boundary never turns around Q  -> winding 0 -> OUTSIDE

self-crossing polygon (a star drawn in one stroke):
  centre has winding 2 -> even-odd says OUTSIDE,
                          nonzero rule says INSIDE

            

        

        
    
            
  1. বহুভুজ। পাঁচটি বাহু। V3 → V4 → V5 অংশটি ওপর থেকে নিচে নেমে আবার ওঠে — একটি V আকারের খাঁজ। খাঁজের ভেতরের বিন্দু বহুভুজের বাইরে, যদিও তার নিচে আর দুই পাশে বহুভুজ।
    2. 
            
  2. Q(3, 4) — বাইরে। ডানের রশ্মি V3V4 বাহু পার হয় x = ৫-এ, তারপর ডান দেয়াল V2V3 পার হয় x = ৬-এ। মোট ২ — জোড়, তাই বাইরে। x নির্ণয়ে একটি ভাগ লাগে; পূর্ণসংখ্যায় রাখতে চাইলে “x > Q.x” তুলনাকে orientation-এর চিহ্নে বদলে নেওয়া যায় (অনুশীলন ৪).
    3. 
            
  3. R(1, 1) — ভেতরে। রশ্মি y = ১-এ; দুই তির্যক বাহুর y-সীমা ২ থেকে ৫, তাই তারা গোনায় আসে না। শুধু ডান দেয়াল — মোট ১, বিজোড়, ভেতরে।
    4. 
            
  4. S(1, 2) — কোণের ফাঁদ। রশ্মি ঠিক V4-এর ওপর দিয়ে যায়। অর্ধ-খোলা নিয়মে V4 “একটু ওপরে” ধরা হয়, তাই V3V4 আর V4V5 দুটিই গোনা হয়, সাথে ডান দেয়াল — মোট ৩, ভেতরে। সত্যিই তাই: y = ২ রেখায় x = ০ থেকে ৬ পুরোটাই বহুভুজে, শুধু V4 বিন্দুটি সীমানায়। কোণটিকে একবার গুনলে মোট ২ হতো — ভুল উত্তর “বাইরে”.
    5. 
            
  5. বিকল্প: winding number. সীমানা ধরে একবার হেঁটে দেখুন বিন্দুটিকে কতবার পুরো ঘুরে এলেন — এটি winding number. শূন্য হলে বাইরে। সাধারণ বহুভুজে দুই পদ্ধতির উত্তর এক; নিজেকে কাটে এমন আকারে (যেমন এক টানে আঁকা তারা) ফল আলাদা হতে পারে — তাই SVG আর অনেক গ্রাফিক্স লাইব্রেরিতে “even-odd” আর “nonzero” দুটি নিয়মই বেছে নেওয়া যায়।
    6. 
        

    


    
সময় Θ(n) প্রতি প্রশ্নে, প্রতিটি বাহু একবার দেখা হয়; জায়গা Θ(1). একই বহুভুজে লাখো প্রশ্ন এলে বহুভুজকে আগে থেকে সাজিয়ে রাখা যায়: convex বহুভুজে একটি কোণ থেকে ছড়ানো ত্রিভুজগুলোর ওপর binary search (পর্ব ১৮) চালিয়ে প্রতি প্রশ্ন O(log n). বিন্দুটি ঠিক সীমানায় থাকলে কী বলবেন (ভেতরে, বাইরে, নাকি “সীমানায়”) — সেটি সমস্যার বিবরণ থেকে ঠিক করুন, আর আগে আলাদা করে প্রতিটি বাহুর ওপর orient = ০ ও ON_BOX পরীক্ষা করুন।


    
    
৭ · Convex hull — Graham scan আর Andrew-এর monotone chain


    
একটি বোর্ডে কয়েকটি পেরেক পোঁতা। একটি রাবার ব্যান্ড টেনে সবগুলোর বাইরে দিয়ে ছেড়ে দিলে ব্যান্ডটি যে আকার নেয়, সেটিই convex hull — সব বিন্দুকে ধারণ করে এমন সবচেয়ে ছোট convex polygon. গ্রামের মাঠে ছড়িয়ে থাকা গাছগুলো ঘিরে সবচেয়ে কম তারের বেড়া, কোনো গেমে একটি জটিল আকারকে ঘিরে সহজ সংঘর্ষ-সীমানা, ছবির মধ্যে একটি বস্তুর আকার — সবখানে এই প্রশ্ন। Hull-এর কোণগুলো ইনপুটেরই কিছু বিন্দু; বাকিরা ভেতরে বা বাহুর ওপরে।


    
মূল পর্যবেক্ষণ: hull-এর ধার ধরে counter-clockwise হাঁটলে প্রতিটি কোণে বাঁয়ে ঘুরতে হয়। কোথাও ডানে ঘুরতে হলে বা সোজা যেতে হলে, সেই মাঝের বিন্দুটি কোণ নয়। দুটি বিখ্যাত অ্যালগরিদম ঠিক এই নিয়ম একটি stack দিয়ে প্রয়োগ করে।


    
Graham scan (১৯৭২)

    
Bell Labs-এর গণিতবিদ Ronald Graham ১৯৭২ সালে প্রকাশ করেন Graham scan: সবচেয়ে নিচের বিন্দু p0 (সমান হলে সবচেয়ে বাঁয়ের) বেছে নিন — এটি নিশ্চিতভাবে hull-এ। বাকিদের p0-এর চারপাশে polar angle অনুযায়ী সাজান। কোণ মাপতে atan2 লাগে না: a আগে আসবে যদি orient(p0, a, b) > 0. তারপর ক্রমানুসারে প্রতিটি বিন্দু stack-এ নিন — আর নেওয়ার আগে, যতক্ষণ ওপরের দুটি আর নতুন বিন্দু বাঁ মোড় না বানায়, ততক্ষণ pop. কোণে কোণে সমান হলে (p0-এর সাথে একই রেখা) দূরত্ব দিয়ে ক্রম ঠিক করতে হয় — এই খুঁটিনাটি Graham scan-এর সবচেয়ে বেশি ভুল হওয়া জায়গা।


    
Andrew-এর monotone chain (১৯৭৯)

    
A. M. Andrew ১৯৭৯ সালে একটি সহজতর রূপ দেন — monotone chain. কোণ অনুযায়ী নয়, শুধু (x, তারপর y) অনুযায়ী সাজান, যা যেকোনো লাইব্রেরির সাধারণ sort করে দেয়। তারপর দুটি পাস: বাঁ থেকে ডানে গিয়ে নিচের hull (lower hull), আর ডান থেকে বাঁয়ে ফিরে ওপরের hull (upper hull). দুটি জোড়া দিলেই পুরো hull, counter-clockwise ক্রমে।


    
MONOTONE-CHAIN(P)                      // 0-based; P sorted by (x, y), duplicates removed
    if |P| < 3: return P
    H = empty stack
    for i = 0 to n-1:                                  // lower hull
        while |H| ≥ 2 and orient(H[-2], H[-1], P[i]) ≤ 0: pop H
        push P[i]
    t = |H| + 1                                        // keep the lower hull safe
    for i = n-2 down to 0:                             // upper hull
        while |H| ≥ t and orient(H[-2], H[-1], P[i]) ≤ 0: pop H
        push P[i]
    pop H                                              // P[0] was pushed twice
    return H                                           // counter-clockwise


    
১০টি বিন্দু নিয়ে ধাপে ধাপে দেখুন — সাজানো ক্রমে (0,3) (1,1) (1,4) (2,5) (3,0) (3,3) (4,2) (5,1) (5,4) (6,2).


    

        

            

                
lower hull (বাঁ → ডান)# স্ট্যাকে · * এখনকার · x বাদ


5  . . o . . . .
4  . * . . . o .
3  # . . o . . .
2  . . . . o . o
1  . # . . . o .
0  . . . o . . .
   0 1 2 3 4 5 6

(0,3) : push
(1,1) : push
(1,4) : push (cross=3)

stack: (0,3) (1,1) (1,4)

            

            

                
lower hull (বাঁ → ডান)# স্ট্যাকে · * এখনকার · x বাদ


5  . . * . . . .
4  . x . . . o .
3  # . . o . . .
2  . . . . o . o
1  . # . . . o .
0  . . . o . . .
   0 1 2 3 4 5 6

(2,5) : pop (1,4) cross=-3, push (cross=6)

stack: (0,3) (1,1) (2,5)

            

            

                
lower hull (বাঁ → ডান)# স্ট্যাকে · * এখনকার · x বাদ


5  . . x . . . .
4  . o . . . o .
3  # . . o . . .
2  . . . . o . o
1  . # . . . o .
0  . . . * . . .
   0 1 2 3 4 5 6

(3,0) : pop (2,5) cross=-9, push (cross=3)

stack: (0,3) (1,1) (3,0)

            

            

                
lower hull (বাঁ → ডান)# স্ট্যাকে · * এখনকার · x বাদ


5  . . o . . . .
4  . o . . . o .
3  # . . x . . .
2  . . . . * . o
1  . # . . . o .
0  . . . # . . .
   0 1 2 3 4 5 6

(3,3) : push (cross=6)
(4,2) : pop (3,3) cross=-3, push (cross=5)

stack: (0,3) (1,1) (3,0) (4,2)

            

            

                
lower hull (বাঁ → ডান)# স্ট্যাকে · * এখনকার · x বাদ


5  . . o . . . .
4  . o . . . x .
3  # . . o . . .
2  . . . . x . *
1  . # . . . # .
0  . . . # . . .
   0 1 2 3 4 5 6

(5,1) : pop (4,2) cross=-3, push (cross=4)
(5,4) : push (cross=6)
(6,2) : pop (5,4) cross=-3, push (cross=1)

stack: (0,3) (1,1) (3,0) (5,1) (6,2)

            

            

                
upper hull (ডান → বাঁ)# স্ট্যাকে · * এখনকার · x বাদ


5  . . o . . . .
4  . o . . . # .
3  # . . * . . .
2  . . . . x . #
1  . # . . . # .
0  . . . # . . .
   0 1 2 3 4 5 6

(5,4) : push
(5,1) : push (cross=3)
(4,2) : pop (5,1) cross=-3, push (cross=4)
(3,3) : pop (4,2) cross=-3, push (cross=5)

stack: (0,3) (1,1) (3,0) (5,1) (6,2) (5,4) (3,3)

            

            

                
upper hull (ডান → বাঁ)# স্ট্যাকে · * এখনকার · x বাদ


5  . . * . . . .
4  . o . . . # .
3  # . . x . . .
2  . . . . o . #
1  . # . . . # .
0  . . . # . . .
   0 1 2 3 4 5 6

(3,0) : push (cross=6)
(2,5) : pop (3,0) cross=-3, pop (3,3) cross=-5, push (cross=5)

stack: (0,3) (1,1) (3,0) (5,1) (6,2) (5,4) (2,5)

            

            

                
upper hull (ডান → বাঁ)# স্ট্যাকে · * এখনকার · x বাদ


5  . . # . . . .
4  . x . . . # .
3  * . . o . . .
2  . . . . o . #
1  . # . . . # .
0  . . . # . . .
   0 1 2 3 4 5 6

(1,4) : push (cross=4)
(1,1) : push (cross=3)
(0,3) : pop (1,1) cross=-3, pop (1,4) cross=0, push (cross=8)

stack: (0,3) (1,1) (3,0) (5,1) (6,2) (5,4) (2,5) (0,3)

            

        

        
    
            
  1. শুরু, বাঁ থেকে ডানে। (0,3) আর (1,1) সরাসরি ঢোকে — দুটির কম থাকলে মোড়ের প্রশ্নই নেই। (1,4) আসার সময় orient((0,3), (1,1), (1,4)) = ৩ > ০, বাঁ মোড়, তাই সেও ঢোকে।
    2. 
            
  2. প্রথম pop. (2,5): orient((1,1), (1,4), (2,5)) = −৩ — ডান মোড়! নিচের সীমানা ধরে বাঁ থেকে ডানে চললে সবসময় বাঁয়ে ঘুরতে হবে, তাই (1,4) নিচের hull-এর কোণ হতে পারে না। Pop, তারপর orient((0,3), (1,1), (2,5)) = ৬ > ০ — push.
    3. 
            
  3. (3,0). orient((1,1), (2,5), (3,0)) = −৯ → (2,5) বাদ; orient((0,3), (1,1), (3,0)) = ৩ → push. Stack-এ এখন নিচের দিকে বাঁকা একটি বাটি: (0,3) (1,1) (3,0).
    4. 
            
  4. (3,3) ঢোকে, (4,2) তাকে সরায়। (3,3) বাঁ মোড়ে ঢোকে (৬), কিন্তু (4,2) এলে orient((3,0), (3,3), (4,2)) = −৩ → (3,3) বাদ। একটি বিন্দু আজ ঢুকে কাল বেরিয়ে যেতে পারে — কিন্তু একবারই।
    5. 
            
  5. Lower hull শেষ। (5,1) এসে (4,2)-কে সরায়, (5,4) ঢোকে, (6,2) এসে (5,4)-কে সরায় (−৩). শেষ orient((3,0), (5,1), (6,2)) = ১ — সামান্য বাঁ মোড়, তবু বাঁ। Lower hull: (0,3) (1,1) (3,0) (5,1) (6,2).
    6. 
            
  6. Upper hull, ডান থেকে বাঁয়ে। এখন stack-এর lower অংশ সুরক্ষিত — শুধু (6,2)-এর পরে যোগ হওয়া বিন্দু pop হতে পারে। (5,4), (5,1) ঢোকে; (4,2) এসে (5,1)-কে সরায় (−৩) — এটি শুধু ওপরের শিকল থেকে বাদ, নিচের শিকলে (5,1) থেকেই যায়। (3,3) এসে (4,2)-কে সরায়।
    7. 
            
  7. এক ধাপে দুটি pop. (3,0) ঢোকে (৬). (2,5) এলে orient((3,3), (3,0), (2,5)) = −৩ → (3,0) বাদ, তারপর orient((5,4), (3,3), (2,5)) = −৫ → (3,3)-ও বাদ, তারপর push. এক ধাপে অনেক pop হতে পারে, কিন্তু মোট pop কখনো মোট push ছাড়ায় না।
    8. 
            
  8. একই রেখা, আর শেষ। (1,4), (1,1) ঢোকে। (0,3) এলে (1,1) বাদ (−৩), তারপর orient((2,5), (1,4), (0,3)) = ০ — তিনটি একই রেখায়। ≤ 0 বলে (1,4)-ও বাদ, তাই hull-এ বাহুর মাঝের বিন্দু থাকে না। শেষে (0,3) দ্বিতীয়বার ঢোকে; সেটি ফেলে দিলে hull: (0,3) (1,1) (3,0) (5,1) (6,2) (5,4) (2,5) — ৭টি কোণ, shoelace-এ ক্ষেত্রফল ১৯.
    9. 
        

    


    
কেন সঠিক, আর কত দ্রুত

    
সঠিকতা (invariant, induction): lower পাসে P[0..i] প্রক্রিয়া করার পর stack ঠিক P[0..i]-এর lower hull — বাঁ থেকে ডানে একটি শিকল, যার প্রতিটি কোণে বাঁ মোড়, আর P[0..i]-এর প্রতিটি বিন্দু শিকলের ওপরে বা গায়ে। i = ০, ১-এ এটি স্পষ্টতই সত্য। নতুন P[i] সবচেয়ে ডানের (সাজানো ক্রমের কারণে), তাই সে lower hull-এ থাকবেই। যে H[-1] pop হয়, সে H[-2] থেকে P[i]-এর রেখাংশের ওপরে বা গায়ে পড়ে (orient ≤ 0) — তাই নতুন শিকলের ওপরে, কোণ হতে পারে না। আর যখন pop থামে, বাকি শিকলের শেষ মোড় বাঁ — invariant বজায় থাকে। Upper পাস একই যুক্তি, উল্টো দিকে।

    
সময়: সাজানো Θ(n log n). তারপর প্রতিটি বিন্দু প্রতি পাসে একবার push হয়, আর বড়জোর একবার pop — তাই দুই পাস মিলিয়ে Θ(n), যদিও একটি ধাপে অনেক pop হতে পারে। এটি amortized analysis-এর aggregate যুক্তি (পর্ব ৬০), আর পর্ব ১৩-এর monotonic stack-এর জ্যামিতিক রূপ। মোট Θ(n log n); ইনপুট আগে থেকে সাজানো থাকলে Θ(n). জায়গা: stack-এ Θ(n). Graham scan-এর হিসাবও একই: কোণ-অনুসারে sort Θ(n log n), scan Θ(n).


    
প্রোগ্রামটি ১০টি বিন্দুর hull ছাপে আর সূত্র দিয়ে বানানো ১২০টি বিন্দুতেও চালায় (x = i² mod 97, y = i³ mod 89 — দুই ভাষায় হুবহু এক ইনপুট). দুই ক্ষেত্রেই উত্তরকে একটি সহজ কিন্তু ধীর brute force-এর সাথে মেলানো হয়: প্রতিটি জোড়া (a, b)-কে hull-এর বাহু ধরা হয় যদি বাকি সব বিন্দু a → b-এর বাঁয়ে থাকে, বা একই রেখায় a আর b-এর মাঝে — Θ(n³).


    

        

            
#include <algorithm>
#include <compare>
#include <cstdio>
#include <initializer_list>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
struct P { ll x, y; auto operator<=>(const P&) const = default; };   // sorts by x, then y
ll cross(P o, P a, P b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); }
vector<P> hull(vector<P> p) {                   // p sorted, distinct; Andrew's monotone chain
    if (p.size() < 3) return p;
    vector<P> h;
    for (int pass = 0; pass < 2; ++pass) {      // lower hull left to right, then upper hull back
        size_t base = h.empty() ? 0 : h.size() - 1;   // upper pass keeps the finished lower hull
        for (size_t i = pass; i < p.size(); ++i) {
            P q = pass == 0 ? p[i] : p[p.size() - 1 - i];
            while (h.size() >= base + 2 && cross(h[h.size() - 2], h.back(), q) <= 0)
                h.pop_back();                   // right turn or straight: not a corner
            h.push_back(q);
        }
    }
    h.pop_back(); return h;                     // CCW; last point repeated the first
}
vector<P> brute(const vector<P>& p) {           // O(n^3): a-b is a hull edge if nobody is right of it
    vector<P> v;
    for (P a : p) for (P b : p) if (a != b && all_of(p.begin(), p.end(), [&](P c) {
        ll s = cross(a, b, c);
        return s > 0 || (s == 0 && (a.x - c.x) * (b.x - c.x) + (a.y - c.y) * (b.y - c.y) <= 0); })) v.push_back(a);
    sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); return v;
}
int main() {
    vector<P> fixed = {{0, 3}, {1, 1}, {2, 5}, {3, 0}, {3, 3}, {5, 1}, {5, 4}, {6, 2}, {4, 2}, {1, 4}}, big;
    for (ll i = 1; i <= 120; ++i) big.push_back({i * i % 97, i * i * i % 89});
    for (auto [name, p] : {pair{"fixed 10", fixed}, pair{"formula 120", big}}) {
        sort(p.begin(), p.end()); p.erase(unique(p.begin(), p.end()), p.end());
        vector<P> h = hull(p), hs = h; ll a = 0; sort(hs.begin(), hs.end());
        for (size_t i = 0; i < h.size(); ++i) a += h[i].x * h[(i + 1) % h.size()].y - h[(i + 1) % h.size()].x * h[i].y;
        printf("%s: %zu points, hull has %zu vertices, area = %lld.%d\n", name, p.size(), h.size(), a / 2, a % 2 ? 5 : 0);
        if (h.size() <= 10) { printf("  hull (CCW):"); for (P q : h) printf(" (%lld,%lld)", q.x, q.y); printf("\n"); }
        printf("  brute-force O(n^3) hull agrees: %s\n", hs == brute(p) ? "yes" : "NO");
    }
}

            

                
মূল লাইন: hull (CCW): (0,3) (1,1) (3,0) (5,1) (6,2) (5,4) (2,5). পুরো আউটপুট আর ব্যাখ্যা নিচে।

            

        

        

            
def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def hull(pts):                              # Andrew's monotone chain: CCW, no collinear points
    p = sorted(set(pts))
    if len(p) < 3:
        return p
    h = []
    for half in (p, p[-2::-1]):             # lower hull left to right, then upper hull back
        base = max(len(h) - 1, 0)           # upper pass keeps the finished lower hull
        for q in half:
            while len(h) >= base + 2 and cross(h[-2], h[-1], q) <= 0:
                h.pop()                     # right turn or straight: h[-1] is not a corner
            h.append(q)
    return h[:-1]                           # last point repeats the first

def brute(pts):                             # O(n^3): a-b is a hull edge if no point is right of it
    p = sorted(set(pts))
    v = {a for a in p for b in p if a != b and all(
        cross(a, b, c) > 0 or (cross(a, b, c) == 0 and
        (a[0] - c[0]) * (b[0] - c[0]) + (a[1] - c[1]) * (b[1] - c[1]) <= 0) for c in p)}
    return sorted(v)

def area2(h):                               # shoelace, twice the area
    return sum(h[i][0] * h[(i + 1) % len(h)][1] - h[(i + 1) % len(h)][0] * h[i][1] for i in range(len(h)))

fixed = [(0, 3), (1, 1), (2, 5), (3, 0), (3, 3), (5, 1), (5, 4), (6, 2), (4, 2), (1, 4)]
big = [(i * i % 97, i * i * i % 89) for i in range(1, 121)]
for name, pts in [("fixed 10", fixed), ("formula 120", big)]:
    h = hull(pts)
    a = area2(h)
    print(f"{name}: {len(set(pts))} points, hull has {len(h)} vertices, area = {a // 2}.{5 if a % 2 else 0}")
    if len(h) <= 10:
        print("  hull (CCW):", " ".join(f"({x},{y})" for x, y in h))
    print("  brute-force O(n^3) hull agrees:", "yes" if sorted(h) == brute(pts) else "NO")

            

                
আউটপুট C++-এর সাথে হুবহু এক। Python-এ tuple নিজেই (x, তারপর y) ক্রমে তুলনা হয়, তাই sorted(set(pts)) এক লাইনে সাজানো আর ডুপ্লিকেট বাদ — দুটিই করে।

            

        

    


    

        
দুই ভাষাতেই আউটপুট:


fixed 10: 10 points, hull has 7 vertices, area = 19.0
  hull (CCW): (0,3) (1,1) (3,0) (5,1) (6,2) (5,4) (2,5)
  brute-force O(n^3) hull agrees: yes
formula 120: 119 points, hull has 13 vertices, area = 7981.0
  brute-force O(n^3) hull agrees: yes

        
১০টি বিন্দুর hull ঠিক stepper-এর ৭টি কোণ, ক্ষেত্রফল ১৯. সূত্রের ১২০টি বিন্দুর মধ্যে একটি জোড়া মিলে গেছে, তাই আলাদা বিন্দু ১১৯টি — ডুপ্লিকেট বাদ না দিলে monotone chain-এর stack-এ একই বিন্দু দুবার উঠতে পারত। Hull-এ মাত্র ১৩টি কোণ — বেশিরভাগ বিন্দু ভেতরে। Brute force এখানে বড়জোর প্রায় ১৭ লাখ orientation হিসাব করতে পারে (১১৯ × ১১৮ × ১১৯), monotone chain করে কয়েকশো। কোডের খুঁটিনাটি: (১) <= 0-এ pop মানে বাহুর মাঝের collinear বিন্দু বাদ; সেগুলো রাখতে চাইলে < 0 — কিন্তু তখন সব বিন্দু একই রেখায় থাকলে বিশেষ যত্ন লাগে। (২) base upper পাসে lower hull-কে রক্ষা করে — এটি না থাকলে upper পাস নিচের শিকলও খেয়ে ফেলত। (৩) ক্ষেত্রফল দ্বিগুণ আকারে পূর্ণসংখ্যায় রেখে শেষে “.0” বা “.5” ছাপা হয়েছে — কোনো double লাগেনি।

    


    
    
৮ · Gift wrapping, নিম্নসীমা আর সবচেয়ে দূরের জোড়া


    
Jarvis march — উপহার মোড়ানো

    
১৯৭৩ সালে R. A. Jarvis একটি আরও স্বাভাবিক পদ্ধতি দেন — gift wrapping বা Jarvis march. সবচেয়ে বাঁয়ের বিন্দু থেকে শুরু করুন। প্রতিটি ধাপে বাকি সব বিন্দু দেখে এমন একটি q বাছুন যাতে বাকি সবাই বর্তমান → q রেখার বাঁয়ে থাকে (orient দিয়ে একটি লুপে). তারপর q থেকে একই কাজ, যতক্ষণ না শুরুতে ফিরে আসেন — যেন উপহারের কাগজ চারপাশে মোড়ানো। প্রতিটি ধাপ Θ(n), আর ধাপ ঠিক h টি (h = hull-এর কোণের সংখ্যা): মোট Θ(nh). এমন অ্যালগরিদম, যার সময় আউটপুটের আকারের ওপরও নির্ভর করে, তাকে বলে output-sensitive algorithm. h ছোট হলে (যেমন h = ৫) এটি Θ(n), monotone chain-এর চেয়ে দ্রুত; কিন্তু সব বিন্দু একটি বৃত্তের ওপর থাকলে h = n, তখন Θ(n²).


    

        

            
অ্যালগরিদমবছরসময়মূল কৌশল

            
                
Brute force (সব জোড়া বাহু)—Θ(n³)প্রতিটি জোড়ার জন্য সব বিন্দুর orientation

                
Graham scan১৯৭২Θ(n log n)কোণ অনুযায়ী sort + stack

                
Jarvis march১৯৭৩Θ(nh)প্রতিবার পরের কোণ খোঁজা

                
Andrew-এর monotone chain১৯৭৯Θ(n log n)(x, y) sort + দুই পাসে stack

                
Chan-এর অ্যালগরিদম১৯৯৬O(n log h)ছোট দলে Graham, তারপর Jarvis

            
        

    


    
Ω(n log n) — sort-এর চেয়ে দ্রুত সম্ভব নয়

    
Convex hull কি sort ছাড়া হতে পারে? না — অন্তত তুলনা-ভিত্তিক গণনায়। প্রমাণ একটি reduction: ধরুন n টি সংখ্যা x1, …, xn সাজাতে হবে। প্রতিটিকে বিন্দু (xi, xi²) বানান — সবগুলো পরাবৃত্ত y = x²-এর ওপর, আর পরাবৃত্ত convex বলে প্রতিটি বিন্দুই hull-এর কোণ। Hull-কে সবচেয়ে বাঁয়ের বিন্দু থেকে counter-clockwise পড়লে x-গুলো ছোট থেকে বড় ক্রমে আসে — সংখ্যাগুলো সাজানো হয়ে গেল! বিন্দু বানানো আর পড়া Θ(n). তাই hull যদি o(n log n)-এ হতো, sort-ও হতো — কিন্তু পর্ব ২৪-এ দেখেছেন তুলনা-ভিত্তিক sort-এর lower bound Ω(n log n). অতএব hull (ক্রমসহ) Ω(n log n), আর Graham ও Andrew asymptotically সেরা।


    

        
আরও গভীরে: সব বিন্দুর মধ্যে সবচেয়ে দূরের জোড়া (diameter) সবসময় hull-এর দুটি কোণ। Hull পেয়ে গেলে rotating calipers দিয়ে Θ(h) সময়ে বের করা যায়: hull-এর দুই পাশে দুটি সমান্তরাল রেখা (চিমটার দুই বাহুর মতো) চেপে ধরুন, তারপর hull-এর চারপাশে ঘোরান। যে জোড়া কোণ একসাথে দুই রেখা ছোঁয় (antipodal pair), শুধু তাদের মধ্যেই উত্তর — আর এমন জোড়া Θ(h)টি, দুই pointer-এর মতো (পর্ব ১৬) একদিকে এগিয়ে পাওয়া যায়। কোডে: প্রতিটি বাহু (hi, hi+1)-এর জন্য j-কে ততক্ষণ এগিয়ে নিন যতক্ষণ ত্রিভুজ (hi, hi+1, hj)-এর ক্ষেত্রফল (orient) বাড়ে। Shamos ১৯৭৮ সালে diameter-এর জন্য পদ্ধতিটি ব্যবহার করেন, আর Godfried Toussaint ১৯৮৩ সালে “rotating calipers” নাম দিয়ে একে ন্যূনতম ঘেরা আয়তক্ষেত্র, দুই বহুভুজের দূরত্বসহ বহু সমস্যায় ছড়িয়ে দেন। মোট খরচ hull-সহ O(n log n) — brute force-এর Θ(n²)-এর বদলে।

    


    
    
৯ · Line sweep, বাস্তব প্রয়োগ আর ইতিহাস


    
পর্ব ৫০-এ interval-এর সমস্যায় দেখেছেন sweep line: একটি কাল্পনিক রেখা বাঁ থেকে ডানে টানা হয়, আর শুধু “ঘটনা”-র বিন্দুতে কাজ হয়। জ্যামিতিতে এটি আরও শক্তিশালী, কারণ রেখার গায়ে থাকা বস্তুগুলোকে একটি balanced BST-এ (C++-এর std::set) y অনুযায়ী সাজিয়ে রাখা যায়।

    
    
        
  • Closest pair sweep দিয়ে: বিন্দুগুলো x অনুযায়ী সাজান, এখন পর্যন্ত সেরা দূরত্ব d. রেখা যখন বিন্দু p-তে, তখন p.x − d-এর চেয়ে বাঁয়ের বিন্দুগুলো set থেকে বাদ দিন, আর set-এ শুধু y-এ [p.y − d, p.y + d] সীমার বিন্দু দেখুন। পর্ব ৪৯-এর strip lemma-র মতো যুক্তিতে এমন বিন্দু ধ্রুবক সংখ্যক, তাই মোট O(n log n) — divide and conquer-এর একই ফল, কিন্তু রিকার্শন ছাড়া।
    • 
        
  • কোনো দুটি রেখাংশ কি কাটে? Shamos ও Hoey (১৯৭৬): রেখাংশগুলোর প্রান্তবিন্দু হলো ঘটনা; set-এ রেখার গায়ের রেখাংশগুলো ওপর-নিচ ক্রমে। মূল অন্তর্দৃষ্টি — প্রথম ছেদের ঠিক আগে দুটি রেখাংশ set-এ পাশাপাশি থাকতে বাধ্য, তাই ঢোকানো বা বাদ দেওয়ার সময় শুধু প্রতিবেশীদের সাথে অংশ ৪-এর পরীক্ষা চালালেই চলে: O(n log n).
    • 
        
  • সব ছেদ খোঁজা: Bentley–Ottmann অ্যালগরিদম (১৯৭৯) ছেদবিন্দুগুলোকেও ঘটনা হিসেবে একটি priority queue-তে রাখে, আর ছেদে দুটি রেখাংশের ক্রম অদলবদল করে: O((n + k) log n), যেখানে k = ছেদের সংখ্যা। সব জোড়া দেখার Θ(n²)-এর চেয়ে অনেক ভালো যখন k ছোট।
    • 
    


    

        

            
মানচিত্র ও GIS

            
GPS বিন্দু কোন ওয়ার্ডে (point in polygon), প্লটের ক্ষেত্রফল (shoelace), নদী আর সড়কের মানচিত্র মিলিয়ে সেতুর জায়গা খোঁজা (segment intersection), সবচেয়ে কাছের হাসপাতাল।

            মানচিত্র
        

        

            
গেমে সংঘর্ষ

            
প্রথমে সস্তা বাক্স-পরীক্ষা আর sweep দিয়ে সম্ভাব্য জোড়া বাছাই, তারপর convex আকারে নির্ভুল পরীক্ষা — separating axis theorem: দুটি convex আকার না কাটলে এমন একটি রেখা আছে যা তাদের আলাদা করে।

            collision
        

        

            
রোবটিক্স

            
বাধার convex hull নিয়ে নিরাপদ এলাকা, রোবটের আকার দিয়ে বাধাকে “ফুলিয়ে” নিয়ে বিন্দু-রোবটের পথ খোঁজা; বহুভুজ বাধার মাঝে সবচেয়ে ছোট পথ বাধার কোণ ছুঁয়ে যায়।

            পথ পরিকল্পনা
        

    


    

        
ইউক্লিডের জ্যামিতি দুই হাজার বছরেরও বেশি পুরোনো, কিন্তু “কত দ্রুত” প্রশ্নটি নতুন। Michael Ian Shamos ১৯৭৫ সালে “Geometric Complexity” প্রবন্ধে আর Dan Hoey-র সাথে closest pair-এর কাজে জ্যামিতিক সমস্যাকে অ্যালগরিদমের চোখে দেখার কাঠামো দাঁড় করান — সমস্যার নিম্নসীমা, reduction আর দক্ষ অ্যালগরিদম একসাথে। ১৯৭৮ সালে Yale বিশ্ববিদ্যালয়ে তাঁর PhD thesis-এর নামই ছিল Computational Geometry, আর এটিকেই সাধারণত এই শাখার জন্ম ধরা হয়। পরে Franco Preparata-র সাথে লেখা Computational Geometry: An Introduction (১৯৮৫) বহু বছর এই বিষয়ের প্রধান পাঠ্যবই ছিল।

    


    

        
পরীক্ষা ও ইন্টারভিউতে

        
    
            
  • “তিনটি বিন্দু বাঁ মোড় না ডান মোড়, কীভাবে বুঝবেন?” — orient(o, a, b) = (a − o) × (b − o); ধনাত্মক বাঁ, ঋণাত্মক ডান, শূন্য collinear.
    • 
            
  • “দুটি রেখাংশের ছেদ পরীক্ষার সব ক্ষেত্র লিখুন।” — চারটি orientation; বিপরীত চিহ্নের দুটি জোড়া, নয়তো শূন্য orientation-এর সাথে বাক্সের ভেতরে থাকা।
    • 
            
  • “Graham scan বা monotone chain-এর complexity কত, কেন?” — Θ(n log n): sort; stack-এ প্রতিটি বিন্দু একবার push, বড়জোর একবার pop.
    • 
            
  • “Convex hull-এর Ω(n log n) নিম্নসীমা প্রমাণ করুন।” — sort থেকে reduction: x → (x, x²), hull-এর ক্রম = সাজানো ক্রম।
    • 
            
  • “কোঅর্ডিনেট 109 পর্যন্ত — কোন টাইপ?” — long long; orient সর্বোচ্চ প্রায় 8·1018, int-এ overflow, double-এ ভুল চিহ্ন।
    • 
        

    


    

        
        
    


    
    
১০ · AI-এর যুগে computational geometry


    
জ্যামিতির কোড AI চমৎকারভাবে লিখে দেয় — আর ঠিক এখানেই বিপদ, কারণ বেশিরভাগ ভুল সাধারণ ইনপুটে ধরা পড়ে না। সমস্যা দেখা দেয় একই রেখার বিন্দু, ডুপ্লিকেট, কোণের ওপর রশ্মি বা বিশাল কোঅর্ডিনেটে। যেসব ভুল বারবার দেখা যায়:


    

        

            
AI-এর ভুলফলকীভাবে ধরবেন

            
                
পূর্ণসংখ্যার ইনপুটেও double আর atan2 দিয়ে কোণ-sortপ্রায় একই কোণের বিন্দুতে ভুল ক্রম, ভুল hullএকই রেখার কয়েকটি বিন্দু আর বড় কোঅর্ডিনেট দিয়ে পরীক্ষা

                
int-এ cross productকোঅর্ডিনেট প্রায় 5·104 ছাড়ালেই overflow, উল্টো চিহ্নকোঅর্ডিনেট ±109 দিয়ে brute force-এর সাথে মেলান

                
রেখাংশের ছেদে collinear ক্ষেত্র বাদT-ছোঁয়া বা overlap “ছেদ নেই” বলেঅংশ ৪-এর ছয়টি ক্ষেত্র চালান

                
Hull-এ ডুপ্লিকেট বা সব বিন্দু একই রেখায়একই বিন্দু দুবার, বা ভুল আকার, বা crashn = ১, ২, সব সমান, সব এক রেখায় — edge case

                
Ray casting-এ কোণের ওপর রশ্মিকোণ দুবার বা শূন্যবার গোনারশ্মি ঠিক কোনো কোণ দিয়ে যায় এমন বিন্দু দিন

                
“Jarvis march O(n log n)” বা “hull O(n)” দাবিভুল complexityবৃত্তের ওপর n টি বিন্দুতে সময় মাপুন; sort-এর reduction মনে রাখুন

            
        

    


    

        
AI-কে কোডের সাথে প্রমাণ, edge case আর পরীক্ষাও দিতে বলুন:

        
আমি C++-এ [সমস্যা, যেমন convex hull / রেখাংশের ছেদ / point in polygon] লিখতে চাই। কোঅর্ডিনেট পূর্ণসংখ্যা, |x|, |y| ≤ 10^9. শর্তগুলো:

১. শুধু long long-এ orientation (cross product) দিয়ে লেখো — double, atan2, ভাগ বা বর্গমূল ব্যবহার করবে না। কোথাও overflow হতে পারে কি না, হিসাব করে দেখাও।
২. একই রেখার বিন্দু, ডুপ্লিকেট, n = ১ বা ২, আর সব বিন্দু এক রেখায় — প্রতিটি ক্ষেত্রে কোড কী করে, স্পষ্ট বলো।
৩. সঠিকতার একটি ছোট যুক্তি (invariant) আর সময় ও জায়গার complexity দাও।
৪. একটি O(n³) বা O(n²) brute force আর একটি stress test লেখো: ছোট এলোমেলো ইনপুটে (কোঅর্ডিনেট 0 থেকে 5, যাতে অনেক বিন্দু এক রেখায় পড়ে) দুটির উত্তর মেলাবে, না মিললে ইনপুট ছাপবে।

    


    
AI-এর দেওয়া জ্যামিতির কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

    
    
        
    • 
        
    • 
        
    • 
        
    • 
        
    • 
        
    • 
    


    
    

        
 ভাবনার প্রশ্ন

        
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন — তারপর “→ উত্তর” চাপুন।


        

            প্র ০১জ্যামিতি তো হাজার বছরের পুরোনো — তাহলে ১৯৭০-এর দশকে “computational geometry” আলাদা শাখা হলো কেন, আর Shamos ঠিক কী নতুন আনলেন?
            

                
প্রাচীন জ্যামিতি জানতে চাইত “কী সত্য” — ত্রিভুজের কোণের যোগফল, বৃত্তের ক্ষেত্রফল। কম্পাস আর রুলার দিয়ে “নির্মাণ” ছিল একধরনের অ্যালগরিদম, কিন্তু কত ধাপ লাগে সেই প্রশ্ন প্রায় কেউ করেনি। ১৯৬০-এর দশকে কম্পিউটার গ্রাফিক্স, CAD (যন্ত্রাংশের নকশা) আর মানচিত্র তৈরিতে হাজার হাজার বিন্দু আর রেখা নিয়ে কাজ শুরু হয়, আর প্রত্যেকে নিজের মতো করে একই সমস্যা আবার সমাধান করছিলেন — কেউ জানতেন না কোন সমাধান ভালো, বা আরও ভালো সম্ভব কি না।

                
Michael Shamos-এর অবদান ছিল এই বিচ্ছিন্ন কৌশলগুলোকে অ্যালগরিদম তত্ত্বের কাঠামোয় আনা। ১৯৭৫ সালের প্রবন্ধে আর Dan Hoey-র সাথে closest pair-এর কাজে তিনি একসাথে তিনটি জিনিস করেন: জ্যামিতিক সমস্যার স্পষ্ট সংজ্ঞা, দক্ষ অ্যালগরিদম (divide and conquer, Voronoi diagram), আর নিম্নসীমা — সাধারণত sort বা element uniqueness থেকে reduction দিয়ে। এই পর্বের convex hull-এর Ω(n log n) যুক্তি ঠিক এই ধারার। ১৯৭৮ সালে Yale-এ তাঁর thesis “Computational Geometry” পুরো তালিকাটি এক জায়গায় আনে, আর নামটিই শাখার নাম হয়ে যায়।

                
এরপর দ্রুত গবেষণা বাড়ে: ১৯৮০-এর দশকে নিয়মিত সম্মেলন (ACM Symposium on Computational Geometry, ১৯৮৫ থেকে), Preparata–Shamos-এর পাঠ্যবই, Delaunay triangulation, point location, range searching-এর তত্ত্ব। মজার ব্যাপার, Shamos নিজে পরে আইনজীবী হন আর ভোটযন্ত্রের নিরাপত্তা ও মেধাস্বত্ব নিয়ে কাজ করেন — কিন্তু তাঁর সংজ্ঞায়িত প্রশ্নগুলো আজও এই শাখার পাঠ্যসূচির ভিত্তি। আজ GIS, রোবটিক্স, গেম ইঞ্জিন, চিপের নকশা আর 3D প্রিন্টিং সফটওয়্যার — সবখানে এই অ্যালগরিদমগুলো চলে।

                
মূল উপলব্ধি: একটি নতুন শাখা জন্মায় যখন কেউ ছড়িয়ে থাকা কৌশলগুলোকে একটি সাধারণ ভাষায় — সংজ্ঞা, অ্যালগরিদম আর নিম্নসীমা — বাঁধেন। “কী সত্য” থেকে “কত দ্রুত, আর এর চেয়ে দ্রুত কি সম্ভব” — এই প্রশ্ন বদলই computational geometry.

            

        


        

            প্র ০২বাস্তব সফটওয়্যারে কোঅর্ডিনেট প্রায়ই দশমিক। তাহলে CAD বা GIS প্রোগ্রাম floating point-এর ভুল থেকে কীভাবে বাঁচে?
            

                
সমস্যাটি শুধু তাত্ত্বিক নয়। ১৯৯০-এর দশকে গবেষকরা দেখান, জনপ্রিয় জ্যামিতি সফটওয়্যারে convex hull বা দুই বহুভুজের মিলন (union) হিসাবের সময় কিছু ইনপুটে প্রোগ্রাম crash করে, অসীম লুপে পড়ে, বা নিজেকে কাটা অসম্ভব বহুভুজ তৈরি করে। কারণ অংশ ৩-এর মতো: একটি orientation-এর চিহ্ন ভুল হলে পরের সিদ্ধান্তগুলো তার সাথে অসংগত হয় — অ্যালগরিদম ধরে নেয় “a, b-এর বাঁয়ে আর b, c-এর বাঁয়ে, তাই …”, অথচ সংখ্যাগুলো এমন সিদ্ধান্ত দিয়েছে যা কোনো বাস্তব জ্যামিতিতে একসাথে সম্ভব নয়।

                
সমাধানের তিনটি প্রধান ধারা আছে। প্রথম, নির্ভুল predicate: orientation-এর মতো সিদ্ধান্তগুলো এমনভাবে হিসাব করা যাতে চিহ্ন সবসময় ঠিক হয়। ১৯৯৭ সালে Jonathan Shewchuk “adaptive precision” পদ্ধতি প্রকাশ করেন — প্রথমে সাধারণ double-এ হিসাব, আর ফল যদি শূন্যের এত কাছে হয় যে চিহ্ন সন্দেহজনক, শুধু তখনই বেশি নির্ভুলতায় আবার। বেশিরভাগ ইনপুটে খরচ প্রায় সাধারণ হিসাবের সমান। দ্বিতীয়, CGAL-এর মতো লাইব্রেরির নীতি “exact predicates, inexact constructions”: সিদ্ধান্ত (বাঁ না ডান) নির্ভুল, কিন্তু নতুন বিন্দু (যেমন ছেদবিন্দু) আনুমানিক — বেশিরভাগ অ্যালগরিদমের সঠিকতা শুধু সিদ্ধান্তের ওপর নির্ভর করে। তৃতীয়, একই রেখা বা একই বৃত্তের মতো “অধঃপতিত” (degenerate) ক্ষেত্রগুলো এড়াতে প্রতীকী ক্ষুদ্র নাড়াচাড়া (symbolic perturbation) — Edelsbrunner ও Mücke ১৯৯০ সালে “Simulation of Simplicity” নামে এর একটি পদ্ধতি দেন।

                
কনটেস্টে ব্যবহারিক নিয়ম সহজ: ইনপুট পূর্ণসংখ্যা হলে পুরো সমাধান পূর্ণসংখ্যায় রাখুন; দশমিক ইনপুট হলে নির্দিষ্ট দশমিক ঘর পর্যন্ত দেওয়া থাকলে (যেমন ২ ঘর) ১০০ দিয়ে গুণ করে পূর্ণসংখ্যা বানান; আর একান্ত দরকার হলে ε দিয়ে তুলনা করুন, সব জায়গায় একই নিয়মে।

                
মূল উপলব্ধি: জ্যামিতি অ্যালগরিদমের সঠিকতার প্রমাণ ধরে নেয় যে প্রতিটি “বাঁ না ডান” সিদ্ধান্ত নির্ভুল। Robust সফটওয়্যার তাই গতির আগে সিদ্ধান্তের নির্ভুলতা নিশ্চিত করে।

            

        


        

            প্র ০৩Hull-এ কোণ যদি খুব কম হয় (h ছোট), তাহলে কি n log n-এর চেয়ে দ্রুত পাওয়া যায়? Chan-এর অ্যালগরিদম কী করে?
            

                
Jarvis march Θ(nh), Graham Θ(n log n). h ছোট হলে Jarvis জেতে, বড় হলে Graham. দুটোর সেরাটা একসাথে — O(n log h) — কি সম্ভব? ১৯৮৬ সালে David Kirkpatrick ও Raimund Seidel প্রথম O(n log h) অ্যালগরিদম দেন, প্রবন্ধের শিরোনামে প্রশ্ন রেখে: “The ultimate planar convex hull algorithm?” তাঁদের কৌশল ছিল উল্টো divide and conquer — আগে মাঝের রেখা পার হওয়া hull-এর বাহুটি (bridge) linear time-এ খুঁজে বের করা, তারপর দুই পাশে রিকার্শন (“marriage before conquest”). তাঁরা দেখান যে Ω(n log h)-ও নিম্নসীমা, তাই এটি সেরা।

                
১৯৯৬ সালে Timothy Chan অনেক সহজ একটি পদ্ধতি দেন। ধরুন h আগে থেকে জানা, বা অন্তত একটি অনুমান m ≥ h. বিন্দুগুলোকে m আকারের n/m টি দলে ভাগ করুন, প্রতিটি দলে Graham scan — মোট O(n log m). তারপর পুরো hull-এর জন্য Jarvis march চালান, কিন্তু প্রতিটি ধাপে n টি বিন্দু না দেখে প্রতিটি দলের ছোট hull-এ binary search করে সেই দলের সেরা প্রার্থী খুঁজুন — প্রতি ধাপে O((n/m) log m), h ধাপে O(n log m). m = h হলে মোট O(n log h). h তো আগে জানা নেই! তাই m = 4, 16, 256, … — প্রতিবার আগের বর্গ — দিয়ে চেষ্টা করুন, আর m ধাপের মধ্যে hull বন্ধ না হলে থেমে পরের m. খরচের যোগফল একটি দ্রুত বাড়া ধারা, যার শেষ পদই প্রাধান্য পায় — মোট O(n log h).

                
এই “অনুমান দ্বিগুণ বা বর্গ করে চেষ্টা” কৌশলটি পর্ব ১৮-এর exponential search-এর আত্মীয়, আর অনেক output-sensitive অ্যালগরিদমে কাজে লাগে। বাস্তবে অবশ্য Andrew-এর monotone chain-ই বেশি চলে — সরল, cache-বান্ধব, আর sort খুব দ্রুত।

                
মূল উপলব্ধি: Complexity শুধু ইনপুটের আকারে নয়, আউটপুটের আকারেও মাপা যায়। আর দুটি অ্যালগরিদমের শক্তি জোড়া দিতে প্রায়ই একটি অজানা মাপের চতুর অনুমানই যথেষ্ট।

            

        


        

            প্র ০৪Hull শুধু কোণগুলোর সেট চাইলে (ক্রম ছাড়া) sort-এর reduction কাজ করে না। তবু কি Ω(n log n) সত্য? আর নিম্নসীমা আসলে কোন মডেলে?
            

                
সূক্ষ্ম কিন্তু গুরুত্বপূর্ণ প্রশ্ন। অংশ ৮-এর reduction-এ পরাবৃত্তের সব বিন্দুই hull-এ — কোণের সেট চাইলে উত্তর “সবগুলো”, কোনো sort হলো না! তাই ক্রমসহ hull-এর জন্য যুক্তিটি ঠিক, কিন্তু শুধু সেটের জন্য অন্য যুক্তি লাগে। ১৯৮১ সালে Andrew Yao দেখান যে শুধু কোণের সেট খুঁজতেও Ω(n log n) লাগে — একটি “quadratic decision tree” মডেলে, যেখানে প্রতিটি ধাপে ইনপুটের ওপর দ্বিঘাত বহুপদীর চিহ্ন পরীক্ষা করা যায় (orientation ঠিক এমন একটি পরীক্ষা). ১৯৮৩ সালে Michael Ben-Or আরও সাধারণ “algebraic decision tree” মডেলে element uniqueness-সহ অনেক সমস্যার Ω(n log n) প্রমাণ করেন, যা থেকে closest pair-এর মতো সমস্যার নিম্নসীমা আসে।

                
এই মডেলগুলোর বাইরে গেলে ছবি বদলায়। পর্ব ২৪-এ দেখেছেন, পূর্ণসংখ্যা হলে radix sort তুলনা-নিম্নসীমা ভাঙে, কারণ এটি সংখ্যার bit সরাসরি ব্যবহার করে। একইভাবে word-RAM মডেলে, যেখানে পূর্ণসংখ্যার bit-স্তরের কাজ অনুমোদিত, কিছু জ্যামিতিক সমস্যার জন্য n log n-এর চেয়ে দ্রুত পদ্ধতি নিয়ে গবেষণা আছে (যেমন ২০০০-এর দশকে Timothy Chan ও Mihai Pătraşcu-র কাজ). কিন্তু reduction উল্টো দিকেও খাটে: hull দ্রুত হলে sort-ও তত দ্রুত — তাই hull কখনো ওই মডেলের সেরা integer sort-এর চেয়ে দ্রুত হতে পারবে না।

                
Reduction-এর ভাবনাটি পর্ব ৬৪-এর P বনাম NP-তে কেন্দ্রীয় হয়ে উঠবে: “A-কে B-তে রূপান্তর করা যায়” মানে “B অন্তত A-এর মতো কঠিন”. এখানে আমরা দেখলাম একই যুক্তি polynomial সময়ের ভেতরের সূক্ষ্ম পার্থক্যেও (n বনাম n log n) কাজ করে।

                
মূল উপলব্ধি: নিম্নসীমা সবসময় একটি গণনা-মডেলের ভেতরে সত্য, আর কী আউটপুট চাওয়া হচ্ছে (ক্রমসহ নাকি শুধু সেট) সেটিও প্রমাণ বদলে দেয়। “এর চেয়ে দ্রুত অসম্ভব” শুনলে জিজ্ঞেস করুন — কোন মডেলে, কোন আউটপুটে?

            

        


        

            প্র ০৫Convex hull-এর পরের ধাপ কী? Voronoi diagram, Delaunay triangulation আর ত্রিমাত্রিক hull কোথায় কাজে লাগে?
            

                
শহরে কয়েকটি হাসপাতাল আছে। প্রতিটি হাসপাতালের “এলাকা” কোনটি — অর্থাৎ শহরের কোন অংশের মানুষের কাছে এই হাসপাতালটিই সবচেয়ে কাছে? এই বিভাজনই Voronoi diagram. ১৮৫৪ সালে লন্ডনে কলেরার প্রাদুর্ভাবের সময় John Snow মৃত্যুগুলোকে মানচিত্রে বসিয়ে কোন পানির পাম্পের কাছের এলাকায় মৃত্যু বেশি তা দেখান — ধারণাটি পরে Voronoi ছবির সাথে তুলনা করা হয়, আর এটি মহামারীবিদ্যার একটি ক্লাসিক গল্প। Shamos ও Hoey ১৯৭৫ সালে Voronoi diagram O(n log n)-এ বানানোর divide and conquer অ্যালগরিদম দেন; ১৯৮৬ সালে Steven Fortune একটি সুন্দর sweep line পদ্ধতি দেন, যা আজ সবচেয়ে বেশি পড়ানো হয়।

                
Voronoi-র “দ্বৈত” (dual) রূপ Delaunay triangulation — রুশ গণিতবিদ Boris Delaunay ১৯৩৪ সালে বর্ণনা করেন: পাশাপাশি Voronoi এলাকার কেন্দ্রগুলো জুড়ে ত্রিভুজ। এর বিশেষত্ব — কোনো ত্রিভুজের পরিবৃত্তের ভেতরে অন্য কোনো বিন্দু থাকে না, তাই সরু “কাঁটার মতো” ত্রিভুজ যতটা সম্ভব এড়ানো যায়। ভূমির উচ্চতা-মানচিত্র (terrain), finite element পদ্ধতিতে সেতু বা ভবনের চাপ হিসাব, আর গেমের 3D মডেল — সবখানে এই ত্রিভুজ-জাল। একটি সুন্দর সংযোগ: দুই মাত্রার বিন্দু (x, y)-কে (x, y, x² + y²)-এ তুললে, সেই ত্রিমাত্রিক বিন্দুগুলোর নিচের convex hull-এর মুখগুলোই Delaunay ত্রিভুজ — অংশ ৮-এর পরাবৃত্তের কৌশলের এক মাত্রা ওপরের রূপ।

                
ত্রিমাত্রিক convex hull-ও O(n log n)-এ সম্ভব — Preparata ও Hong ১৯৭৭ সালে divide and conquer দিয়ে দেখান। বাস্তবে বহুল ব্যবহৃত Qhull লাইব্রেরি (Quickhull পদ্ধতি) MATLAB, SciPy-সহ অনেক জায়গায় hull, Delaunay আর Voronoi হিসাব করে। চার বা আরও বেশি মাত্রায় hull-এর আকারই বিশাল হতে পারে, তাই সেখানে প্রশ্ন বদলে যায়।

                
মূল উপলব্ধি: Convex hull একটি দরজা: একই orientation primitive আর sweep বা divide and conquer কৌশল দিয়েই Voronoi, Delaunay আর উঁচু মাত্রার hull — আর একটি মাত্রা বাড়িয়ে অনেক সমস্যাকে hull-এ রূপান্তর করা যায়।

            

        

    


    
    

        
 অনুশীলন

        
খাতা-কলম নিয়ে বসুন। প্রথম দুটি হাতে trace, তৃতীয়টি বিশ্লেষণ, শেষটি কোড লেখা।

        
    
            
  1. 
                হাতে trace করুন: বিন্দু (0,0), (2,1), (4,0), (3,2), (4,4), (1,3), (2,2)-এ Andrew-এর monotone chain চালান। সাজানো ক্রম, lower hull, upper hull আর চূড়ান্ত hull লিখুন। কোন বিন্দু কেন বাদ পড়ল?
                
    
                    
    সাজানো: (0,0) (1,3) (2,1) (2,2) (3,2) (4,0) (4,4). Lower: (0,0), (1,3) ঢোকে; (2,1): orient((0,0),(1,3),(2,1)) = 1·1 − 3·2 = −৫ → (1,3) বাদ; (2,2): orient((0,0),(2,1),(2,2)) = ২ → ঢোকে; (3,2): orient((2,1),(2,2),(3,2)) = −১ → (2,2) বাদ, orient((0,0),(2,1),(3,2)) = ১ → ঢোকে; (4,0): (3,2) বাদ (−৩), (2,1) বাদ (−৪), ঢোকে; (4,4): orient((0,0),(4,0),(4,4)) = ১৬ → ঢোকে। Lower = (0,0) (4,0) (4,4). Upper (ডান থেকে বাঁয়ে, (4,0) থেকে শুরু): (4,0) ঢোকে, কিন্তু (3,2) এলে orient((4,4),(4,0),(3,2)) = −৪ → ওপরের শিকল থেকে বাদ (নিচের শিকলে সে থাকে); (3,2) ঢোকে; (2,2) এসে (3,2) বাদ (−২); (2,2) ঢোকে, (2,1) ঢোকে (২); (1,3) এসে (2,1) বাদ (−১), (2,2)-ও বাদ (−৪); (1,3) ঢোকে; শেষে (0,0): orient((4,4),(1,3),(0,0)) = ৮ → থাকে। চূড়ান্ত hull (CCW): (0,0) (4,0) (4,4) (1,3). (2,1), (2,2), (3,2) ভেতরে। shoelace-এ 2A = 0 + 16 + 8 + 0 = ২৪, A = ১২.
    
                
    
            
    2. 
            
  2. 
                হাতে trace করুন: ত্রিভুজ (0,0), (5,1), (2,4)-এর ক্ষেত্রফল shoelace দিয়ে বের করুন। তারপর Pick-এর উপপাদ্য দিয়ে ভেতরের lattice point গুনুন।
                
    
                    
    পদ: 0·1 − 5·0 = ০; 5·4 − 2·1 = ১৮; 2·0 − 0·4 = ০. 2A = ১৮, A = ৯ (ধনাত্মক — কোণগুলো counter-clockwise). সীমানা: gcd(5,1) = ১, gcd(3,3) = ৩, gcd(2,4) = ২ → B = ৬. Pick: I = A − B/2 + 1 = 9 − 3 + 1 = ৭. যাচাই করতে গ্রাফ কাগজে আঁকুন: (1,1), (2,1), (3,1), (4,1), (2,2), (3,2), (2,3) — সাতটি।
    
                
    
            
    3. 
            
  3. 
                বিশ্লেষণ: (ক) n টি বিন্দু একটি বৃত্তের ওপর সমান দূরত্বে থাকলে Jarvis march আর monotone chain-এর সময় কত? (খ) n = ১০ লাখ বিন্দু, কিন্তু সব একটি বর্গক্ষেত্রের ভেতরে আর তার চার কোণ ইনপুটে আছে — কোনটি দ্রুত? (গ) Hull-এর ক্রম জানার পর বহুভুজটি convex কি না যাচাই করতে কত সময় লাগে?
                
    
                    
    (ক) সব বিন্দু hull-এ, h = n: Jarvis Θ(n²), monotone chain Θ(n log n). (খ) Hull শুধু চারটি কোণ, h = ৪: Jarvis Θ(4n) = Θ(n), monotone chain Θ(n log n) (sort-এর জন্য) — Jarvis দ্রুত, যদিও বাস্তবে sort এত দ্রুত যে পার্থক্য ছোট। (গ) Θ(n): প্রতিটি পরপর তিনটি কোণের orientation একই চিহ্নের কি না দেখুন (আর মোট একবারই ঘোরে কি না — নিজেকে কাটা “তারা” বাদ দিতে).
    
                
    
            
    4. 
            
  4. 
                কোড লিখুন: C++-এ int inside(const vector<P>& poly, P q) লিখুন: সীমানায় হলে 0, ভেতরে 1, বাইরে −1. শুধু পূর্ণসংখ্যা — ভাগ নয়। অংশ ৬-এর Q(3,4), R(1,1), S(1,2) আর সীমানার বিন্দু (6,3) দিয়ে পরীক্ষা করুন।
                
    
                    
    int inside(const vector<P>& poly, P q) {          // 0 boundary, 1 inside, -1 outside
    bool in = false; size_t n = poly.size();
    for (size_t i = 0; i < n; ++i) {
        P a = poly[i], b = poly[(i + 1) % n];
        if (cross(a, b, q) == 0 && onSeg(a, b, q)) return 0;      // on an edge
        if ((a.y > q.y) != (b.y > q.y)) {                         // half-open rule
            // crossing x > q.x  <=>  q is left of a->b when b is above a
            ll s = cross(a, b, q);
            if (b.y > a.y ? s > 0 : s < 0) in = !in;
        }
    }
    return in ? 1 : -1;
}
// expected: Q(3,4) -> -1, R(1,1) -> 1, S(1,2) -> 1, (6,3) -> 0
    
                    
    কৌশল: “ছেদবিন্দুর x > q.x” মানে q রশ্মি-রেখায় বাহুটির বাঁয়ে। বাহু ওপরের দিকে গেলে (b.y > a.y) সেটি orient(a, b, q) > 0, নিচের দিকে গেলে < 0. ভাগ ছাড়া, তাই নির্ভুল। প্রতি প্রশ্নে Θ(n), জায়গা Θ(1). cross আর onSeg অংশ ৫-এর প্রোগ্রাম থেকে।
    
                
    
            
    5. 
        

    


    
    

        
 নিজেকে যাচাই করুন

        
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।


        

            
ক্রমAndrew-এর monotone chain convex hull-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

            
    
                
  1. বিন্দুগুলো (x, তারপর y) অনুযায়ী সাজানো আর ডুপ্লিকেট বাদ
    2. 
                
  2. বাঁ থেকে ডানে গিয়ে stack-এ lower hull — ডান মোড় বা একই রেখা হলে pop
    3. 
                
  3. ডান থেকে বাঁয়ে ফিরে upper hull — lower অংশকে না ছুঁয়ে একই নিয়মে pop
    4. 
                
  4. শেষে দ্বিতীয়বার ঢোকা প্রথম বিন্দুটি বাদ দেওয়া
    5. 
                
  5. Shoelace দিয়ে hull-এর ক্ষেত্রফল বা অন্য হিসাব
    6. 
            

        


        

            
o = (0, 0), a = (4, 0), b = (2, −3) হলে orient(o, a, b) = (a − o) × (b − o)-এর মান আর অর্থ কী?

            
    
                
  • 12, বাঁ মোড়
    • 
                
  • −12, ডান মোড়
    • 
                
  • 0, একই রেখা
    • 
                
  • −12, বাঁ মোড়
    • 
            

        


        

            
কোণ (0, 0), (4, 0), (0, 3) বিশিষ্ট ত্রিভুজের ক্ষেত্রফল shoelace সূত্রে কত?

            
    
                
  • 12
    • 
                
  • 7
    • 
                
  • 6
    • 
                
  • −6
    • 
            

        


        

            
n টি বিন্দুর convex hull Andrew-এর monotone chain দিয়ে বের করতে মোট সময় কত?

            
    
                
  • Θ(n log n)
    • 
                
  • Θ(n)
    • 
                
  • Θ(n²)
    • 
                
  • Θ(nh), h = hull-এর কোণের সংখ্যা
    • 
            

        


        

            
n টি বিন্দু একটি বৃত্তের ওপর থাকলে gift wrapping (Jarvis march) convex hull-এর সময় কত?

            
    
                
  • Θ(n log n)
    • 
                
  • Θ(n)
    • 
                
  • Θ(n log h)
    • 
                
  • Θ(n²)
    • 
            

        


        

            
Ray casting দিয়ে point in polygon পরীক্ষায় বিন্দু থেকে ডানের রশ্মি সীমানাকে ৩ বার পার হলে বিন্দুটি কোথায়?

            
    
                
  • বাইরে
    • 
                
  • ভেতরে
    • 
                
  • ঠিক সীমানার ওপর
    • 
                
  • বলা যায় না, বহুভুজ convex কি না জানতে হবে
    • 
            

        


        

            
Convex hull-এর Ω(n log n) নিম্নসীমার প্রচলিত প্রমাণে কোন সমস্যা থেকে reduction করা হয়?

            
    
                
  • গ্রাফে shortest path
    • 
                
  • Binary search
    • 
                
  • তুলনা-ভিত্তিক sorting
    • 
                
  • Matrix গুণ
    • 
            

        


        

    


    
    

        
 শব্দকোষ

        
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

        

    


    
    

        
 মনে রাখুন

        
    
            
  1. Orientation সবকিছুর ভিত্তি: (a − o) × (b − o)-এর চিহ্ন — বাঁ (+), ডান (−), একই রেখা (0); মান = ত্রিভুজের দ্বিগুণ ক্ষেত্রফল।
    2. 
            
  2. পূর্ণসংখ্যার কোঅর্ডিনেটে সব হিসাব long long-এ — ভাগ, বর্গমূল আর atan2 ছাড়া; দশমিকে ε সাবধানে।
    3. 
            
  3. রেখাংশের ছেদ = দুই জোড়া বিপরীত চিহ্ন, নয়তো শূন্য orientation + বাক্সের ভেতরে; collinear ক্ষেত্র ভুলবেন না।
    4. 
            
  4. Shoelace Θ(n)-এ বহুভুজের ক্ষেত্রফল, Pick A = I + B/2 − 1, ray casting-এ বিজোড় = ভেতরে (অর্ধ-খোলা নিয়মে কোণ).
    5. 
            
  5. Convex hull Θ(n log n) — sort + stack (Graham, Andrew), Jarvis Θ(nh); sort থেকে reduction-এ Ω(n log n).
    6. 
        

        
পরের পর্বে: এ পর্যন্ত যত সমস্যা দেখেছেন, সবই polynomial সময়ে সমাধান হয়েছে। কিন্তু কিছু সমস্যার উত্তর যাচাই করা সহজ, অথচ খুঁজে পাওয়ার দ্রুত পদ্ধতি কেউ জানে না — P বনাম NP, NP-complete আর reduction, পর্ব ৬৪.

    


    
    

        
 আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

        
    


    

        
    


    
    

        

            এই পর্বটি শেয়ার করুন:
            
            
            
            
            
        

         এই পর্বে ভুল পেয়েছেন? জানান