কনটেন্টে যান

117 — Line Intersection Basic

116-এ orientation শিখেছ — এবার তার প্রথম বড় ফসল তুলব। দুটো line segment কাটে কি না, সেটা বের করতে অনেকে line equation মেলাতে বসে যায় (আর float-এ ডুবে মরে)। আমরা সেদিকেই যাব না। শুধু চারটা orientation চালিয়ে প্রশ্নটা মীমাংসা করব — কোনো ভাগ, কোনো float ছাড়াই। আর সবচেয়ে গুরুত্বপূর্ণ — collinear special case-টা যত্ন করে ধরব, কারণ এখানেই বেশিরভাগ WA লুকিয়ে থাকে।

Problem link ও উৎস

  • Original source: CP-Algorithms — geometry (segment intersection)
  • Platform: CP-Algorithms geometry — https://cp-algorithms.com/geometry/check-segments-intersection.html
  • Topic: Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
  • Difficulty: Medium
  • Pattern: orientation test
  • Basic idea inherited from: 116 — Orientation of Three Points (চারবার orientation চালিয়ে কাটাকাটি)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

দুটো line segment দেওয়া — একটা P–Q, আরেকটা R–S (চারটা endpoint)। বলতে হবে এই দুটো segment পরস্পরকে কাটে (intersect) কি না — মানে তাদের অন্তত একটা সাধারণ point আছে কি না।

মনে রেখো — এটা segment (দুই প্রান্তে সীমিত), অসীম line নয়। দুটো অসীম line প্রায় সবসময়ই কোথাও কাটে (সমান্তরাল না হলে), কিন্তু segment দুটো ছোট — তারা হয়তো একে অপরের নাগালেই পৌঁছায় না।

Input ও output

উদাহরণ
P       Q       R        S         intersect?
-----------------------------------------------------
(0,0)   (4,4)   (0,4)    (4,0)     True   (X-এর মতো ক্রস, মাঝে কাটে)
(0,0)   (4,0)   (2,1)    (2,5)     False  (RS উপরে, ছোঁয় না)
(0,0)   (4,4)   (5,5)    (6,6)     False  (একই লাইনে, কিন্তু ফাঁক)
(0,0)   (4,4)   (2,2)    (6,6)     True   (collinear, overlap করে)
(0,0)   (4,0)   (4,0)    (8,0)     True   (শুধু এক endpoint ছোঁয় -> touch)
(0,0)   (4,0)   (2,0)    (2,3)     True   (T-জংশন, endpoint segment-এ)

খেয়াল করো collinear case দুটো: একই লাইনে থেকেও কেউ overlap করে (True), কেউ ফাঁক রেখে দাঁড়িয়ে (False)। আর শুধু এক প্রান্ত ছোঁয়াও (touch) এখানে intersection ধরছি — এই সংজ্ঞাটা problem ভেদে বদলাতে পারে, তাই খেয়াল রেখো।

চেনা উদাহরণে বোঝা

ভাবো মাটিতে দুটো লাঠি ফেলা — একটা PQ, একটা RS। তুমি জানতে চাও এরা একে অপরের উপর দিয়ে গেছে কি না (X-এর মতো ক্রস করেছে)।

চোখে দেখার বদলে চালাকি: PQ লাঠির বরাবর দাঁড়িয়ে দেখো — RS লাঠির দুই মাথা (R আর S) কি তোমার বাঁ আর ডান, দুই দিকে আলাদা? যদি দুই মাথাই একই পাশে থাকে, তাহলে RS লাঠিটা PQ-কে পেরোতেই পারেনি। এবার RS-এর বরাবর দাঁড়িয়ে একই প্রশ্ন PQ-র দুই মাথা নিয়ে। দুই পরীক্ষাতেই "দুই পাশে" হলে তবেই লাঠি দুটো ক্রস করেছে। আর যদি কোনো মাথা ঠিক অন্য লাঠির গায়ে পড়ে (orientation 0) — তখন আলাদা করে দেখতে হয় সেটা লাঠির দৈর্ঘ্যের ভেতরে নাকি বাইরে।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

