line-intersection
This example demonstrates an interactive line-intersection visualization, where users can add points by clicking on a canvas and drag them to see the resulting line segments and their intersections update in real time. The visualization highlights the geometric intersection points between line segments connecting all pairs of points, with a vertical divider separating the interactive area from a static queue preview. The rendering uses SVG with points, lines, and pair paths, and includes a side panel that shows a scaled representation of the point coordinates. The underlying code provides utility functions for point, distance, angle, and intersection calculations, and uses a sorted array with a custom bisector to manage points.
AI-generated descriptionThe Bentley–Ottmann algorithm finds all the intersections that occur in a set of line segments. Drag the endpoints of the line to move, click to add and right click to remove.
Instead of calculating the intersection of every pair of segments, which would require O(n²) comparisons for a set of n lines, the algorithm uses a sweep line. Starting at the top of the screen and moving down, it keeps track of the order of the lines' x positions at the current y position (represented by the figure on the right). As lines start, end or intersect, new pairs of lines become adjacent in the x ordering and are checked for intersections.
A set of lines with I intersections ends up only requiring O(n log n + I log n) operations. Computational Geometry: Algorithms and Applications, chapter 2 has a proof and a more detailed explanation.