CIn · UFPE

Tolerance regions

Demo by Pedro M. M. de Castro · Derived from Castro et al., 2009

Diagram

An application: move sites toward their Voronoi centroids.
01

The plane

Select and drag a vertex
Delaunay Voronoi
02

Near z

A · Complete region B · Centered disk
Reference disk B radius—point-set units

At the reference positionConnectivity preserved

The region stays fixed as you move the point.

Point-set source, units & transformations
A

The complete safe region

Intersect the permitted sides of every delimiter involving z. Its boundary consists of circular arcs and, near the convex hull, straight lines.

B

The largest disk with this center

In fixed mode, the center stays at z₀. Live mode centers it at the current vertex. Its radius is the smallest clearance to a delimiter: r = min dist(z₀, D). The disk touches the boundary of A.

↗

Beyond the boundary

Leaving A removes the preservation guarantee. Connections may change or stay the same. The current triangulation is checked independently.

Explore the geometry

  1. Choose a point set and select a vertex. The detail panel shows its region. Choose Live: all tolerance regions to update every vertex’s regions while dragging any one point. Other regions are outlines and the selected region is filled. A and B remain independently selectable.
  2. Move the point by dragging, with the arrow keys, or by entering coordinates. The small ring marks the reference position.
  3. Compare the results. Region membership and actual connectivity are reported separately.
  4. Adopt current Delaunay to keep the current triangulation as the fixed reference. Selection alone does not change the reference. Undo and Redo restore both the points and their reference.
  5. Explore Lloyd CVT runs the bounded centroidal Voronoi walkthrough on the current point set: cells, frozen centroid targets, movement (Together or One by one under Move sites) and the new diagram. Its panel explains the energy, the residual and the sequential disk-B counts.

Fixed reference keeps the regions in place. Live: all tolerance regions recomputes the triangulation and every vertex’s regions together at each displayed movement frame, including vertices whose neighbours change. Live: selected region shows only the selected region for a lighter view. A point being at the center of its freshly recomputed region does not certify that its movement preserved connectivity. Connectivity is compared separately with the last adopted triangulation. Large point sets can animate more slowly with all regions enabled.

On a mouse, drag the background to pan. On touchscreens, tap a vertex to select it, then drag the selected vertex with one finger to move it. Swiping elsewhere scrolls the page; two fingers zoom and pan the diagram without moving points. The Plane / Near z tabs keep one panel visible on small screens.

Use +, − and Fit to control the view. With focus in a diagram, arrow keys move the selected point; Shift reduces the step. Escape cancels a drag. Undo reverses a completed drag, keyboard gesture, coordinate move, adoption, mode change or dataset change. During a drag it cancels that movement. Redo restores the undone action.

Definitions and conventions

A bi-cell consists of adjacent triangles. Its standard delimiter is the median circle of the concentric annulus through the shared edge and the opposite vertices. Shared-edge vertices stay inside; opposite vertices stay outside. Both types of infinite bi-cell supply half-plane constraints.

A is the complete intersection of these constraints. It depends on the chosen delimiters and supports simultaneous movements within the reference regions. It is not the maximal region obtained by holding every other vertex fixed.

B is the largest disk centered at the reference vertex. Boundaries are drawn, but boundary and numerically uncertain states receive no strict preservation guarantee. Unbounded regions are explicitly labeled as partial views.

Circle constructions and intersections use finite precision. The uncertainty band is a heuristic, not a certified error bound, particularly in multiscale inputs. The topology uses certified predicate signs on represented coordinates; the triangulation is rebuilt for every accepted move.

Coincident inputs are grouped with a notice, and coincident drag targets are rejected. Collinear sets have no 2D tolerance region. At cocircularity, multiple Delaunay diagonals can be valid.

Read the scientific notes and numerical limitations

Your point set

One point per line: x y, x,y or tab-separated. An x,y, lon,lat or longitude,latitude header is optional. Use exactly two columns; a trailing separator is allowed. Use a decimal point. Up to 150 rows; exact coincident pairs are grouped. Files are read locally.

Move the selected vertex

The fixed regions stay in place until adoption.