116-এ আমরা orientation(a, b, c) বানিয়েছি — তিন point-এর বাঁক CCW/CW/collinear। তখন বলেছিলাম "117 আর 120 এটা ছাড়া অচল" — এখানেই সেই দাবি প্রমাণ।

এই problem আসলে orientation function-কে চারবার চালানো ছাড়া আর কিছুই না। যদি 116 পরিষ্কার থাকে, তাহলে আজকের কাজ শুধু সেই চারটা ফলাফল সাজানো — কোন combination মানে কাটে, কোনটা মানে কাটে না। মূল algorithm এক লাইনের; বাকিটা case সামলানো। তাই 116-কে ভালো করে গেঁথে নিয়ে এসো।

ভেতরের অঙ্ক

মূল idea orientation দিয়ে "দুই পাশে আছে কি না" পরীক্ষা। দুটো segment সাধারণভাবে কাটে যদি:

উদাহরণ
R আর S, PQ লাইনের দুই বিপরীত পাশে থাকে
   AND
P আর Q, RS লাইনের দুই বিপরীত পাশে থাকে

"দুই পাশে" মানে orientation চিহ্ন আলাদা:

উদাহরণ
o1 = orientation(P, Q, R)
o2 = orientation(P, Q, S)
o3 = orientation(R, S, P)
o4 = orientation(R, S, Q)

general case: o1 != o2  AND  o3 != o4  -> কাটে

আর যদি কোনো orientation 0 হয় (মানে কোনো endpoint অন্য segment-এর লাইনে), তখন collinear special case — দেখতে হয় সেই endpoint টা অন্য segment-এর সীমার (bounding box) ভেতরে পড়ে কি না।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

orientation না জানলে, প্রথমে দুটো line-এর equation বানিয়ে কাটার point বের করার চেষ্টা মাথায় আসে:

Python
def intersect_bad(p, q, r, s):
    # দুটো line ax+by=c বানিয়ে কাটার point (x, y) বের করি
    a1, b1 = q[1]-p[1], p[0]-q[0]
    c1 = a1*p[0] + b1*p[1]
    a2, b2 = s[1]-r[1], r[0]-s[0]
    c2 = a2*r[0] + b2*r[1]
    det = a1*b2 - a2*b1
    if det == 0:
        return False              # সমান্তরাল (collinear handle হয়নি!)
    x = (b2*c1 - b1*c2) / det     # ভাগ -> float
    y = (a1*c2 - a2*c1) / det
    # (x,y) কি দুই segment-এর ভেতরে? float তুলনা...
    return (min(p[0],q[0]) <= x <= max(p[0],q[0]) and
            min(r[0],s[0]) <= x <= max(r[0],s[0]))

এটা সাধারণ case-এ কাজ করে, কিন্তু det দিয়ে ভাগ (float!), কাটার point float-এ এসে "segment-এর ভেতরে কি না" তুলনাও float — আর collinear case পুরো এড়িয়ে গেছে।

কোথায় বেশি কাজ হতে পারে

"slow" নয়, বরং float-ভঙ্গুর আর অসম্পূর্ণ:

উদাহরণ
equation পথ:  det দিয়ে ভাগ -> কাটার point (x, y) float
              -> "segment-এর ভেতরে?" float তুলনা -> প্রান্তে ভুল
              -> collinear (det == 0) আলাদা করে ভাবতেই হয়, নাহলে ভুল

orientation পথ:  চারটা integer cross product-এর চিহ্ন
                 -> কাটার point বের করারই দরকার নেই!
                 -> collinear-এ bounding box (integer তুলনা)

মূল কথা — আমরা শুধু জানতে চাই "কাটে কি না", কাটার জায়গা কোথায় নয়। তাই কাটার point বের করতে ভাগ করাই অপচয়। orientation চিহ্নই উত্তর দেয়, integer-এ, নিখুঁতভাবে।

