Page Title

100%

✓ Published0🌍 Public

Last edited Sep 22, 2014

Created on Sep 21, 2014

This visualization demonstrates the convex hull algorithm, which finds the smallest convex polygon that contains a set of randomly generated points. The process animates step by step: first locating the highest point, then identifying subsequent points by measuring the smallest angle from the previous line segment using dot products, and finally drawing the boundary polyline as the algorithm progresses. The visualization uses D3.js v3 with SVG elements, including circles for data points, a polyline for the boundary, and animated lines representing the sweep line and ray. Points turn red as they join the hull, while the sweep line rotates to test each candidate point against the current angle threshold.

AI-generated description

This program demonstrates an algorithm for finding the smallest convex polygon containing a given set of points (Convex hull).

The algorithm works as follows

Find the highest point A.
Find the second point by searching for a point B such that AB makes the smallest angle with the positive x direction.
Find the remaining points recursively by searcing for a point Z such that YZ makes the smallest angle with XY where X and Y are the last two points found (Y after X). Include the initial point A in the search. When the search ends in A, then the path is complete.

The dot product is used to find the angle between two vectors.

Similar vizzes

Loading thumbnail…

Convex Hull

A set of 100 randomly positioned points forms a convex hull, depicted as a rounded, padded blue polygon that encloses the outermost points. Users can move the first point by moving the mouse and add new points by clicking, which recomputes the hull in real time. The example uses d3.geom.hull to calculate the polygon boundary and d3’s selection and data-join methods to update the SVG circles and path. Drawing occurs in SVG with d3.v3, and the hull’s thick stroke visually pads the geometric outline.

FFrissAnalytics

80% match

Loading thumbnail…

Convex Hull

This example visualizes the convex hull of a set of normally distributed points, updating live as the user moves the mouse to reposition the first point or clicks to add new points. The hull is rendered as a padded, rounded stroke path, using `d3.geom.hull` to compute the polygon from the current vertex array. The points themselves are drawn as white circles with black strokes, and their positions are updated via `attr("transform", ...)` translations. All rendering is done with SVG elements, and the example relies on `d3.select`, `d3.mouse`, and `d3.range` for interaction and data generation.

Mmbostock

78% match

Loading thumbnail…

Convex Hull

A set of one hundred normally distributed points is enclosed by their convex hull, a steel-blue polygon computed with Andrew’s monotone chain algorithm via the `d3-polygon` `hull` function. As the mouse moves, the first point is repositioned and the hull is recomputed in real time. The visualization is drawn on a Canvas using the standard `canvas` API, with the underlying point set generated by `d3-random.normal` from the `d3-random` library.

Mmbostock

77% match

Loading thumbnail…

D3.js

This D3.js example demonstrates the marching squares and convex hull algorithms from the d3.geom module, rendering SVG polygons with animation. The visualization computes contour polygons for a given grid function and convex hulls for sets of points, displaying them as animated vector graphics. Using d3.v2, the code samples highlight algorithmic geometry operations (contour tracing and Graham scan) implemented in D3's geometry namespace, with the SVG rendering showing how these computed polygons adapt dynamically as the underlying data changes.

GGerHobbelt

74% match

Loading thumbnail…

Bounded Voronoi Tessellation

This interactive visualization demonstrates a bounded Voronoi tessellation, where 100 randomly placed sites partition the SVG canvas into colored polygonal cells. The mouse controls the first site, dynamically updating the diagram as it moves. The code uses d3.voronoi to compute the tessellation and d3.polygonHull to create a convex hull around the sites, which is then expanded outward to bound the diagram. Artificial points are added along this expanded hull to ensure the Voronoi cells are fully enclosed, with the generator sites rendered as circles and the convex hull traced as a pink line.

PPhilippe Rivière

69% match

Loading thumbnail…

Alpha-Shapes

This example visualizes the alpha-shape boundary of a set of 2D points, highlighting the concave hull that encloses the data. It uses D3.js to compute a Delaunay triangulation via `d3.geom.delaunay`, filters triangles whose edges exceed a squared alpha threshold, and then traces the outer edges with a custom `boundary` function. The points are offset horizontally, and the resulting polygon is rendered in yellow SVG paths over a blue background, while the raw vertices remain hidden. The code relies on D3 v5 and an older D3 geometry module for triangulation.

EEdward-Elric233

68% match

Loading thumbnail…

Circular Bounded Voronoi Tessellation

This example displays a Voronoi tessellation of one hundred randomly placed circular sites, with a colored convex hull that fully encloses the diagram and a single site that follows the mouse. The hull shape is derived from `d3.polygonHull` and then expanded outward along each vertex’s centroid radial angle using a distance calculated from the median of the Delaunay links, computed with `d3.median`. The code uses `d3.voronoi` with an extent, and renders the result as SVG paths, lines, and circles. The convex hull itself is drawn as a closed Catmull‑Rom curve via `d3.line().curve(d3.curveCatmullRomClosed)`, with additional artificial points added along the expanded hull boundary to ensure the tessellation stays within it.

PPhilippe Rivière

68% match

Loading thumbnail…

Image Hulling

Image Hulling turns a photograph into a stylized mosaic by sampling pixel colors and using d3’s Delaunay triangulation to connect them into a concave hull. The visualization displays a color-based image outline, with the concavity of the hull controlled by a distance metric calculated from the Delaunay triangles, and the original image is shown alongside for reference. A custom d3.geom.concaveHull plugin is used to generate the outline, with optional padding, and the final result is rendered with both SVG and canvas to show the image regions.

DDinoJay

67% match