-- Finds the finite DVertex that is nearest to newPt. If none such, returns a random (infinite) DVertex.

BEGIN
minDist: REAL;
VTest: Diag.VisitProc =
{d: DVertex = Org[e];
dist: REAL;
IF Homo.FinPt[d.pt] THEN
{dist ← Cart.Dist [Homo.Coords [d.pt], newPt];
IF eMin.rec = NIL OR dist < minDist THEN
{eMin ← e; minDist ← dist}}};
[] ← Diag.Traverse [dlau.dg, VTest, NIL, vertices];
IF eMin.rec = NIL THEN eMin ← dlau.dg
END;

-- Adds a new finite vData point newPt to the Delaunay diagram Diag

-- Assumes the diagram is currently an object of the Drawing dr and assumes the caller has write access rights to dr. If trace=TRUE, will highlight the new and deleted edges by adding new objects to dr; these will NOT be removed from dr before returning.

BEGIN
en: Diag.DEdge ← DumbLocateInVoronoi [newPt, dlau];
n: DVertex = Org [en]; -- point closest to newPt
p: DVertex = NEW [VertexRec ←
[pt: [newPt.x, newPt.y, 1.0], no: dlau.limDV]];
lvr, lvs: VVertex;
q, r, s, t: DVertex;
ep, er, es, et: Diag.DEdge;

Bug.out.PutF ["\nVorIncr.InsertInVoronoi: Inserting point %g at [%g, %g]...", int[p.no],
real[newPt.x], real[newPt.y]];
Bug.out.PutF ["\nVorIncr.InsertInVoronoi: nearest point is Org [ "]; Diag.PutE[en];
Bug.out.PutF ["] = vertex %g", int[n.no]];
IF trace THEN ShowVertex [v: p, color: red, side: 3];
IF trace THEN ShowVertex [v: n, color: green, side: 3];
IF p.pt = n.pt THEN
{Bug.out.PutF["\nDuplicate point - ignored"];
RETURN};
q ← n;
-- locate the segment qp between consecutive edges er and es out of q
er ← en;
UNTIL Homo.CCW [p.pt, q.pt, (r ← Dest[er]).pt] DO er ← Diag.OPrev[er] ENDLOOP;
DO
es ← Diag.LPrev[er]; s ← Org[es];
IF Homo.CCW[p.pt, q.pt, s.pt] THEN {er ← Diag.Sym[es]; r ← s} ELSE EXIT
ENDLOOP;
-- delete all edges that have to be deleted, leaving a "hole" in the delaunay surrounding
-- the point p. Also updates the Voronoi vertices of the edges around this hole.
DO
-- at this point q is a vertex of the final hole,
-- es is the c.c.w. edge of the latter with Dest = q, s is Org[es],
-- and er is LNext[es] in the current voronoi (not necessarily in the final hole).
-- delete edges out of q if needed
DO
et ← Diag.OPrev[er]; t ← Dest[et];
IF Homo.CCW [p.pt, q.pt, r.pt] AND
(NOT Homo.CCW [p.pt, q.pt, t.pt] OR NOT Homo.CCW [t.pt, r.pt, p.pt]
OR Homo.InCircle [p.pt, q.pt, t.pt, r.pt]) THEN EXIT;
-- the edge er must be deleted
IF trace THEN ShowEdge [e: er, width: 2, color: blue];
-- Bug.out.PutF ["\nVorIncr: Deleting edge "]; Diag.PutE[er]; -- -- DEBUG --
[] ← Diag.DeleteEdge [er]; dlau.nVV ← dlau.nVV - 1;
er ← et; r ← t
ENDLOOP;
-- At this point er is LNext[es] in the final hole too.
-- The angles [p, s, q] and [q, r, p] are convex.

-- Compute the left Voronoi vertex of er if needed
IF NOT Homo.CCW [s.pt, q.pt, r.pt] OR NOT Homo.CCW [r.pt, p.pt, s.pt]
OR Homo.InCircle [r.pt, p.pt, s.pt, q.pt] THEN
{lvr ← NEW [VertexRec ←
[pt: VVertexCoords[p.pt, q.pt, r.pt], no: dlau.limVV]];
dlau.limVV ← dlau.limVV + 1}
ELSE
{lvr ← lvs};
-- fix the left Voronoi vertex of er (can't connect p and q now because there
-- may be other edges crossing the seg. p-q)
Diag.FixLeft [er, lvr];
Bug.out.PutF ["\nVorIncr: Following edge "]; Diag.PutE[er];
IF trace THEN ShowEdge [e: er, width: 2, color: red];
-- advance to next vertex around hole
q ← r; es ← er; s ← q; lvs ← lvr;
er ← Diag.LNext[es]; r ← Dest[er];
IF q = n THEN EXIT
ENDLOOP;

-- At this point q=n, the hole is ready, and es, er are the c.c.w. edges preceding and
-- following q around the hole.

-- Now connect p to the appropriate vertices around the hole. These are the vertices
-- separating two consecutive edges with different left Voronoi vertices, as
-- they were defined in the previous loop.
ep ← [NIL, ];
DO
-- At this point q is a vertex of the hole, er and es are as said above,
-- ep is the last edge laid out from p, and lvs is Left[es].
lvr ← Left[er];
IF lvr # lvs THEN
{-- Connect p to q
IF ep.rec = NIL THEN
{-- first edge out of p
ep ← Diag.Sym[Diag.AddVertex[p, es, left]];
dlau.nDV ← dlau.nDV + 1;
dlau.limDV ← dlau.limDV + 1}
ELSE
{-- not first edge - will close a ew face of the Delaunay
ep ← Diag.ConnectVertices [a: ep, b: er];
dlau.nVV ← dlau.nVV + 1};
Diag.FixLeft[ep, lvr]; Diag.FixRight[ep, lvs];
IF trace THEN ShowEdge [e: ep, width: 0, color: black];
Bug.out.PutF["\nVorIncr: Connected to vertex %g", int[q.no]];
};
-- advance to next vertex around hole
q ← r; es ← er; s ← q; lvs ← lvr;
IF q = n THEN EXIT;
er ← Diag.LNext[er]; r ← Dest[er]
ENDLOOP;
Bug.out.PutF ["\nVorIncr.InsertInVoronoi: EXIT"]
END;

BEGIN
-- parms: [dr, eventData: REF, x, y: REAL, event: MouseEvent]
-- called with write access. The Delaunay object where to inser the
-- point is GetProp[dr, $DelObj]
dlob: Draw.Object = NARROW [Draw.GetProp[dr, $DelObj]];
dlau: Delaunay = NARROW [dlob.parms.data];
CleanTheDrawing[repaint: TRUE];
Draw.PutProp[dr, $Tlee, NIL]; -- KLUDGE
InsertInVoronoi [[x, y], dlau, TRUE]
END;

BEGIN
-- parameters: [dr, menuData: REF ANY, button: MouseButton]
-- called with write access. The Dealunay object where to insert the new points
-- is GetProp[dr, $DelObj]
dlob: Draw.Object = NARROW [Draw.GetProp[dr, $DelObj]];
dlau: Delaunay = NARROW [dlob.parms.data];
CleanTheDrawing[repaint: TRUE];
Draw.PutProp[dr, $Tlee, NIL]; -- KLUDGE
THROUGH [1..10] DO
InsertInVoronoi [Cart.Random [drBox], dlau, FALSE];
Draw.RepaintAll [dr]
ENDLOOP
END;