DIRECTORY Rope USING [ROPE], IO USING [PutF, int, real, GetChar], GraphicsColor USING [red, black, blue], COGDebug USING [in, out], Real USING [], COGCart USING [Point, Random, Box, Dist], COGHomo USING [Point, Coords, Convex, ShouldConnect24, FinPt], COGVoronoi USING [Delaunay, DVertex, VVertex, InfiniteTriangle, VVertexCoords, MakeDVertex, MakeVVertex, MakeDelaunayObject, MakeEdgeObject, MakeVertexObject, MakeRegionObject, AddDualEntryToMenu, Dest, Org, VertexRec], COGDiagram USING [DEdge, Sym, ONext, OPrev, LNext, SetLeft, AddVertex, CloseFace, VisitProc, Traverse, DeleteEdge, PutE, PutLRing], COGDrawing USING [Drawing, Color, Object, Size, MakeDrawing, Add, DoPaintAll, RemoveAll, MouseProc, MenuProc, AddMouseAction, AddMenuAction]; COGVorIncr: CEDAR MONITOR IMPORTS IO, COGHomo, Real, COGDrawing, COGDebug, COGCart, COGDiagram, COGVoronoi, GraphicsColor = BEGIN OPEN Real, Rope, GraphicsColor, IO, Homo: COGHomo, Cart: COGCart, Draw: COGDrawing, COGVoronoi, Bug: COGDebug, Diag: COGDiagram; theDrawing: Draw.Drawing; drBox: Cart.Box = [min: [-1, -1], max: [1, 1]]; theDlObj: Draw.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 [dr: Draw.Drawing, 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 = 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; ShowEdge: PROC [dr: Draw.Drawing, e: Diag.DEdge, color: Draw.Color _ black, width: Draw.Size _ 0] = BEGIN Draw.Add [dr: dr, obj: MakeEdgeObject [e, color, width], order: 4, curr: write] END; ShowRegion: PROC [dr: Draw.Drawing, e: Diag.DEdge, color: Draw.Color _ black, size: Draw.Size _ 0] = BEGIN Draw.Add [dr: dr, obj: MakeRegionObject [e, color, size], order: 4, curr: write] END; ShowVertex: PROC [dr: Draw.Drawing, v: REF VertexRec, color: Draw.Color _ black, size: Draw.Size _ 0] = TRUSTED BEGIN Draw.Add [dr: dr, obj: MakeVertexObject [v, color, size], order: 4, curr: write] END; InsertMousedPoint: Draw.MouseProc = 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; ThrowTenPoints: Draw.MenuProc = 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; Bug.out.PutF["\nVorIncr: Hello! Say something: "]; [] _ Bug.in.GetChar[]; theDrawing _ Draw.MakeDrawing ["INCREMENTAL VORONOI", drBox]; theDlObj _ MakeDelaunayObject [InfiniteTriangle[]]; Draw.Add [theDrawing, theDlObj, 3, none]; AddDualEntryToMenu [theDrawing]; Draw.AddMouseAction [theDrawing, [button: left], InsertMousedPoint, theDlObj, write]; Draw.AddMenuAction [theDrawing, "ThrowTen", ThrowTenPoints, theDlObj, write]; Bug.out.PutF["\nEnjoy yourself. Bye!"] END. œ-- COGVorIncr.mesa: Incremental Voronoi construction -- last modified by Stolfi - September 22, 1982 5:43 pm -- To run: run COGAll; run COGVoronoiImpl; run COGVorIncr -- 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. -- 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. ΚP– "Mesa" style˜IprocšΟcΠbc"™4Kš7™7Kšž"œ™ŸœŸœAŸœ‡ŸœŸœFŸœ)Ÿœ ŸœŸœBŸœŸœŸœŸœŸœ5Ÿœ˜Α—š‘œŸœW˜eKšŸœSŸœ˜\—š‘ œŸœV˜fKšŸœTŸœ˜]—š‘ œŸœŸœ>Ÿ˜qKšŸœTŸœ˜]—š œ˜#KšŸœHœž ž 7œŸœ!ŸœxŸœŸœ˜ψ—š œ˜KšŸœFœž ž7œŸœ ŸœUŸœ Ÿœ5ŸœŸœŸœ˜Ύ—KšœζŸœ˜μ—…—XD