আরও ভালোভাবে ভাবা

মূল insight: "কাটে কি না" = orientation-এর চিহ্ন মেলানো — কাটার point লাগে না। চারটা orientation:

Python
def segments_intersect(p, q, r, s):
    o1 = orientation(p, q, r)
    o2 = orientation(p, q, s)
    o3 = orientation(r, s, p)
    o4 = orientation(r, s, q)
    if o1 != o2 and o3 != o4:      # general case: দুই পাশে
        return True
    # collinear special cases: কোনো endpoint অন্য segment-এর উপর?
    if o1 == 0 and on_segment(p, q, r): return True
    if o2 == 0 and on_segment(p, q, s): return True
    if o3 == 0 and on_segment(r, s, p): return True
    if o4 == 0 and on_segment(r, s, q): return True
    return False

on_segment(a, b, c) চেক করে — c, AB-র উপর (collinear ধরে নিয়ে, তার bounding box-এ পড়ে কি না)। সব integer, কোনো ভাগ নেই।

ভাবনার পরিবর্তন

আসল "আহা!": কাটাকাটি জানতে কাটার বিন্দু খোঁজার দরকার নেই — শুধু "প্রতিটা segment অন্যটার endpoint দুটোকে দুই পাশে রাখে কি না" — দুটো orientation চিহ্নের মিল-অমিল।

আর দ্বিতীয় গুরুত্বপূর্ণ tweak — collinear special case-ই আসল পরীক্ষা। general case দুই লাইনের; কিন্তু WA-র 90% আসে যখন endpoint গুলো এক লাইনে পড়ে আর তুমি bounding box চেক ভুলে যাও। তাই চারটা o == 0-এর case আর on_segment — এগুলো অবহেলা কোরো না।

ছবিতে বোঝা

general case — endpoint গুলো দুই পাশে থাকলে কাটে:

উদাহরণ
কাটে (cross):              কাটে না (একই পাশে):
        R                        R   S
        |                         \ /
P ------+------ Q          P ------X------ Q   (X এখানে শুধু ছবির জন্য;
        |                                       আসলে R,S দুজনেই উপরে)
        S
o1=orient(P,Q,R) = +1      o1 = +1
o2=orient(P,Q,S) = -1      o2 = +1
o1 != o2 ✓ (দুই পাশে)      o1 == o2 ✗ (একই পাশে -> কাটে না)

collinear special case:
P ---- Q ---- R ---- S      P ---- Q   R ---- S
   (Q,R মাঝে overlap)          (ফাঁক -> কাটে না)
সব orientation 0 -> bounding box overlap দেখো

লক্ষ করো — general case-এ শুধু চিহ্ন আলাদা কি না দেখি; কিন্তু সব orientation 0 হলে (এক লাইনে) আলাদা করে দেখতে হয় segment দুটো সত্যিই ছুঁয়েছে নাকি মাঝে ফাঁক।

ছোট input-এ ধাপে ধাপে

চলো P=(0,0), Q=(4,4), R=(0,4), S=(4,0) — X-এর মতো ক্রস:

  1. শুরু: PQ হলো y=x রেখার অংশ, RS হলো y=−x+4-এর অংশ
  2. o1 = orientation(P, Q, R) = orientation((0,0),(4,4),(0,4)) val = (4)(4) − (4)(0) = 16 > 0 → +1
  3. o2 = orientation(P, Q, S) = orientation((0,0),(4,4),(4,0)) val = (4)(0) − (4)(4) = −16 < 0 → −1
  4. o1 != o2? +1 != −1? হ্যাঁ → R, S দুই পাশে ✓
  5. o3 = orientation(R, S, P) = orientation((0,4),(4,0),(0,0)) val = (4)(−4) − (−4)(0) = −16 → −1
  6. o4 = orientation(R, S, Q) = orientation((0,4),(4,0),(4,4)) val = (4)(0) − (−4)(4) = 16 → +1
  7. o3 != o4? −1 != +1? হ্যাঁ → P, Q দুই পাশে ✓
  8. দুটোই হ্যাঁ → কাটে (True) ✓

