<<-- 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.>> 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; <<-- VORONOI/DELAUNAY DIAGRAMS - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ->> 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) ]; <<-- 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)>> Org: PROC [e: Diag.DEdge] RETURNS [d: DVertex]; <<-- Origin DVertex of e.>> Dest: PROC [e: Diag.DEdge] RETURNS [d: DVertex]; <<-- Destination DVertex of e.>> Left: PROC [e: Diag.DEdge] RETURNS [v: VVertex]; <<-- Voronoi vertex at left of e.>> Right: PROC [e: Diag.DEdge] RETURNS [v: VVertex]; <<-- Voronoi vertex at right of e.>> <<-- PROCEDURES FOR CREATING AND MODIFYING DELAUNAY DIAGRAMS - - - - - - - - - - ->> TrivialDelaunay: PROC [pt: Homo.Point] RETURNS [dlau: Delaunay]; <<-- Creates a Delaunay diagram containing just a DVertex with coordinates p and a dummy VVertex (with indeterminate coordinates).>> InfiniteTriangle: PROC RETURNS [dlau: Delaunay]; <<-- 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.>> VVertexCoords: PROC [p, q, r: Homo.Point] RETURNS [vPt: Homo.Point]; <<-- 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.>> RenumberVertices: PROC [dlau: Delaunay]; <<-- 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 - - - - - - - - - - - - - - - - - - - - - >> DelaunayPainter, VertexPainter, RegionPainter, EdgePainter: Draw.PainterProc; MakeDelaunayObject: PROC [dlau: Delaunay, color: Draw.Color _ Gr.black] RETURNS [obj: Draw.Object] = INLINE <<-- 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.>> {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 <<-- 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.>> {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 <<-- 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.>> {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 <<-- 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.>> {RETURN [Draw.Make [RegionPainter, [data: e.rec, color: color, size: side, style: e.ix]]]}; <<-- DIAGRAM VALIDATION - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ->> CheckDelaunay: PROC [dg: Diag.DEdge]; <<-- 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.>> CheckFaceConvexity: PROC [dg: Diag.DEdge, convex: BOOL _ TRUE]; <<-- Prnts in the debug viewer all non-convex faces of the given delaunay. If convex = FALSE, prints all non-concave ones instead.>> END.