line-intersection

100%

line-intersection

✓ Published0🌍 Public

Last edited May 25, 2016

Created on May 25, 2016

This interactive visualization demonstrates the Bentley–Ottmann algorithm for finding line segment intersections. Users can drag endpoints to move lines, click to add new line segments, and right-click to remove them. The algorithm efficiently computes intersections using a sweep line rather than checking all pairs, achieving O(n log n + I log n) complexity. The right panel displays the current x-ordering of lines as the sweep progresses. Built with SVG and D3, the visualization updates in real time as users manipulate the line segments.

AI-generated description

The 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.

forked from <a href='http://bl.ocks.org/1wheel/'>1wheel</a>'s block: <a href='http://bl.ocks.org/1wheel/464141fe9b940153e636'>line-intersection</a>

forked from <a href='http://bl.ocks.org/apburnes/'>apburnes</a>'s block: <a href='http://bl.ocks.org/apburnes/68f69b32d86f6d987ddfd0e2c48d2872'>line-intersection</a>

forked from <a href='http://bl.ocks.org/apburnes/'>apburnes</a>'s block: <a href='http://bl.ocks.org/apburnes/c0d53f70215d4a49a200d24a5c0e6b3a'>line-intersection</a>

forked from <a href='http://bl.ocks.org/apburnes/'>apburnes</a>'s block: <a href='http://bl.ocks.org/apburnes/42118e82a0756867276c9afe5567e0c5'>line-intersection</a>

forked from <a href='http://bl.ocks.org/apburnes/'>apburnes</a>'s block: <a href='http://bl.ocks.org/apburnes/70b94260e227098fcca7caa069768655'>line-intersection</a>

forked from <a href='http://bl.ocks.org/apburnes/'>apburnes</a>'s block: <a href='http://bl.ocks.org/apburnes/29954d6dd6659485a402273b5dd8f3f4'>line-intersection</a>

Similar vizzes

Loading thumbnail…

line-intersection

This interactive visualization demonstrates the Bentley–Ottmann algorithm for finding line segment intersections. Users can drag endpoints to move lines, click to add new segments, and right-click to remove them. The algorithm sweeps a line from top to bottom, maintaining the order of segment x-positions at the current y (shown in the right panel), checking only adjacent pairs as the ordering changes. This reduces the complexity from O(n²) to O(n log n + I log n) for a set of lines with I intersections. The SVG rendering shows the segments and highlights intersections dynamically as they are discovered.

Aapburnes

98% match

Loading thumbnail…

line-intersection

This interactive visualization demonstrates the Bentley–Ottmann algorithm for finding all intersections among a set of line segments. Users can drag endpoints to reposition lines, click to add new segments, and right-click to remove them. The algorithm employs a sweep line that moves down the screen, maintaining the left-to-right order of line x-positions at the current y-coordinate in the panel on the right. As the sweep line encounters segment endpoints or intersections, it checks only adjacent pairs, achieving O(n log n + I log n) complexity instead of O(n²) for all pairs. The SVG rendering shows the line segments with draggable endpoints and displays the current sweep-line state, with red points marking intersection events.

Aapburnes

98% match

Loading thumbnail…

line-intersection

This interactive visualization demonstrates the Bentley–Ottmann algorithm for finding line segment intersections. Users can drag line endpoints to reposition them, click to add new segments, and right-click to remove them. The algorithm sweeps a horizontal line from top to bottom, maintaining the order of segment x-positions at the current y (shown in the right panel). Instead of checking all O(n²) segment pairs, only adjacent segments are tested for intersections as they start, end, or cross, yielding O(n log n + I log n) time for I intersections. The SVG rendering highlights intersection points as they are discovered, providing an intuitive view of the sweep-line process.

Aapburnes

98% match

Loading thumbnail…

line-intersection

This interactive visualization demonstrates the Bentley–Ottmann algorithm for finding all intersections in a set of line segments. Users can drag endpoints to reposition lines, click to add new segments, and right-click to remove them. Rather than checking every pair of segments (O(n²) comparisons), the algorithm sweeps a horizontal line from top to bottom, maintaining the left-to-right order of segment intersections with the sweep line in a balanced tree shown on the right. As segments start, end, or cross, only newly adjacent pairs are tested for intersections, reducing the complexity to O(n log n + I log n) for I total intersections. The visualization uses SVG rendering and is implemented with D3.

Aapburnes

97% match

Loading thumbnail…

line-intersection

The visualization demonstrates the Bentley–Ottmann algorithm for finding all intersections among a set of line segments. Users can drag endpoints to move lines, click to add new segments, and right-click to remove them. Rather than checking every pair of segments (O(n²)), the algorithm sweeps a horizontal line from top to bottom, maintaining the order of line x-positions at the current y in the right-hand panel. Intersections are detected only between adjacent lines in this ordering, reducing the complexity to O(n log n + I log n) for I intersections. The left panel shows the line segments with their intersection points marked, while the right panel displays the sweep line's current ordering. Rendered as SVG using D3.

Aapburnes

97% match

Loading thumbnail…

n-line intersection

This example visualizes the Bentley-Ottmann algorithm for finding intersections among multiple line segments, using an animated sweep line to show when segment adjacency changes. The left panel displays the segment ordering as a sequence of dots, with black lines connecting newly adjacent pairs that are checked for potential crossings. The right panel renders the segments themselves, highlighting intersection points in red. The code uses D3.js with custom helper libraries (d3-jetpack, d3-starterkit, geometry) for SVG rendering, along with Lodash for utility functions. The animation progressively updates the sweep line position, demonstrating how the algorithm maintains order and only tests nearby segments.

11wheel

89% match

Loading thumbnail…

line-intersection

Interactive line intersection visualization built with D3.js and SVG. Users click to add draggable points, which automatically connect to form line segments. The visualization computes and highlights all intersection points between line segments, with different colors indicating whether intersections are genuine crossings or overlaps at endpoints. Points can be dragged to dynamically update the intersections in real time, providing an intuitive way to explore geometric relationships between lines.

Aapburnes

83% match

Loading thumbnail…

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.

11wheel

82% match