collinear উদাহরণ P=(0,0) Q=(4,4) R=(5,5) S=(6,6): সব orientation 0, কিন্তু on_segment সব fail (R,S সবাই PQ-র বাইরে) → ফাঁক → False।

কোড ও ব্যাখ্যা

Python

Python
def orientation(a, b, c):
    """+1 = CCW, -1 = CW, 0 = collinear (116 থেকে)।"""
    val = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
    if val > 0:
        return 1
    if val < 0:
        return -1
    return 0


def on_segment(a, b, c):
    """c collinear ধরে নিয়ে: c কি AB segment-এর bounding box-এ পড়ে?"""
    return (min(a[0], b[0]) <= c[0] <= max(a[0], b[0]) and
            min(a[1], b[1]) <= c[1] <= max(a[1], b[1]))


def segments_intersect(p, q, r, s):
    """PQ আর RS segment কাটে কি না (touch-ও কাটা ধরা হচ্ছে)।"""
    o1 = orientation(p, q, r)
    o2 = orientation(p, q, s)
    o3 = orientation(r, s, p)
    o4 = orientation(r, s, q)

    if o1 != o2 and o3 != o4:           # general case
        return True

    # collinear / endpoint-touch special cases
    if o1 == 0 and on_segment(p, q, r):
        return True
    if o2 == 0 and on_segment(p, q, s):
        return True
    if o3 == 0 and on_segment(r, s, p):
        return True
    if o4 == 0 and on_segment(r, s, q):
        return True

    return False


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert segments_intersect((0, 0), (4, 4), (0, 4), (4, 0)) is True    # X ক্রস
assert segments_intersect((0, 0), (4, 0), (2, 1), (2, 5)) is False   # ছোঁয় না
assert segments_intersect((0, 0), (4, 4), (5, 5), (6, 6)) is False   # collinear, ফাঁক
assert segments_intersect((0, 0), (4, 4), (2, 2), (6, 6)) is True    # collinear, overlap
assert segments_intersect((0, 0), (4, 0), (4, 0), (8, 0)) is True    # endpoint touch
assert segments_intersect((0, 0), (4, 0), (2, 0), (2, 3)) is True    # T-জংশন
assert segments_intersect((0, 0), (1, 1), (2, 2), (3, 3)) is False   # collinear, ফাঁক
assert segments_intersect((0, 0), (5, 5), (1, 1), (2, 2)) is True    # ভেতরে ঢুকে আছে

print(segments_intersect((0, 0), (4, 4), (0, 4), (4, 0)))   # True
print(segments_intersect((0, 0), (4, 0), (2, 1), (2, 5)))   # False
print(segments_intersect((0, 0), (4, 4), (2, 2), (6, 6)))   # True
print("সব test pass!")

কোডের প্রতিটি অংশ

উদাহরণ
def on_segment(a, b, c):
    return (min(a[0], b[0]) <= c[0] <= max(a[0], b[0]) and
            min(a[1], b[1]) <= c[1] <= max(a[1], b[1]))

c যে AB-র সাথে collinear সেটা ধরে নিয়ে — শুধু দেখি c-র x আর y, AB-র bounding box-এর ভেতরে কি না। collinear হলে এটাই বলে দেয় c segment-এর উপর আছে নাকি বাড়ানো লাইনের বাইরে।

উদাহরণ
    o1 = orientation(p, q, r)
    ...
    if o1 != o2 and o3 != o4:
        return True

চারটা orientation। general case — R,S যদি PQ-র দুই পাশে (o1 != o2) এবং P,Q যদি RS-র দুই পাশে (o3 != o4) — তবেই কাটে।

উদাহরণ
    if o1 == 0 and on_segment(p, q, r):
        return True
    ...

