line-intersection

100%

line-intersection

✓ Published0🌍 Public

Last edited Apr 5, 2016

Created on Apr 6, 2016

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.

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.

Similar vizzes

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

88% match

Loading thumbnail…

two line intersection

A draggable line-intersection demo lets the user move four endpoints to see where two line segments cross. The intersection point is drawn as a small circle, which turns red only when the segments actually intersect; otherwise it stays gray. The visualization uses D3’s drag behavior and data joins to bind the points and path elements, while a custom `intersection` function in `geometry.js` computes the crossing and checks whether it lies on both segments. Rendering relies on SVG paths and circle elements, with coordinates updated on each drag event.

11wheel

85% match

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

Aapburnes

83% 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

82% match

Loading thumbnail…

intersection-multi-line

A grid of animated, multi-colored lines traces the paths of moving points, with highlighted intersection points where lines cross. Rendered with SVG and canvas, the visualization uses d3.js to compute and draw line intersections in real time, creating an intricate, ever-changing pattern. The animation emphasizes the dynamic relationships between the moving lines as they intersect.

11wheel

82% 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

81% match

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

80% 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

80% match