[Cyan]<PreISLCedar>Stolfi>COG>COGVoronoi.mesa!1

-- 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.