কোনো orientation 0 মানে সেই endpoint অন্য segment-এর লাইনে; তখন on_segment দিয়ে দেখি সে আসলে segment-এর দৈর্ঘ্যের ভেতরে পড়ে কি না। চারটা endpoint-এর জন্য চারটা চেক।

বাকি assert লাইনগুলো general, collinear-overlap, collinear-gap, touch, T-junction — সব case যাচাই করছে; সব মিললে শেষে সব test pass!।

Output মিলিয়ে দেখা

চালালে যা ছাপবে:

উদাহরণ
True
False
True
সব test pass!

প্রথম: (0,0)-(4,4) আর (0,4)-(4,0) X-এর মতো ক্রস → True। দ্বিতীয়: horizontal segment আর তার উপরের vertical segment ছোঁয় না → False। তৃতীয়: একই লাইনে দুটো segment overlap করে → True। তার আগের সব assert চুপচাপ pass করেছে। সবশেষে সব test pass!।

খরচ ও সাধারণ ভুল

সময়

O(1) — চারটা orientation (প্রতিটা O(1)) আর কয়েকটা bounding box চেক। input-নির্বিশেষে ধ্রুবক।

অতিরিক্ত জায়গা

O(1) — শুধু চারটা orientation মান (o1–o4)। কোনো বাড়তি data structure নেই।

যে ভুলগুলো এড়াতে হবে

  1. collinear special case ভুলে যাওয়া — শুধু general case (o1!=o2 and o3!=o4) লিখলে এক লাইনে থাকা overlap/touch ধরা পড়বে না — এটাই WA-র প্রধান উৎস।
  2. on_segment-এ collinearity ধরে না নেওয়া — on_segment শুধু তখনই অর্থপূর্ণ যখন সংশ্লিষ্ট orientation 0; নাহলে bounding box-এ থাকা ≠ segment-এ থাকা।
  3. touch নিয়ে সংজ্ঞা না পড়া — শুধু এক প্রান্ত ছুঁলে intersection ধরা হবে কি না, problem-ভেদে আলাদা; এখানে আমরা touch-কে True ধরেছি।
  4. কাটার point বের করতে যাওয়া — দরকার নেই; "কাটে কি না"-তে point খুঁজলে অকারণ float আর জটিলতা।
  5. orientation চিহ্ন convention — 116-এর মতোই; screen coordinate-এ চিহ্ন উল্টো হলেও "দুই পাশে" (চিহ্ন আলাদা) test অপরিবর্তিত থাকে — সেটা সুবিধা।

শেখা ও পরের অনুশীলন

এই ধারণার পরের অনুশীলন

  • CSES — Line Segment Intersection (https://cses.fi/problemset/task/2190) — ঠিক এই segment intersection test, collinear সহ সব case।
  • CSES — Polygon Lattice Points / point-in-polygon ray casting — segment intersection-এর ভিত্তিতে ভেতরে/বাইরে নির্ণয়।
  • 120 (Convex Hull Intro) — এই repo-রই পরের Hard, যেখানে একই orientation দিয়ে সীমানা গড়া হবে।

কৌশলটি মনে রাখুন

Segment intersection via orientation — চারটা orientation চিহ্ন মিলিয়ে "দুই পাশে কি না"; কাটার point লাগে না, integer-এ নিখুঁত। বড় শিক্ষা: general case সহজ (দুই লাইন); আসল যত্ন চাই collinear special case-এ (bounding box overlap) — সেখানেই বাগ লুকোয়।

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

ভবিষ্যতের আমাকে এক লাইনে: "segment কাটে কি না = চারটা orientation; o1≠o2 and o3≠o4 হলে general কাটা; কোনো o==0 হলে on_segment দিয়ে collinear case। কাটার point খুঁজো না — শুধু চিহ্ন। আর collinear case ভুলো না, ওখানেই WA।"

পরের ধাপ → 118 — Rectangle Overlap (এবার interval logic — interview-ঘরানা)। শিকড় → 116 — Orientation of Three Points। সম্পর্কিত → 120 — Convex Hull Intro।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।