DIRECTORY COGCart USING [ScaleFactors], COGHomo USING [Point], Graphics USING [Context, black], COGDrawing USING [Drawing, Color, Object, Size, PainterProc, Make], COGDiagram USING [DEdge]; COGVoronoi: CEDAR DEFINITIONS IMPORTS COGDrawing, COGDiagram = BEGIN OPEN Cart: COGCart, Homo: COGHomo, Draw: COGDrawing, Gr: Graphics, Diag: COGDiagram; DVertex: TYPE = REF VertexRec; -- Delaunay vertex ( = data point) VVertex: TYPE = REF VertexRec; -- Voronoi vertex ( = Delaunay face) VertexRec: TYPE = -- Voronoi or Delaunay vertex RECORD [pt: Homo.Point, -- vertex coordinates no: VertexNo -- DVertex or VVertex id number (used for debugging) ]; VertexNo: TYPE = NAT; -- vertex number Delaunay: TYPE = REF DelaunayRec; DelaunayRec: TYPE = RECORD [dg: Diag.DEdge, -- an edge of the Dealunay diagram nDV, nVV: INT _ 0, -- number of Delaunay and Voronoi vertices in diagram -- The following data are used for debugging minDV, limDV: INT _ 0, -- numbers of DVertices should be in the range [minDV..limDV) minVV, limVV: INT _ 0 -- numbers of VVertices should be in the range [minVV..limVV) ]; Org: PROC [e: Diag.DEdge] RETURNS [d: DVertex]; Dest: PROC [e: Diag.DEdge] RETURNS [d: DVertex]; Left: PROC [e: Diag.DEdge] RETURNS [v: VVertex]; Right: PROC [e: Diag.DEdge] RETURNS [v: VVertex]; TrivialDelaunay: PROC [pt: Homo.Point] RETURNS [dlau: Delaunay]; InfiniteTriangle: PROC RETURNS [dlau: Delaunay]; VVertexCoords: PROC [p, q, r: Homo.Point] RETURNS [vPt: Homo.Point]; RenumberVertices: PROC [dlau: Delaunay]; DelaunayPainter, VertexPainter, RegionPainter, EdgePainter: Draw.PainterProc; MakeDelaunayObject: PROC [dlau: Delaunay, color: Draw.Color _ Gr.black] RETURNS [obj: Draw.Object] = INLINE {RETURN [Draw.Make [DelaunayPainter, [data: dlau, color: color]]]}; MakeVertexObject: PROC [v: REF VertexRec, color: Draw.Color _ Gr.black, side: Draw.Size _ 0] RETURNS [obj: Draw.Object] = INLINE {RETURN [Draw.Make [VertexPainter, [data: v, color: color, size: side]]]}; MakeEdgeObject: PROC [e: Diag.DEdge, color: Draw.Color _ Gr.black, width: Draw.Size _ 0] RETURNS [obj: Draw.Object] = INLINE {RETURN [Draw.Make [EdgePainter, [data: e.rec, color: color, size: width, style: e.ix]]]}; MakeRegionObject: PROC [e: Diag.DEdge, color: Draw.Color _ Gr.black, side: Draw.Size _ 0] RETURNS [obj: Draw.Object] = INLINE {RETURN [Draw.Make [RegionPainter, [data: e.rec, color: color, size: side, style: e.ix]]]}; CheckDelaunay: PROC [dg: Diag.DEdge]; CheckFaceConvexity: PROC [dg: Diag.DEdge, convex: BOOL _ TRUE]; END. ุ-- COGVoronoi.mesa: definition of Voronoi/Delaunay data structure -- last modified by Stolfi - October 15, 1982 4:11 pm -- To do: join with COGVorTest? -- To do: add local variants of ConnectDVertices, DeleteEdge, AddDVertex, CloseFace, etc. that update nDV, nVV, etc. and (maybe) do automatic ShowEdge, etc on global Drawing. -- VORONOI/DELAUNAY DIAGRAMS - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- PROCEDURES FOR WALKING ON DELAUNAY DIAGRAMS - - - - - - - - - - - - - - - - - - - -- In all the procedures in this section, e should be an edge of the Delaunay (i.e., Org[e] should be a Delaunay vertex, not a Voronoi one) -- Origin DVertex of e. -- Destination DVertex of e. -- Voronoi vertex at left of e. -- Voronoi vertex at right of e. -- PROCEDURES FOR CREATING AND MODIFYING DELAUNAY DIAGRAMS - - - - - - - - - - - -- Creates a Delaunay diagram containing just a DVertex with coordinates p and a dummy VVertex (with indeterminate coordinates). -- Creates a Delaunay diagram containing three points at the "Mercedes" infinities. The edge dlau.dg will be the one connecting the bottom two of these, from left to right. -- Computes the coordinates vp of the Voronoi vertex corresponding to a Delaunay region, given three c.c.w. consecutive vertices p, q, r of it. This is the circumcenter of the three points p, q, r, if they form a convex angle; otherwise, it is an infinity point lying to the left of pq and perpendicular to it. -- If the three points form a convex triangle, but one of them is at infinity, the returned vertex will also be at infinity, along the bisector of the other two. -- Renumbers all DVertices and VVertices (independently) from the current minDV and minVV, and sets limDV, limVV accordingly. If nDV and/or nVV are zero, will set them too; otherwise they must be exact. -- PROCEDURES FOR DRAWING DELAUNAY DIAGRAMS - - - - - - - - - - - - - - - - - - - - - -- Makes a Delaunay diagram into into a Drawing object that will paint itself either in the Delaunay or in the Voronoi form, depending on whether the drawing has the $Voronoi property. -- The properties $VNum and $ENum, if not NIL, will cause edge and vertex numbers to be painted too. The vertex numbers will refer to the Delaunay or Voronoi vertiices depending on the setting of $Voronoi. -- Makes a Drawing object that will paint a given vertex (voronoi or delaunay) as a small square of given side. -- Will paint the vertex number if the property $VNum is not NIL. -- Makes a Drawing object that will paint a delaunay edge e either in the Delaunay or in the Voronoi form, depending on whether the drawing has the $Voronoi property. -- Wiil also paint the edge number if the proeprty $ENum is not NIL. -- Makes a Drawing object that will paint either Org[e] as a small square of given side, or the Voronoi region for Org[e] as a polygon of given color, depending on whether the drawing has the $Voronoi property. In either case, e must be a Delaunay edge, i.e., Org[e][ must be a DVertex. -- If $VNum is not NIL, the number of the Delaunay vertex will be painted in any case, independently of the setting of $Voronoi. -- DIAGRAM VALIDATION - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- For every edge of the Delaunay whose adjacent faces are convex (in the appropriate directions) satisfies the quadrilateral condition. Errors are printed in the debug viewer. -- Prnts in the debug viewer all non-convex faces of the given delaunay. If convex = FALSE, prints all non-concave ones instead. ส%– "Mesa" style˜Iprocšฯcะbc/™Aš5™5KšœฯbœŸ™KšŸ œค™ฎ—Kš ฯk œ  œ œ œ  œA œ ˜วKš Ÿ œ œ  œ œ œ œV˜ขK˜KšZ™ZKšŸœ œ œ "˜AKšŸœ œ œ $˜CKš Ÿ œ œœ œœ5œ˜ดKšŸœ œ œ˜&KšŸœ œ œ ˜!KšŸ œ œ œ#œ  œ6œ-œ œ>œ œ>œ˜K˜šT™TKš*ž`™‹—šฯnœ œ œ˜/Kš œ ž™—šกœ œ œ˜0Kšœ ž™—šกœ œ œ˜0Kšž™—šกœ œ œ˜1Kšž™ —K˜KšP™Pšกœ œ œ˜@KšIž6™€—šกœ œ œ˜0Kšฌ™ฌ—šก œ œ œ˜EKšžcžžž5žžžWž™ทK™ก—šกœ œ˜)Kšž ž "žž žžžž;™ห—K˜KšV™VK˜KšŸœŸ œŸ œŸ œ˜Mšะbnœ œ1 œ ˜lKš)žxžœ™บKšœŸœŸœฃŸœ™อKšœ œ<˜C—š ขœ œ œ@ œ ˜Kš ž]™oKšœ0Ÿœ ™AKšœ œC˜J—šขœ œF œ ˜}Kš  ž(žYžœ™งKšœ3Ÿœ ™DKšœ œS˜Z—šขœ œE œ ˜~Kš žžž=žœžHžœž ž žž ž™ŸKšœŸœlŸœ™€Kšœ œT˜[—K˜Kša™aK˜šข œ œ ˜%Kšœญ™ฐ—šขœ œ œ œ˜?Kšœ}™€—Kšœ œ˜J˜—…—