SaraP
458 lines
16 KiB
C++
458 lines
16 KiB
C++
/*****************************************************************************/
|
|
/* */
|
|
/* Copyright (C) 2001-2025 M. Held */
|
|
/* */
|
|
/* This code is not in the public domain. All rights reserved! Please make */
|
|
/* sure to read the full copyright statement contained in "README" or in the */
|
|
/* "main" file of this code, such as "main.cc". */
|
|
/* */
|
|
/*****************************************************************************/
|
|
/* */
|
|
/* Written by: Martin Held */
|
|
/* */
|
|
/* E-Mail: held@cs.sbg.ac.at */
|
|
/* Fax Mail: (+43 662) 8044-611 */
|
|
/* Voice Mail: (+43 662) 8044-6304 */
|
|
/* Snail Mail: Martin Held */
|
|
/* FB Informatik */
|
|
/* Universitaet Salzburg */
|
|
/* A-5020 Salzburg, Austria */
|
|
/* */
|
|
/*****************************************************************************/
|
|
|
|
/* */
|
|
/* get my header files */
|
|
/* */
|
|
#include "vroni_object.h"
|
|
|
|
#ifdef VRONI_INFO
|
|
#define IntWarning(S1, I1, S2, I2) \
|
|
{\
|
|
if (verbose) { \
|
|
printf("\nwarning in ComputeVD() - the %s %d and the %s %d intersect!\n",\
|
|
S1, I1, S2, I2); \
|
|
} \
|
|
}
|
|
#else
|
|
#define IntWarning(S1, I1, S2, I2) {}
|
|
#endif
|
|
|
|
/* */
|
|
/* find the Voronoi node on the Voronoi boundary of pnts[i] whose Voronoi */
|
|
/* disk is violated the most by the insertion of p. */
|
|
/* */
|
|
int vroniObject::FindMostViolatedNodePnt(int i, coord p)
|
|
{
|
|
int e, e0, k, k_min = NIL;
|
|
coord q;
|
|
double dist, dist_min, rad, rad_min;
|
|
|
|
e = GetPntVDPtr(i);
|
|
assert(InEdgesList(e));
|
|
assert(IsLftPnt(e, i) || IsRgtPnt(e, i));
|
|
|
|
if (IsRgtPnt(e, i)) k = GetEndNode(e);
|
|
else k = GetStartNode(e);
|
|
|
|
assert(InNodesList(k));
|
|
e0 = e;
|
|
dist_min = 1.0;
|
|
rad_min = 0.0;
|
|
|
|
/* */
|
|
/* scan the Voronoi cell in CCW order. */
|
|
/* */
|
|
do {
|
|
GetNodeData(k, &q, &rad);
|
|
dist = PntPntDistSq(p, q);
|
|
if (rad > dist) {
|
|
/* */
|
|
/* p is inside the Voronoi disk of nodes[k]. */
|
|
/* */
|
|
if (dist_min * rad > rad_min * dist) {
|
|
dist_min = dist;
|
|
rad_min = rad;
|
|
k_min = k;
|
|
}
|
|
}
|
|
e = GetCCWEdge(e, k);
|
|
k = GetOtherNode(e, k);
|
|
} while (e != e0);
|
|
|
|
if (k_min == NIL) {
|
|
VD_Warning("FindMostViolatedNodePnt() - no Voronoi disk violated!");
|
|
|
|
troubles = true;
|
|
|
|
if (IsInvalidData(true)) return NIL;
|
|
|
|
if (IsRgtPnt(e, i)) k = GetEndNode(e);
|
|
else k = GetStartNode(e);
|
|
dist_min = -DBL_MAX;
|
|
|
|
do {
|
|
GetNodeData(k, &q, &rad);
|
|
dist = sqrt(rad) - PntPntDist(p, q);
|
|
if (dist > dist_min) {
|
|
dist_min = dist;
|
|
rad_min = rad;
|
|
k_min = k;
|
|
}
|
|
e = GetCCWEdge(e, k);
|
|
k = GetOtherNode(e, k);
|
|
} while (e != e0);
|
|
}
|
|
|
|
return k_min;
|
|
}
|
|
|
|
|
|
|
|
void vroniObject::UpdateRecursivePnt(int i, int n, int e,
|
|
int *el, int *er, int *nl, int *nr)
|
|
{
|
|
int i0, i1, i2, n0, e0, k, k1, k2, e1, e2;
|
|
int e1r, n1r, e2l, n2l;
|
|
coord p, q, u, A, B, C;
|
|
double r2, dist, rad;
|
|
vr_bool delete_node;
|
|
|
|
k = GetOtherNode(e, n);
|
|
delete_node = false;
|
|
e1 = e2 = NIL;
|
|
|
|
if (IsNodeUnchecked(k)) {
|
|
/* */
|
|
/* only if this node has not yet been visited; make sure to avoid a */
|
|
/* loop! */
|
|
/* */
|
|
e1 = GetCCWEdge(e, k);
|
|
e2 = GetCWEdge(e, k);
|
|
k1 = GetEndNode(e1);
|
|
if (k1 == k) {
|
|
i1 = GetRgtSite(e1);
|
|
}
|
|
else {
|
|
assert(k == GetStartNode(e1));
|
|
i1 = GetLftSite(e1);
|
|
}
|
|
assert((IsLftPnt(e2, i1)) || (IsRgtPnt(e2, i1)));
|
|
|
|
if (i1 != NIL) {
|
|
if (!IsPntVisited(i1)) {
|
|
/* */
|
|
/* the Voronoi region of i1 has not yet been entered. we don't */
|
|
/* want to create two disconnected parts. */
|
|
/* */
|
|
k1 = GetOtherNode(e1, k);
|
|
k2 = GetOtherNode(e2, k);
|
|
|
|
if (!(IsNodeDeleted(k1) || IsNodeDeleted(k2))) {
|
|
/* */
|
|
/* only if removing k would not create a loop. */
|
|
/* */
|
|
GetNodeData(k, &q, &r2);
|
|
p = GetPntCoords(i);
|
|
dist = PntPntDistSq(p, q) - r2;
|
|
|
|
if (lt(dist, ZERO2)) {
|
|
/* */
|
|
/* the Delaunay circle of this node is violated by the */
|
|
/* insertion of p. */
|
|
/* */
|
|
SetPntVisited(i1, true);
|
|
AddPntVisited(i1);
|
|
MarkNodeDeleted(k);
|
|
#ifdef TRACE
|
|
#ifdef GRAPHICS
|
|
if (graphics) AddToCurBuffer(k, VDN, CurrColor);
|
|
#endif
|
|
#endif
|
|
delete_node = true;
|
|
}
|
|
else {
|
|
MarkNodeChecked(k);
|
|
AddNodeChecked(k);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if (delete_node) {
|
|
/* */
|
|
/* the Voronoi edge edges[e] is to be deleted; proceed recursively */
|
|
/* */
|
|
assert(e1 != NIL);
|
|
assert(e2 != NIL);
|
|
UpdateRecursivePnt(i, k, e1, el, &e1r, nl, &n1r);
|
|
if (restart) return;
|
|
UpdateRecursivePnt(i, k, e2, &e2l, er, &n2l, nr);
|
|
if (restart) return;
|
|
|
|
/* */
|
|
/* insert a new bisector and close a Voronoi cell. */
|
|
/* */
|
|
if (GetEndNode(e1r) == n1r) {
|
|
i0 = GetRgtSite(e1r);
|
|
}
|
|
else {
|
|
assert(GetStartNode(e1r) == n1r);
|
|
i0 = GetLftSite(e1r);
|
|
}
|
|
e0 = StoreEdge(n1r, n2l, i, i0, PNT, PNT);
|
|
#ifdef GRAPHICS
|
|
if (graphics) AddToCurBuffer(e0, VDE, VDCurrColor);
|
|
#endif
|
|
CloseVoronoiCell(e1r, e0, e2l, n1r, n2l);
|
|
|
|
/* */
|
|
/* make sure the VD edge pointer is up-to-date */
|
|
/* */
|
|
SetPntVDPtr(i0, e0);
|
|
|
|
/* */
|
|
/* delete edges[e] and nodes[k]. */
|
|
/* */
|
|
DeleteEdge(e);
|
|
DeleteNode(k);
|
|
}
|
|
else {
|
|
/* */
|
|
/* the Voronoi node nodes[k] is to be kept. insert a replacement */
|
|
/* node for nodes[n] (which will be deleted). */
|
|
/* */
|
|
i1 = GetLftSite(e);
|
|
i2 = GetRgtSite(e);
|
|
if (!PntPntPntCntr(i, i1, i2, &q, &r2)) {
|
|
troubles = true;
|
|
if (IsInvalidData(true)) {
|
|
restart = true;
|
|
return;
|
|
}
|
|
else {
|
|
GetNodeData(n, &u, &rad);
|
|
dist = PntPntDistSq(u, pnts[i].p) - rad;
|
|
if (eq(dist, ZERO)) {
|
|
q = u;
|
|
r2 = rad;
|
|
}
|
|
else {
|
|
A = GetPntCoords(i);
|
|
B = GetPntCoords(i1);
|
|
C = GetPntCoords(i2);
|
|
DesperatePntPntPntCntr(A, B, C, &q, &r2);
|
|
VD_Warning("UpdateRecursivePnt() - desperate mode for center used!\n");
|
|
desperate = true;
|
|
}
|
|
}
|
|
}
|
|
|
|
/* */
|
|
/* store the new node, and locally prepare the VD for the update. */
|
|
/* */
|
|
n0 = StoreNode(q.x, q.y, r2);
|
|
MarkNodeChecked(n0);
|
|
AddNodeChecked(n0);
|
|
UpdateNodeEdgeData(e, n, n0);
|
|
*el = *er = e;
|
|
*nl = *nr = n0;
|
|
#ifdef GRAPHICS
|
|
if (graphics) AddToCurBuffer(n0, VDN, CurrColor);
|
|
#endif
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
void vroniObject::InsertPntIntoVD(int i)
|
|
{
|
|
int j, i0, e0, e1, e2, e3;
|
|
int e1l, e1r, n1l, n1r, e2l, e2r, n2l, n2r, e3l, e3r, n3l, n3r;
|
|
int n, i1, i2, i3;
|
|
coord p;
|
|
double min_dist, EPS;
|
|
vr_bool grid_inserted;
|
|
|
|
|
|
assert(InPntsList(i));
|
|
EPS = ZERO2 * 100.0;
|
|
|
|
#ifdef GRAPHICS
|
|
if (graphics) {
|
|
ResetCurBuffer();
|
|
ResetVDBuffer();
|
|
MarkDrawSite(i, PNT);
|
|
AddToCurBuffer(i, PNT, SiteCurrColor);
|
|
}
|
|
#endif
|
|
|
|
#ifdef TRACE
|
|
printf("inserting pnt[%d]: (%20.16f %20.16f)\n", i,
|
|
GetPntCoords(i).x, GetPntCoords(i).y);
|
|
#endif
|
|
|
|
/* */
|
|
/* add pnts[i] to the grid or to the 2d-tree. */
|
|
/* */
|
|
grid_inserted = false;
|
|
if (grid_used) {
|
|
j = InsertPntIntoGrid(i, &min_dist);
|
|
/* */
|
|
/* find the nearest neighbor pnts[j] of point pnts[i]. */
|
|
/* */
|
|
if (grid_used && gt(min_dist, ZERO2)) {
|
|
grid_inserted = true;
|
|
j = FindNearestNeighborGrid(i, j, &min_dist);
|
|
}
|
|
}
|
|
else {
|
|
j = InsertPntIntoTree(i, &min_dist, false);
|
|
}
|
|
assert(InPntsList(j));
|
|
if (eq(min_dist, EPS)) {
|
|
if (grid_inserted) DeletePntFromGrid(i);
|
|
if ((GetPntCoords(i).x == GetPntCoords(j).x) &&
|
|
(GetPntCoords(i).y == GetPntCoords(j).y)) {
|
|
SetDeletedPnt(i, true); /* pnts[i].p == pnts[j].p !! */
|
|
if ((num_segs > 0) || (num_arcs > 0))
|
|
RepairPntLinks(i, j, false);
|
|
if (!restart) ++num_pnts_deleted;
|
|
}
|
|
else {
|
|
VD_Dbg_Warning("InsertPntIntoVD() - two points too close!");
|
|
IntWarning("pnt", i, "pnt", j);
|
|
MergePoints(i, j);
|
|
restart_due_to_intersection = numerical = true;
|
|
restart = true;
|
|
return;
|
|
}
|
|
return;
|
|
}
|
|
|
|
#ifdef GRAPHICS
|
|
#ifdef TRACE
|
|
if (graphics) {
|
|
AddCirToBuffer(GetPntCoords(i), sqrt(min_dist));
|
|
AddToCurBuffer(j, PNT, AlertColor);
|
|
}
|
|
#endif
|
|
#endif
|
|
|
|
/* */
|
|
/* find the nearest Voronoi node in the Voronoi cell of j. */
|
|
/* */
|
|
p = GetPntCoords(i);
|
|
n = FindMostViolatedNodePnt(j, p);
|
|
if (restart) return;
|
|
assert(InNodesList(n));
|
|
#ifdef GRAPHICS
|
|
#ifdef TRACE
|
|
if (graphics) AddToCurBuffer(n, VDN, CurrColor);
|
|
#endif
|
|
#endif
|
|
|
|
/* */
|
|
/* recursively discard all nodes and edges that are to be deleted. also, */
|
|
/* we insert the new Voronoi nodes and edges. */
|
|
/* */
|
|
e1 = GetIncidentEdge(n);
|
|
e2 = GetCCWEdge(e1, n);
|
|
e3 = GetCCWEdge(e2, n);
|
|
MarkNodeDeleted(n);
|
|
i1 = GetLftSite(e1);
|
|
i2 = GetRgtSite(e1);
|
|
i3 = GetLftSite(e2);
|
|
if ((i3 == i1) || (i3 == i2)) i3 = GetRgtSite(e2);
|
|
assert((i3 != i1) && (i3 != i2));
|
|
AddPntVisited(i1);
|
|
AddPntVisited(i2);
|
|
AddPntVisited(i3);
|
|
SetPntVisited(i1, true);
|
|
SetPntVisited(i2, true);
|
|
SetPntVisited(i3, true);
|
|
UpdateRecursivePnt(i, n, e1, &e1l, &e1r, &n1l, &n1r);
|
|
if (restart) return;
|
|
UpdateRecursivePnt(i, n, e2, &e2l, &e2r, &n2l, &n2r);
|
|
if (restart) return;
|
|
UpdateRecursivePnt(i, n, e3, &e3l, &e3r, &n3l, &n3r);
|
|
if (restart) return;
|
|
|
|
/* */
|
|
/* close the three Voronoi cells around nodes[n], which is to be deleted.*/
|
|
/* */
|
|
if (GetEndNode(e1r) == n1r) {
|
|
i0 = GetRgtSite(e1r);
|
|
}
|
|
else {
|
|
assert(GetStartNode(e1r) == n1r);
|
|
i0 = GetLftSite(e1r);
|
|
}
|
|
e0 = StoreEdge(n1r, n2l, i, i0, PNT, PNT);
|
|
|
|
/* */
|
|
/* make sure the VD edge pointer is up-to-date */
|
|
/* */
|
|
SetPntVDPtr(i0, e0);
|
|
|
|
#ifdef GRAPHICS
|
|
if (graphics) AddToCurBuffer(e0, VDE, VDCurrColor);
|
|
#endif
|
|
CloseVoronoiCell(e1r, e0, e2l, n1r, n2l);
|
|
if (GetEndNode(e2r) == n2r) {
|
|
i0 = GetRgtSite(e2r);
|
|
}
|
|
else {
|
|
assert(GetStartNode(e2r) == n2r);
|
|
i0 = GetLftSite(e2r);
|
|
}
|
|
e0 = StoreEdge(n2r, n3l, i, i0, PNT, PNT);
|
|
|
|
/* */
|
|
/* make sure the VD edge pointer is up-to-date */
|
|
/* */
|
|
SetPntVDPtr(i0, e0);
|
|
|
|
#ifdef GRAPHICS
|
|
if (graphics) AddToCurBuffer(e0, VDE, VDCurrColor);
|
|
#endif
|
|
CloseVoronoiCell(e2r, e0, e3l, n2r, n3l);
|
|
if (GetEndNode(e3r) == n3r) {
|
|
i0 = GetRgtSite(e3r);
|
|
}
|
|
else {
|
|
assert(GetStartNode(e3r) == n3r);
|
|
i0 = GetLftSite(e3r);
|
|
}
|
|
e0 = StoreEdge(n3r, n1l, i, i0, PNT, PNT);
|
|
|
|
/* */
|
|
/* make sure the VD edge pointer is up-to-date */
|
|
/* */
|
|
SetPntVDPtr(i0, e0);
|
|
|
|
#ifdef GRAPHICS
|
|
if (graphics) AddToCurBuffer(e0, VDE, VDCurrColor);
|
|
#endif
|
|
CloseVoronoiCell(e3r, e0, e1l, n3r, n1l);
|
|
|
|
/* */
|
|
/* delete node nodes[n] */
|
|
/* */
|
|
DeleteNode(n);
|
|
|
|
/* */
|
|
/* set the Voronoi pointer for site pnts[i] */
|
|
/* */
|
|
SetPntVDPtr(i, e0);
|
|
|
|
/* */
|
|
/* reset flags */
|
|
/* */
|
|
ResetPntVisited(j);
|
|
ResetNodeChecked(j);
|
|
|
|
return;
|
|
}
|