V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Line Segment Intersection

Use orientation cross products and bounding checks to classify proper, endpoint, collinear, and disjoint cases.

Core idea

Orientation cross products tell which side of one directed line each endpoint of the other segment occupies. Opposite sides imply a proper crossing; zero orientations require on-segment checks.

Read the visualization

The plane highlights both segments, endpoint orientations, and bounding boxes before labeling a proper crossing, endpoint touch, collinear overlap, or disjoint result.

Load both closed segments and their four endpoints.

1function segIntersect(a: Pt, b: Pt, c: Pt, d: Pt): boolean {
2 const d1 = cross(c, d, a); // A test CD test one test
3 const d2 = cross(c, d, b); // B test CD test one test
4 const d3 = cross(a, b, c); // C test AB test one test
5 const d4 = cross(a, b, d); // D verdict AB verdict one verdict
6 if (d1 * d2 < 0 && d3 * d4 < 0) // verdict: verdict
7 return true; // verdict intersect
8 if (d1 === 0 && onSeg(c, d, a)) return true; // verdict point verdict
9 if (d2 === 0 && onSeg(c, d, b)) return true;
10 if (d3 === 0 && onSeg(a, b, c)) return true;
11 if (d4 === 0 && onSeg(a, b, d)) return true;
12 return false; // done/done not done → disjoint
13}
segment pair3
1 / 8

Complexity and tradeoffs

Time: O(1). Space: O(1). Robust implementations must handle zero orientation and numeric precision explicitly.

Invariant: The sign of each exact cross product consistently encodes left, right, or collinear orientation for its ordered point triple.

Where it fits

Segment intersection is a primitive for clipping, polygon validity, collision detection, and sweep-line algorithms. Integer coordinates help avoid floating-point sign errors.