Stony Brook Algorithm Repository


Robust Geometric Primitives

Input
Output

Input Description: A point \(p\) and a line segment \(l\), or two line segments \(l_1\) and \(l_2\).
Problem: Does \(p\) lie over, under, or on \(l\)? Does \(l_1\) intersect \(l_2\)?

Excerpt from The Algorithm Design Manual: Implementing basic geometric primitives is a task fraught with peril, even for such simple tasks as returning the intersection point of two lines. What should you return if the two lines are parallel, meaning they don't intersect at all? What if the lines are identical, so the intersection is not a point but the entire line?

What if one of the lines is horizontal, so that in the course of solving the equations for the intersection point you are likely to divide by zero? What if the two lines are almost parallel, so that the intersection point is so far from the origin as to cause arithmetic overflows? These issues become even more complicated for intersecting line segments, since there are a bunch of other special cases that must be watched for and treated specially.


Implementations

CGAL (rating 10)
LEDA (rating 9)
libigl (rating 8)
gosl (rating 8)
3D Convex Hull algorithm in Java (rating 8)
EGC (rating 8)
geometry3Sharp (rating 7)
Fast Robust Predicates for Computational Geometry (rating 7)
wykobi (rating 6)
geode (rating 6)
Computational-geometry (rating 6)


Recommended Books

Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky Computational Geometry in C by Joseph O'Rourke Algorithms from P to NP, Vol. I: Design and Efficiency by B. Moret and H. Shapiro

Related Problems


Determinants and Permanents

Intersection Detection

Maintaining Line Arrangements


As an Amazon affiliate, I earn from qualifying purchases if you buy from links on this website.


Go To Main Page