Skip to content

Geometry -> Segment Intersection

Robust orientation tests, on-segment handling, and degenerate cases for line and segment intersection.

  • Topic slug: geometry/segment-intersection
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 2
  • Repo companion pages: 2
  • Curated external problems: 5

Microtopics

  • orientation-test
  • on-segment
  • collinear-overlap
  • degeneracies
  • integer-robustness
  • line-vs-segment

Learning Sources

Source Type
cp-algorithms segment intersection Reference
Topcoder geometry concepts part 2 Essay / Blog
Princeton geometric primitives Course

Practice Sources

Source Type
CSES Line Segment Intersection Practice
CSES Point in Polygon Practice
CSES Point Location Test Practice

Repo Companion Material

Material Type
Geometry cheatsheet quick reference
Templates overview template guide

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Line Segment Intersection CSES Medium Orientation Case Analysis Orientation Tests; Segment Bounding Boxes Robust Geometry; Ccw; Overlap; Touching The canonical segment-intersection decision problem.
Line Segments Trace I CSES Medium Sweep-Line - - Envelope; Max-Point; Scan A line-segment scan problem where sweep-style reasoning is natural.
Line Segments Trace II CSES Hard Sweep-Line - - Envelope; Comparisons; Scan The harder companion to Trace I with similar line-sweep flavor.

Challenge

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Area of Rectangles CSES Hard - Sweep-Line; Coordinate Compression Segment Events; Range Coverage Sweep Line; Interval Coverage; Rectangles The canonical rectangle-union sweep-line problem.
Intersection Points CSES Hard Sweep-Line, Intersection-Counting Sweep-Line Event Sorting; Balanced Tree / Fenwick Orthogonal Segments; Horizontal-Vertical; Events; Count Counts many segment intersections with a line-sweep approach.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
LINESEGMENTINTERSECTION Line Segment Intersection primary easy orientation test; on segment inclusion; collinear overlap handling Note Code
POINTINPOLYGON Point in Polygon secondary medium ray casting parity; boundary classification; on segment test Note Code

Regeneration

python3 scripts/generate_problem_catalog.py