-- the drawing and object where the delaunay is being displayed

-- 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 = MakeDVertex [[newPt.x, newPt.y, 1.0]];
vcur: VVertex;
q, r, s, t: DVertex;
ep, er, es, et: Diag.DEdge;
erConv: BOOL;

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 [dr: dr, v: p, size: 3];
ShowVertex [dr: dr, v: n, color: red, size: 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
erConv ← FALSE; es ← en;
DO
IF NOT Homo.Convex [p.pt, q.pt, Dest[es].pt] THEN
{IF erConv THEN EXIT}
ELSE
{erConv ← TRUE};
er ← es; es ← Diag.ONext[es]
ENDLOOP;
-- add p to the diagram, connected to q
ep ← Diag.AddVertex [p, Diag.Sym[es], left];
Bug.out.PutF["\nVorIncr: connected to vertex %g.", int[q.no]];
-- main loop
DO
-- at this point ep is a new edge out of q, between er and es c.c.w
r ← Dest[er];
-- delete edges out of q that interfere with p
DO
et ← Diag.OPrev[er]; t ← Dest[et];
IF NOT Homo.Convex [p.pt, q.pt, t.pt] OR
NOT Homo.Convex [t.pt, r.pt, p.pt] OR
Homo.ShouldConnect24 [p.pt, q.pt, t.pt, r.pt] THEN EXIT;
IF trace THEN ShowEdge [dr: dr, e: er, width: 2, color: blue];
Bug.out.PutF["\nVorIncr: Deleting edge "]; Diag.PutE[er];
[] ← Diag.DeleteEdge [er];
Bug.out.PutF[" - new face: "]; Diag.PutLRing[et];
er ← et; r ← t
ENDLOOP;
-- advance q to next vertex to be connected to p
DO
es ← Diag.Sym[er]; s ← q;
q ← r; er ← Diag.OPrev[es];
IF q = n OR
NOT Homo.Convex [r.pt, p.pt, s.pt] OR
NOT Homo.Convex [s.pt, q.pt, r.pt] OR
Homo.ShouldConnect24 [r.pt, p.pt, s.pt, q.pt] THEN EXIT;
ENDLOOP;
-- connect p to q (unless q is the starting vertex n) and set Voronoi vertex
vcur ← MakeVVertex [VVertexCoords[p.pt, s.pt, q.pt]];
IF q # n THEN
{ep ← Diag.Sym[Diag.CloseFace [ep, es, vcur, right]]}
ELSE
{ep ← er; er ← Diag.OPrev[er]; Diag.SetLeft [ep, vcur]};
Bug.out.PutF["\nVorIncr: closed face = "]; Diag.PutLRing [ep];
IF trace THEN
{et ← Diag.LNext [ep];
ShowEdge [dr: dr, e: ep];
DO
et ← Diag.LNext [et];
IF et = ep THEN EXIT;
ShowEdge [dr: dr, e: et, color: red, width: 2]
ENDLOOP};
IF q = n THEN EXIT;
ENDLOOP;
Bug.out.PutF ["\nVorIncr.InsertInVoronoi: EXIT"]
END;

BEGIN
Draw.Add [dr: dr, obj: MakeEdgeObject [e, color, width], order: 4, curr: write]
END;

BEGIN
Draw.Add [dr: dr, obj: MakeRegionObject [e, color, size], order: 4, curr: write]
END;

BEGIN
Draw.Add [dr: dr, obj: MakeVertexObject [v, color, size], order: 4, curr: write]
END;

BEGIN
-- parms: [dr, drawData, eventData: REF, x, y: REAL, event: MouseEvent]
-- called with write access. The eventData is the Dealunay object where to insert the new point.
dlob: Draw.Object = NARROW [eventData];
dlau: Delaunay = NARROW [dlob.parms.data];
Draw.RemoveAll [dr, write];
Draw.Add [dr, dlob, 3, write];
InsertInVoronoi [dr, [x, y], dlau, TRUE]
END;

BEGIN
-- parameters: [dr, drawData, menuData: REF ANY, button: MouseButton]
-- called with write access. The menuData is the Dealunay object where to insert the new points
dlob: Draw.Object = NARROW [menuData];
dlau: Delaunay = NARROW [dlob.parms.data];
Draw.RemoveAll [dr, write];
Draw.Add [dr, dlob, 3, write];
THROUGH [1..10] DO
InsertInVoronoi [dr, Cart.Random [drBox], dlau, FALSE];
Draw.DoPaintAll [dr]
ENDLOOP
END;