# Scientific specification and numerical conventions This demonstration implements the two-dimensional tolerance-region construction in Castro, Tournois, Alliez and Devillers. It rebuilds the actual Delaunay triangulation for each accepted movement. It does not implement the paper's incremental update queue or benchmark the filtering algorithm. ## Verified sources - **Filtering Relocations on a Delaunay Triangulation**, Computer Graphics Forum 28(5), 1465–1474 (2009), P. M. M. de Castro, J. Tournois, P. Alliez and O. Devillers. [DOI](https://doi.org/10.1111/j.1467-8659.2009.01523.x), [public Eurographics PDF](https://diglib.eg.org/bitstreams/65b5d5b6-999a-4c1d-ae92-5a9fe02ca74b/download). This is the principal, full article. - **Fast Delaunay Triangulation for Converging Point Relocation Sequences**, P. M. M. de Castro and O. Devillers, EuroCG 2009, 231–234. [Official proceedings](https://computational-geometry.org/abstracts/eurocg/2009.pdf#page=232). This is the precursor. Its Figure 1 corresponds to Figure 3 in the full article. - **Practical Ways to Accelerate Delaunay Triangulations**, P. M. M. de Castro, doctoral thesis (2010), Chapter 5, §§5.1–5.3, pp. 54–63 / PDF pp. 83–92; Figure 5.3 on p. 58 / PDF p. 87. Chapter 5 presents the corresponding definitions. The implementation follows the definitions in §§2.1–2.3 of the full article, including the convex-hull cases (§2.2), fixed/moving positions (§3.2), the numerical discussion on p. 1470, Equation (4) and Figures 1–4. Chapter 5 of the thesis gives a corresponding account. ## The implemented object For a reference triangulation T and vertex z, A is the intersection of the permitted sides of **all** bi-cell delimiters involving z. This includes bi-cells in which z belongs to the common edge and those in which z is an opposite vertex. For adjacent triangles abc and abd with common edge ab, the standard delimiter center o solves ``` 2 (b-a) · o = |b|² - |a|² 2 (d-c) · o = |d|² - |c|² r_f = |o-a| = |o-b| r_o = |o-c| = |o-d| R = (r_f + r_o) / 2 ``` The delimiter is the median circle (o,R) of the concentric annulus. It is not one of the triangle circumcircles. For z in {a,b}, the permitted side is |q-o| ≤ R. For z in {c,d}, it is |q-o| ≥ R. The implementation never silently swaps the radii or the permitted sides. `finiteDelimiter` solves in local normalized coordinates. A difference of squared radii divided by their sum reduces cancellation. `margin` uses a related implicit equation to avoid directly subtracting almost equal distances. In 2D, for a strictly Delaunay finite bi-cell, the standard center lies between the adjacent circumcenters along the edge bisector and r_o > r_f. This 2D observation is a derived justification, not a quotation from the article. The numerical construction checks all four residuals. These residual checks also use binary64; they are not an exact or interval certificate of separation. ## Infinite bi-cells Both §2.2 types are included; the viewport does not replace the convex hull. 1. A hull edge ab adjacent to triangle abc supplies the line parallel to ab halfway toward c. The edge endpoints stay on one side, c on the other. 2. A hull vertex b with neighboring vertices a,c supplies the line parallel to ac halfway toward b. Vertex b stays on one side and a,c on the other. The selected vertex may be any participating point. An isolated triangle yields six constraints per vertex, including legitimate geometric duplicates across the two types. A linear constraint has a unit normal n, offset h and side s, and its margin is s(n·q-h) ≥ 0. ## Centered disk B B is centered at the reference position z0. Its radius is the minimum clearance to a delimiter: ``` circle inclusion: R - |z0-o| circle exclusion: |z0-o| - R half-plane: s(n·z0-h) r = minimum of these clearances ``` A disk at this fixed center is contained in the intersection exactly when it is contained in every constraint. Each clearance limits the radius and yields a tangency. No optimization over free centers, polygon erosion, radial sampling or raster search defines A or B. Proposition 1 allows simultaneous relocation inside the vertices' reference regions with the delimiters held fixed. A is not the maximal movement region of a single vertex with every other point fixed. Leaving A removes the guarantee but does not force a connectivity change. The tests exercise both possible outcomes outside A. The closed boundaries are drawn. Strict preservation is not asserted at a boundary or within a numerical uncertainty band. The boundary of B is distinguished from the boundary of A. ## Reference modes, all regions and history **Fixed reference** retains an explicitly adopted triangulation and all of its bi-cell delimiters. Selecting another vertex only selects its region; it does not adopt a new reference. Multiple vertices may be moved against that same reference. The preservation condition requires every vertex to remain strictly inside its own fixed region, and the numerical implementation independently checks the rebuilt connectivity. Membership of one selected point is not a guarantee about the other moved points. **Live regions** rebuilds the current triangulation, its delimiters and all displayed regions as one state for each accepted movement frame. The displayed disks are centered at the current positions. A point being inside a region just recomputed around itself does **not** certify the preceding movement or imply that there was no edge change. No preservation claim is shown in this mode. The topology comparison remains relative to the last explicitly adopted triangulation, which is not silently replaced by live updates. Returning to fixed mode reveals that same adopted reference. **Adopt current Delaunay** replaces the adopted reference with the current positions and triangulation. If activated during a drag, the last pending position is applied and the drag is completed before adoption. Other changes of dataset, mode or selected vertex cancel an unfinished drag. Undo and Redo store points, reference points, mode, selected vertex and dataset provenance together. One completed drag or held-key gesture is one action; adoption is a separate action. Undo during an unfinished gesture cancels only that gesture. A new accepted action clears the redo branch. History retains the latest 60 actions. **Show all regions** computes A and B for every vertex from the same reference mesh. The selected region is filled and other regions are outlined; A and B are independently switchable. Delimiter circles belong only to the selected region. Counts explicitly identify unavailable drawings and unbounded regions. The viewport does not define or truncate any mathematical region, and an overview containing multiple regions is labeled as a partial view. Pointer events are coalesced to the most recent requested position. Live updates with all regions are scheduled no faster than 30 times per second; expensive frames can take longer. Points, mesh, regions, numeric status and canvas are updated together. No asynchronous geometry results can overwrite a later dataset or reference. These are sampled configurations: flips between sampled positions are not enumerated, and no continuous-path certificate is claimed. Mouse background dragging pans. On touchscreens, tap to select and then drag the selected vertex. Swiping near an unselected vertex or on the background scrolls the page; two fingers zoom/pan. Starting a second touch cancels an in-progress relocation before zooming. Small screens show one active diagram; the inactive panel is inert. Cameras are re-expressed in the new normalization after live updates, adoption or history restoration, preserving the physical view. Zoom is limited to a minimum normalized span of 1e-6 without changing the mathematical region. ## Exact cocircularities in measured data Measured coordinates are recorded at a fixed decimal resolution (0.1 mm, 0.1 cm), so exact cocircular quadruples are common: axis-aligned rectangles of four observations lie on one circle. The Iris sepal preset has 14 cocircular finite bi-cells at rest and 79 of its 117 reference regions therefore have a zero tolerance radius. This is a property of the data, not a numerical failure: a weak Delaunay triangulation is used without perturbation, the affected regions have no guaranteed interior, and the preservation condition cannot apply while such ties exist in the current triangulation. The connectivity comparison with the adopted reference is still reported in that state and is flagged as non-unique, because another valid diagonal choice could produce part of the reported difference. ## Arithmetic and practical limits Topological predicates use static floating-point sign filters with Shewchuk's first-stage error constants. Ambiguous, non-finite and extreme-scale evaluations fall back to exact integer arithmetic on the represented IEEE-754 binary64 inputs. `orientExact` and `incircleExact` convert the inputs to common-exponent dyadic integers and evaluate determinants with `BigInt`. The exact signs apply to represented values, not arbitrary decimal real numbers. Reference: [Shewchuk, Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates](https://www.cs.cmu.edu/~quake/robust.html). Circle centers, radii, square roots, intersections, margins and screen coordinates use **binary64**. They are numerical constructions of analytic constraints, not exact algebraic constructions. `Canvas.arc` and clipping display circles and half-planes; rasterization is only a display step. Each circle carries the heuristic uncertainty estimate ``` 512 * Number.EPSILON * max(1, |o_x|, |o_y|, R) * max(1, condition) ``` Lines use 512 * Number.EPSILON; classification has a 1e-14 floor. Classification tests each constraint's own estimate, rather than applying the largest estimate to every constraint. B's interior indication uses the zone-wide estimate conservatively. **The estimate is not a certified bound.** In multiscale inputs, normalization can lose local detail, and the heuristic can underestimate construction error. For nearly parallel bisectors, it can instead grossly overestimate uncertainty. Numerical residual checks do not turn this heuristic into a proof. The theoretical statement is about the analytic delimiters; the interface presents numerical region membership and separately rebuilt topology. This implementation never uses the disk to skip triangulation reconstruction. A circle of normalized radius at least 1e7, or uncertainty estimate at least 1e-5, makes the whole zone non-renderable. The UI displays “Region not displayed — no guarantee.” Near-degenerate inputs do not receive an artificial positive radius through perturbation. Circle intersections and arc selection also use tolerances: up to 1e-10 for merging nearly identical angles and 1e-14–1e-10 for parallel/tangent cases. Tiny arcs require particular care. The inequalities are the region definition; the derived arc list is used to display and frame the region, without claiming symbolic exactness. Inputs are limited to 150 finite points, with coordinate magnitude at most 1e100. Exact coincident inputs are grouped with a notice; coincident move targets are rejected. Collinear inputs have no 2D tolerance region and show the Delaunay chain and Voronoi bisectors. Cocircular inputs admit multiple diagonals; the relevant centered disk has zero radius. A valid weak Delaunay triangulation is used without artificial perturbation. ## Complete region and viewport The fill intersects inclusion disks and half-planes, and excludes disks using an even-odd clipping rule. Boundary pieces are native circular arcs and line segments/rays selected from analytic intersections. The viewport rectangle never adds a geometric constraint or a region boundary. An inclusion disk implies boundedness. Otherwise, the half-planes are tested for a nonzero recession direction; finite excluded disks cannot block its tail. Unbounded regions explicitly say “Unbounded region · partial view.” A bounded region partly outside the view is labeled and can be framed with Fit. As with the construction, framing uses numerical intersection coordinates. ## Figure-derived point set The ten marker centers were recovered approximately from the public vector Figure 3. They are not the original experimental data. `datasets.js` preserves these supplied values and applies only x' = x-300 and y' = 220-y. The selected vertex has index 9. All delimiter circles are recomputed. Eight of the nine illustrated circles closely match the reconstructed bi-cells; the remaining illustrated circle and the illustrated small disk should not be treated as exact numerical source data. In particular, the disk drawn in the figure is not exactly tangent after marker reconstruction. The displayed centered disk is recomputed from the approximate marker positions using the numerical construction described above. ## Validation The implementation was checked with finite tests of global Delaunay validity, region construction, centered containment and tangency, circular boundaries, both infinite bi-cell types, relocation inside, outside and on the boundary, simultaneous relocation, degeneracies, near-degeneracies and scale changes, together with an independent exact-arithmetic comparison on generated cases. Finite tests support the implementation; they do not prove that arbitrary numerical constructions are exact. ## Measured datasets and physical units The four measured presets use the public source snapshots documented in [Measured datasets and sources](DATA-SOURCES.md). Exact coincident source-coordinate pairs are grouped, preserving observation multiplicity; no jitter is applied. Measurement presets use their original mm/cm coordinate values. NOAA presets use a spherical azimuthal equidistant projection in km about the midpoint of each state subset’s longitude/latitude range, with sphere radius 6371.0088 km. This is a local planar approximation, not a geodesic Delaunay triangulation or ellipsoidal survey result. Both screen axes use the same scale. Radii and coordinate controls remain in the dataset’s physical units. The dataset source, license, subset, axes, projection/transform and attribution are available in the interface. Original coordinates, source row/station identifiers and observation multiplicities are retained in the local dataset definitions (`real-datasets.js`). Moving points changes only the exploratory copy and visibly marks positions as modified; Undo can restore the original-data label. Imported local text/CSV data are labeled separately and are not uploaded. ## Coordinate import Imports accept exactly two decimal numeric columns per row, with scientific notation allowed. Use a decimal point and one separator style per row: whitespace, comma or semicolon. One trailing comma/semicolon is accepted; missing leading/interior coordinates, mixed delimiters and hexadecimal literals are rejected. Recognized optional headers are x,y, lon,lat and longitude,latitude (case-insensitive, with equivalent whitespace or semicolon separators). Other first rows are validated as data and never silently discarded. Headers do not trigger a projection or unit conversion.