n-line intersection

100%

n-line intersection

✓ Published0🌍 Public

Last edited Aug 21, 2016

Created on May 18, 2015

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.

AI-generated description

Calculating the intersections between n line segments can be done in n log n time. Here, segments are only checked for intersection when they are newly adjacent after a line start, end or intersection. The dots on the left show the order of the lines at each adjacency change, with newly adjacent pairs of lines connect by a black line.

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

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

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

74% match

Loading thumbnail…

Line Segment Intersection

An interactive line segment intersection test visualizes a red segment controlled by the mouse crossing a black horizontal sine wave. A spatial index tree organizes the wave's segments, and as the mouse moves, the d3.geo.path projection is used to redraw the test line, highlighting any intersecting segments in red. The example uses D3.js and a custom tree.js data structure to efficiently query for collisions based on bounding-box extents.

Mmbostock

74% match

Loading thumbnail…

Closest Line Segment

A brushless interaction demonstrates nearest-neighbor search over line segments. As the mouse moves, a red highlight identifies the closest segment to the cursor, with the active segment brought to the front. The example builds a binary tree of segment bounding boxes to accelerate the search, using a custom min-heap to prune distant branches. The segment geometry derives from a sine wave, rendered as SVG paths via `d3.geo.path`. The search logic is implemented in a standalone `tree.js` module, while `d3.mouse` handles coordinate tracking.

Mmbostock

67% match

Loading thumbnail…

Gist 79ed32828a2db39ec232

This example demonstrates a divide-and-conquer binary search tree constructed over a set of disjoint line segments that span a horizontal strip, with endpoints on two parallel lines. It visualizes how the segments partition the strip into regions and how a query point can be located by traversing the tree. The code uses D3.js with SVG to draw the segments, circles, and tree edges, and employs custom helper functions like `dataAppend` and `translate` from d3-jetpack. The tree is built by recursively splitting the sorted list of bottom endpoints, and the visualization highlights the connection between the geometric arrangement and the hierarchical search structure.

11wheel

67% match

Loading thumbnail…

linecross labels

This example shows how to connect labeled points to a series of evenly spaced endpoints using angled and straight line segments. Colored circles on the left link to larger target circles on the right through two distinct line types, with the bend point shifting between a shared midpoint and a point based on the source x-coordinate depending on the item’s index. The visualization renders three SVG charts side-by-side at different widths, using d3.scaleLinear for vertical positioning and d3-selection-multi’s attrs method to set line and circle properties. The dataset is a hardcoded array of seven objects with x, y, and color values.

PPatrick Wojda

66% match

Loading thumbnail…

Untitled

This example demonstrates how to connect multiple pairs of points with straight lines in a Cartesian coordinate system using D3.js v3. The visualization renders three separate line segments, each defined by two endpoints, on an SVG canvas with labeled x and y axes. The code uses d3.svg.line() to generate the path data, d3.scale.linear() for coordinate mapping, and d3.svg.axis() to draw the axes. Data is stored as an array of coordinate pairs in JavaScript, and each line is appended as an SVG path element with a distinct stroke color.

Aavesh1998

64% match