DIRECTORY Rope USING [ROPE], IO USING [PutF, int, real, GetChar], GraphicsColor USING [red, black, blue, green], COGDebug USING [in, out], COGCart USING [Point, Random, Box, Dist], COGHomo USING [Point, Coords, CCW, InCircle, FinPt], COGVoronoi USING [Delaunay, DVertex, VVertex, VVertexCoords, Dest, Org, Left, VertexRec, MakeDelaunayObject, InfiniteTriangle], COGDiagram USING [DEdge, Sym, OPrev, LNext, LPrev, FixLeft, FixRight, AddVertex, VisitProc, Traverse, DeleteEdge, PutE, ConnectVertices], COGDrawing USING [Drawing, Color, Object, Size, RepaintAll, GetProp, PutProp, MouseProc, MenuProc, AddMouseAction, AddMenuAction, Add], COGVorTest USING [theDrawing, ShowEdge, ShowVertex, CleanTheDrawing, drBox]; COGVorIncrImpl: CEDAR PROGRAM IMPORTS IO, COGHomo, COGDrawing, COGDebug, COGCart, COGDiagram, COGVoronoi, COGVorTest = BEGIN OPEN Rope, GraphicsColor, IO, Homo: COGHomo, Cart: COGCart, Draw: COGDrawing, COGVoronoi, Bug: COGDebug, Diag: COGDiagram, COGVorTest; theDelObj: Draw.Object; -- "the" Delaunay object DumbLocateInVoronoi: PROC [newPt: Cart.Point, dlau: Delaunay] RETURNS [eMin: Diag.DEdge _ [NIL, 0]] = 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; InsertInVoronoi: PROC [newPt: Cart.Point, dlau: Delaunay, trace: BOOL _ TRUE] = 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; InsertMousedPoint: Draw.MouseProc = 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; ThrowTenPoints: Draw.MenuProc = 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; Bug.out.PutF["\nVorIncr: Hello! Say something: "]; [] _ Bug.in.GetChar[]; theDelObj _ MakeDelaunayObject [InfiniteTriangle[]]; Draw.Add [theDrawing, theDelObj, 3]; Draw.PutProp [theDrawing, $DelObj, theDelObj]; Draw.AddMouseAction [theDrawing, [button: red], InsertMousedPoint, NIL, write]; Draw.AddMenuAction [theDrawing, "ThrowTen", ThrowTenPoints, NIL, write]; Bug.out.PutF["\nVorIncr: Enjoy yourself. Bye!"] END. v-- COGVorIncrImpl.mesa: Incremental Voronoi construction -- last modified by Stolfi - October 16, 1982 8:31 pm -- To run: run COGAll; run COGVoronoiImpl; run COGVorTestImpl; run COGVorIncrImpl -- Finds the finite DVertex that is nearest to newPt. If none such, returns a random (infinite) DVertex. -- 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. Ê1– "Mesa" style˜IprocšÏcÐbc"™8Kš5™5Kšž"œ'™TKšœÏk œŸœŸœŸœŸœ-Ÿœ'ŸœŸœ'Ÿœ5Ÿœ†ŸœŸœŽŸœ<˜øKšÏbœŸ œŸœŸœR˜€KšŸœŸœŸœr˜šKš  œ˜0šÏnœŸœ'ŸœŸœ˜gKšh™hKšŸœ ŸœAŸœŸœŸœAŸœ ŸœŸœŸœNŸœŸœ ŸœŸœŸœ˜ì—š¡œŸœ.ŸœŸœ˜QKšC™CKš [žžSž!ž™þKš¤ŸœPœŸœ’ŸœŸœ+ŸœŸœ-Ÿœ Ÿœ8ŸœFœ Ÿœ*ŸœŸœŸœ,ŸœŸœŸœŸœŸœZœSœŸœ2œFœUœ#œŸœ0ŸœŸœ ŸœŸœŸœ'Ÿœ)ŸœŸœœŸœŸœ0@œ œUŸœ8œ2œ3œŸœŸœŸœŸœ&Ÿœ(ŸœŸœ}ŸœNœ0œ`ŸœŸœ-&œQŸœŸœŸœŸœXœ"œUœOœ-œœŸœIœ?œŸœ Ÿœœ¡ŸœŸœ~&œ*ŸœŸœŸœ+Ÿœ5Ÿœ˜ü —š œ˜#KšŸœ>œž@žžžœMŸœŸœŸœ˜—š œ˜KšŸœ<œžFžžžœMŸœbŸœ Ÿœ1ŸœŸœŸœ˜Ý—Kšœ®Ÿœ˜´—…—R!ù