SaraP
1123 lines
35 KiB
C++
1123 lines
35 KiB
C++
/*****************************************************************************/
|
|
/* */
|
|
/* Copyright (C) 1999-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.txt" 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-172 */
|
|
/* Voice Mail: (+43 662) 8044-6304 */
|
|
/* Snail Mail: Martin Held */
|
|
/* FB Informatik */
|
|
/* Universitaet Salzburg */
|
|
/* A-5020 Salzburg, Austria */
|
|
/* */
|
|
/*****************************************************************************/
|
|
|
|
/* */
|
|
/* get standard libraries */
|
|
/* */
|
|
#include <stdlib.h>
|
|
#include <stdio.h>
|
|
#include <assert.h>
|
|
#include <float.h>
|
|
#include <math.h>
|
|
|
|
/* */
|
|
/* get my header files */
|
|
/* */
|
|
#include "fpkernel.h"
|
|
#include "vronivector.h"
|
|
#include "vroni_object.h"
|
|
#include "defs.h"
|
|
#include "numerics.h"
|
|
#include "roots.h"
|
|
#include "intersections.h"
|
|
|
|
|
|
|
|
#define INCR 0.0001
|
|
|
|
|
|
|
|
#ifdef GRAPHICS
|
|
#define HandleSplitArc(I, J, K) \
|
|
{\
|
|
K = SplitArc(I, J); \
|
|
if (graphics) { \
|
|
AddToCurBuffer(I, ARC, AlertColor); \
|
|
AddToCurBuffer(K, ARC, AlertColor); \
|
|
AddToCurBuffer(J, PNT, AlertColor); \
|
|
}\
|
|
}
|
|
#else
|
|
#define HandleSplitArc(I, J, K) \
|
|
{\
|
|
(void) SplitArc(I, J); \
|
|
}
|
|
#endif
|
|
|
|
#ifdef GRAPHICS
|
|
#define HandleSplitSeg(I, J, K) \
|
|
{\
|
|
K = SplitSeg(I, J); \
|
|
if (graphics) { \
|
|
AddToCurBuffer(I, SEG, AlertColor); \
|
|
AddToCurBuffer(K, SEG, AlertColor); \
|
|
AddToCurBuffer(J, PNT, AlertColor); \
|
|
}\
|
|
}
|
|
#else
|
|
#define HandleSplitSeg(I, J, K) \
|
|
{\
|
|
(void) SplitSeg(I, J); \
|
|
}
|
|
#endif
|
|
|
|
|
|
void vroniObject::ResetIntersectionData(void)
|
|
{
|
|
invalid_i1 = NIL;
|
|
invalid_i2 = NIL;
|
|
invalid_t1 = UNKNOWN;
|
|
invalid_t2 = UNKNOWN;
|
|
invalid_eps = ZERO;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
/* */
|
|
/* for every pair of point sites, this routine adds their midpoint as a */
|
|
/* degree-2 node if this mid-point lies on their common Voronoi edge. */
|
|
/* */
|
|
void vroniObject::InsertDegreeTwoNodes(void)
|
|
{
|
|
coord p, q, u, v, w;
|
|
int i, j, e, k, n, m, s_u, s_v, number;
|
|
double det_u, det_v, r;
|
|
t_site ti, tj;
|
|
|
|
number = GetNumberOfEdges();
|
|
|
|
for (e = 0; e < number; ++e) {
|
|
assert(InEdgesList(e));
|
|
if (!IsEdgeDeleted(e)) {
|
|
k = GetStartNode(e);
|
|
n = GetEndNode(e);
|
|
assert(InNodesList(k));
|
|
assert(InNodesList(n));
|
|
if (!(IsDeg2Node(k) || IsDeg2Node(n))) {
|
|
GetLftSiteData(e, &i, &ti);
|
|
GetRgtSiteData(e, &j, &tj);
|
|
if ((ti == PNT) && (tj == PNT)) {
|
|
assert(InPntsList(i));
|
|
assert(InPntsList(j));
|
|
/* */
|
|
/* check whether mid-point of pnts[i] and pnts[j] belongs */
|
|
/* to their common VD edge. if yes, insert a degree-2 node at */
|
|
/* this point in order to split the VD edge into two subedges.*/
|
|
/* */
|
|
p = GetPntCoords(i);
|
|
q = GetPntCoords(j);
|
|
GetNodeData(k, &u, &r);
|
|
det_u = VecDet(p, q, u);
|
|
s_u = Sign(det_u);
|
|
if (s_u == -1) {
|
|
GetNodeData(n, &v, &r);
|
|
det_v = VecDet(p, q, v);
|
|
s_v = Sign(det_v);
|
|
if (s_v == 1) {
|
|
/* */
|
|
/* the nodes k and n lie on different sides of the */
|
|
/* line through pnts[i] and pnts[j]. thus, the */
|
|
/* mid-point belongs to the VD edge. we insert the */
|
|
/* mid-point as a degree-2 node. */
|
|
/* */
|
|
w = MidPoint(p, q);
|
|
m = StoreNode(w.x, w.y, PntPntDist(p, q) / 2.0);
|
|
InsertDummyNode(e, m, false);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
SetDeg2Flag();
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
/* */
|
|
/* set the stepping increment for VRONI's approximation of conic VD edges. */
|
|
/* please note that this approximation is used by VRONI for nothing but */
|
|
/* graphics purposes. if you use it for anything else then this is entirely */
|
|
/* your decision. in particular, the exterior-application macro */
|
|
/* "SetStepSize" let's you can increase or decrease VRONI's default stepping */
|
|
/* increment; don't complain to me if things don't look good once VRONI's */
|
|
/* defaults have been modified. in any case, please note that VRONI's */
|
|
/* approximation of conics is not based on any mathematical considerations */
|
|
/* of the approximation distance achieved. */
|
|
/* */
|
|
void vroniObject::SetStepSize(double_arg delta)
|
|
{
|
|
misc_step_size = delta * INCR / sqrt(sqrt((double) num_pnts));
|
|
|
|
/* let the user influence the stepping increment */
|
|
ExtApplSetStepSize;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
// MODIF nel caso di bisettori a parabola e iperellisse quando viene chiamata la funzione
|
|
// AddEdgeToBuffer vengono passati anche i parametri in cui sono calcolati i due punti del
|
|
// bisettore
|
|
|
|
#ifdef GRAPHICS
|
|
|
|
#ifndef API_PARABOLIC
|
|
void vroniObject::AddParabolaToBuffer(int i, double t1, double t2,
|
|
coord u, coord v, int color)
|
|
{
|
|
int i1, i2;
|
|
coord w, w0;
|
|
double a, b, c, A, B, t, dist, sign, k1, k2, r, incr, d1, d2;
|
|
t_site site_type, arc_type;
|
|
e_formula coeff;
|
|
vr_bool increasing = true;
|
|
|
|
GetLftSiteData(i, &i1, &site_type);
|
|
if (site_type == SEG) {
|
|
GetRgtSiteData(i, &i2, &arc_type);
|
|
assert((arc_type == PNT) || (arc_type == ARC));
|
|
}
|
|
else {
|
|
arc_type = site_type;
|
|
assert((arc_type == PNT) || (arc_type == ARC));
|
|
i2 = i1;
|
|
GetRgtSiteData(i, &i1, &site_type);
|
|
assert(site_type == SEG);
|
|
}
|
|
|
|
if (arc_type == PNT) {
|
|
if (IsSegStartPnt(i1, i2) || IsSegEndPnt(i1, i2)) {
|
|
AddEdgeToBuffer(u.x, u.y, v.x, v.y, color, t1, t2);
|
|
return;
|
|
}
|
|
}
|
|
|
|
if (!ComputeParabolaData(i, &coeff)) {
|
|
/* */
|
|
/* degenerate Voronoi edge */
|
|
/* */
|
|
AddEdgeToBuffer(u.x, u.y, v.x, v.y, color, t1, t2);
|
|
}
|
|
else {
|
|
GetSegEqnData(i1, &a, &b, &c);
|
|
A = coeff.A;
|
|
B = coeff.B;
|
|
dist = coeff.d;
|
|
if (coeff.sign) sign = 1.0;
|
|
else sign = -1.0;
|
|
if (coeff.k1) k1 = 1.0;
|
|
else k1 = -1.0;
|
|
if (coeff.k2) k2 = 1.0;
|
|
else k2 = -1.0;
|
|
if (arc_type == PNT) r = 0.0;
|
|
else r = GetArcRadius(i2);
|
|
|
|
if (t1 > t2) {
|
|
VroniSwap(t1, t2, t);
|
|
VroniSwap(u, v, w);
|
|
}
|
|
|
|
t = PntPntDist(u, v) / misc_step_size;
|
|
if (t < 1.0) t = 1.0;
|
|
incr = (t2 - t1) / t;
|
|
if ((arc_type == ARC) && (t > 4.0)) {
|
|
t = t1 + incr;
|
|
xParabola(A, a, b, sign, dist, t, k1, k2, r, w0.x);
|
|
yParabola(B, a, b, sign, dist, t, k1, k2, r, w0.y);
|
|
d1 = PntPntDistSq(u, w0);
|
|
t = t2 - incr;
|
|
xParabola(A, a, b, sign, dist, t, k1, k2, r, w0.x);
|
|
yParabola(B, a, b, sign, dist, t, k1, k2, r, w0.y);
|
|
d2 = PntPntDistSq(v, w0);
|
|
if (d2 > d1) increasing = false;
|
|
}
|
|
if (increasing) {
|
|
t2 -= (incr / 10.0);
|
|
t = incr + t1;
|
|
w = u;
|
|
while (t < t2) {
|
|
xParabola(A, a, b, sign, dist, t, k1, k2, r, w0.x);
|
|
yParabola(B, a, b, sign, dist, t, k1, k2, r, w0.y);
|
|
AddEdgeToBuffer(w.x, w.y, w0.x, w0.y, color, t - incr, t);
|
|
w = w0;
|
|
incr *= 1.1;
|
|
t += incr;
|
|
}
|
|
AddEdgeToBuffer(w.x, w.y, v.x, v.y, color, t - incr, t2);
|
|
}
|
|
else {
|
|
t1 += (incr / 10.0);
|
|
t = t2 - incr;
|
|
w = v;
|
|
while (t > t1) {
|
|
xParabola(A, a, b, sign, dist, t, k1, k2, r, w0.x);
|
|
yParabola(B, a, b, sign, dist, t, k1, k2, r, w0.y);
|
|
AddEdgeToBuffer(w.x, w.y, w0.x, w0.y, color, t + incr, t);
|
|
w = w0;
|
|
incr *= 1.1;
|
|
t -= incr;
|
|
}
|
|
AddEdgeToBuffer(w.x, w.y, u.x, u.y, color, t + incr, t1);
|
|
}
|
|
}
|
|
|
|
return;
|
|
}
|
|
#endif
|
|
#endif
|
|
|
|
|
|
|
|
#ifdef GRAPHICS
|
|
#ifdef GENUINE_ARCS
|
|
/**
|
|
* i ... Index of Voronoi edge to add bisector of
|
|
* u, t1 ... coordinate and Delaunay-radius of start-node of edge i
|
|
* v, t2 ... coordinate and Delaunay-radius of end-node of edge i
|
|
*
|
|
* --> Draw hyperbola / ellipse through u and v, representing the edge i
|
|
*
|
|
**/
|
|
void vroniObject::AddHyperbolaEllipseToBuffer(int i, double t1, double t2,
|
|
coord u, coord v, int color)
|
|
{
|
|
e_formula coeff;
|
|
int i1, i2, i3;
|
|
t_site ltype, rtype, itype;
|
|
double r1, r2;
|
|
coord p1, p2, p, w, w0;
|
|
double A, B, C, D, dist;
|
|
double r1t, r2t, dx, dy, ht, du, dv;
|
|
double k1, k2, sign, d1, d2;
|
|
double t, angle_s, angle_e, alpha, incr, radius, delta;
|
|
vr_bool increasing = false;
|
|
|
|
GetLftSiteData(i, &i1, <ype);
|
|
GetRgtSiteData(i, &i2, &rtype);
|
|
assert((ltype == PNT) || (ltype == ARC));
|
|
assert((rtype == PNT) || (rtype == ARC));
|
|
|
|
if (i2 > i1) {
|
|
VroniSwap(i1, i2, i3);
|
|
VroniSwap(ltype, rtype, itype);
|
|
}
|
|
else if (i1 == i2) {
|
|
if (rtype == PNT) {
|
|
VroniSwap(i1, i2, i3);
|
|
VroniSwap(ltype, rtype, itype);
|
|
}
|
|
}
|
|
|
|
if (ltype == PNT) {
|
|
if (rtype == ARC) {
|
|
if (IsArcStartPnt(i2, i1) || IsArcEndPnt(i2, i1)) {
|
|
AddEdgeToBuffer(u.x, u.y, v.x, v.y, color, t1, t2);
|
|
return;
|
|
}
|
|
}
|
|
r1 = 0.0;
|
|
p1 = GetPntCoords(i1);
|
|
}
|
|
else {
|
|
r1 = GetArcRadius(i1);
|
|
p1 = GetArcCenter(i1);
|
|
}
|
|
if (rtype == PNT) {
|
|
if (ltype == ARC) {
|
|
if (IsArcStartPnt(i1, i2) || IsArcEndPnt(i1, i2)) {
|
|
AddEdgeToBuffer(u.x, u.y, v.x, v.y, color, t1, t2);
|
|
return;
|
|
}
|
|
}
|
|
r2 = 0.0;
|
|
p2 = GetPntCoords(i2);
|
|
}
|
|
else {
|
|
r2 = GetArcRadius(i2);
|
|
p2 = GetArcCenter(i2);
|
|
}
|
|
|
|
dx = p2.x - p1.x;
|
|
dy = p2.y - p1.y;
|
|
|
|
if (!ComputeHyperbolaEllipseData(i, &coeff)) {
|
|
/* */
|
|
/* degenerate Voronoi edge */
|
|
/* */
|
|
dist = dx * dx + dy * dy;
|
|
if (eq(dist, ZERO_MAX)) {
|
|
dist = r1 - r2;
|
|
if (eq(dist, ZERO_MAX)) {
|
|
/* */
|
|
/* straight-line segment */
|
|
/* */
|
|
AddEdgeToBuffer(u.x, u.y, v.x, v.y, color, t1, t2);
|
|
}
|
|
else {
|
|
/* */
|
|
/* degenerate elliptic edge */
|
|
/* */
|
|
p = MidPoint(p1, p2);
|
|
if (VecDet(p, u, v) < 0.0) {
|
|
VroniSwap(u, v, w);
|
|
VroniSwap(t1, t2, t);
|
|
}
|
|
angle_s = atan2(u.y - p.y, u.x - p.x);
|
|
angle_e = atan2(v.y - p.y, v.x - p.x);
|
|
if (angle_s < 0.0) angle_s += M_2PI;
|
|
if (angle_e < 0.0) angle_e += M_2PI;
|
|
if (angle_e < angle_s) angle_e += M_2PI;
|
|
w = u;
|
|
du = PntPntDist(p, u);
|
|
dv = PntPntDist(p, v);
|
|
radius = (du + dv) / 2.0;
|
|
if (eq(radius, ZERO)) {
|
|
AddEdgeToBuffer(u.x, u.y, v.x, v.y, color, t1, t2);
|
|
}
|
|
else {
|
|
t = PntPntDist(u, v) / misc_step_size;
|
|
if (t <= 1.0) {
|
|
AddEdgeToBuffer(u.x, u.y, v.x, v.y, color, t1, t2);
|
|
}
|
|
else {
|
|
if (t < 2.0) t = 2.0;
|
|
incr = 1.0 / t;
|
|
assert((0.0 < incr) && (incr < 1.0));
|
|
delta = incr;
|
|
alpha = (1.0 - incr) * angle_s + incr * angle_e;
|
|
do {
|
|
radius = (1.0 - delta) * du + delta * dv;
|
|
w0.x = p.x + radius * cos(alpha);
|
|
w0.y = p.y + radius * sin(alpha);
|
|
AddEdgeToBuffer(w.x, w.y, w0.x, w0.y, color, t1, t1);
|
|
w = w0;
|
|
delta += incr;
|
|
alpha = (1.0 - delta) * angle_s + delta * angle_e;
|
|
} while (alpha < angle_e);
|
|
AddEdgeToBuffer(w.x, w.y, v.x, v.y, color, t1, t1);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
else {
|
|
/* */
|
|
/* degenerate hyperbolic edge */
|
|
/* */
|
|
AddEdgeToBuffer(u.x, u.y, v.x, v.y, color, t1, t2);
|
|
}
|
|
}
|
|
else {
|
|
dist = coeff.d;
|
|
dx /= dist;
|
|
dy /= dist;
|
|
A = coeff.A;
|
|
B = coeff.B;
|
|
C = coeff.C;
|
|
D = coeff.D;
|
|
if (coeff.k1) k1 = 1.0;
|
|
else k1 = -1.0;
|
|
if (coeff.k2) k2 = 1.0;
|
|
else k2 = -1.0;
|
|
if (coeff.sign) sign = 1.0;
|
|
else sign = -1.0;
|
|
|
|
if (t1 > t2) {
|
|
VroniSwap(t1, t2, t);
|
|
VroniSwap(u, v, w);
|
|
}
|
|
|
|
t = PntPntDist(u, v) / misc_step_size;
|
|
if (t < 1.0) t = 1.0;
|
|
incr = (t2 - t1) / t;
|
|
if (t > 4.0) {
|
|
t = t1 + incr;
|
|
xHyperEll(A, C, sign, dist, dy, t, k1, k2, r1, r2, r1t, r2t, ht,
|
|
w0.x);
|
|
yHyperEll(B, D, sign, dist, dx, t, k1, k2, r1, r2, r1t, r2t, ht,
|
|
w0.y);
|
|
d1 = PntPntDistSq(u, w0);
|
|
t = t2 - incr;
|
|
xHyperEll(A, C, sign, dist, dy, t, k1, k2, r1, r2, r1t, r2t, ht,
|
|
w0.x);
|
|
yHyperEll(B, D, sign, dist, dx, t, k1, k2, r1, r2, r1t, r2t, ht,
|
|
w0.y);
|
|
d2 = PntPntDistSq(v, w0);
|
|
if (d1 > d2) increasing = true;
|
|
}
|
|
if (increasing) {
|
|
t2 -= (incr / 10.0);
|
|
t = t1 + incr;
|
|
w = u;
|
|
while (t < t2) {
|
|
xHyperEll(A, C, sign, dist, dy, t, k1, k2, r1, r2, r1t, r2t, ht,
|
|
w0.x);
|
|
yHyperEll(B, D, sign, dist, dx, t, k1, k2, r1, r2, r1t, r2t, ht,
|
|
w0.y);
|
|
AddEdgeToBuffer(w.x, w.y, w0.x, w0.y, color, t - incr, t);
|
|
w = w0;
|
|
incr *= 1.05;
|
|
t += incr;
|
|
}
|
|
AddEdgeToBuffer(w.x, w.y, v.x, v.y, color, t - incr, t2);
|
|
}
|
|
else {
|
|
t1 += (incr / 10.0);
|
|
t = t2 - incr;
|
|
w = v;
|
|
while (t > t1) {
|
|
xHyperEll(A, C, sign, dist, dy, t, k1, k2, r1, r2, r1t, r2t, ht,
|
|
w0.x);
|
|
yHyperEll(B, D, sign, dist, dx, t, k1, k2, r1, r2, r1t, r2t, ht,
|
|
w0.y);
|
|
AddEdgeToBuffer(w.x, w.y, w0.x, w0.y, color, t + incr, t);
|
|
w = w0;
|
|
incr *= 1.05;
|
|
t -= incr;
|
|
}
|
|
AddEdgeToBuffer(w.x, w.y, u.x, u.y, color, t + incr, t1);
|
|
}
|
|
}
|
|
|
|
return;
|
|
}
|
|
#endif
|
|
#endif
|
|
|
|
|
|
double vroniObject::NodeSegClassificator(int i, coord p)
|
|
{
|
|
coord u;
|
|
double alpha, lgth, a, b, c;
|
|
|
|
u = GetSegStartCoord(i);
|
|
GetSegEqnData(i, &a, &b, &c);
|
|
lgth = GetSegLgth(i);
|
|
//Projecting p on the segment and determine distance
|
|
//to u
|
|
alpha = (p.x-u.x)*b - (p.y-u.y)*a;
|
|
if (alpha < 0.0) return (- alpha);
|
|
else if (alpha <= lgth) return 0.0;
|
|
else return (alpha - lgth);
|
|
}
|
|
|
|
|
|
|
|
double vroniObject::NodeSidednessClassificator(int i, t_site ti, /* old site */
|
|
const coord & q, /* old node */
|
|
const coord & p) /* new node */
|
|
{
|
|
double qual = LARGE, dist1, dist2;
|
|
coord c;
|
|
double a, b, d, r;
|
|
|
|
switch(ti) {
|
|
case PNT:
|
|
qual = 0.0;
|
|
break;
|
|
case SEG:
|
|
GetSegEqnData(i, &a, &b, &d);
|
|
dist2 = PntLineDist(a, b, d, p);
|
|
if (eq(dist2, ZERO_MAX)) qual = 0.0;
|
|
else {
|
|
dist1 = PntLineDist(a, b, d, q);
|
|
if (eq(dist1, ZERO_MAX)) qual = 0.0;
|
|
else {
|
|
if (((dist1 < 0.0) && (dist2 < 0.0)) ||
|
|
((dist1 > 0.0) && (dist2 > 0.0))) qual = 0.0;
|
|
else qual = Abs(dist2);
|
|
}
|
|
}
|
|
break;
|
|
case ARC:
|
|
c = GetArcCenter(i);
|
|
r = GetArcRadius(i);
|
|
dist2 = PntCircleDist(c, r, p);
|
|
if (eq(dist2, ZERO_MAX)) qual = 0.0;
|
|
else {
|
|
dist1 = PntCircleDist(c, r, q);
|
|
if (eq(dist1, ZERO_MAX)) qual = 0.0;
|
|
else {
|
|
if (((dist1 < 0.0) && (dist2 < 0.0)) ||
|
|
((dist1 > 0.0) && (dist2 > 0.0))) qual = 0.0;
|
|
else qual = Abs(dist2);
|
|
}
|
|
}
|
|
break;
|
|
default:
|
|
assert(0);
|
|
}
|
|
|
|
return qual;
|
|
}
|
|
|
|
|
|
double vroniObject::NodeEdgeClassificator(int e, const coord & p, double eps)
|
|
{
|
|
int i1, i2, n1, n2;
|
|
t_site t1, t2;
|
|
coord q1, q2, q3;
|
|
double d1, d2, d3, d4, r1, r2;
|
|
|
|
/* */
|
|
/* Get start and end nodes (and their coordinates) of edge */
|
|
/* */
|
|
n1 = GetStartNode(e);
|
|
n2 = GetEndNode(e);
|
|
GetNodeData(n1, &q1, &r1);
|
|
GetNodeData(n2, &q2, &r2);
|
|
|
|
/* */
|
|
/* get the defining sites of this VD edge */
|
|
/* */
|
|
GetLftSiteData(e, &i1, &t1);
|
|
GetRgtSiteData(e, &i2, &t2);
|
|
|
|
/* */
|
|
/* check whether the new node is in the cones/strips defined by the old */
|
|
/* nodes */
|
|
/* */
|
|
d1 = PntSiteConeClassificator(i1, t1, q2, q1, p, eps);
|
|
d2 = PntSiteConeClassificator(i2, t2, q1, q2, p, eps);
|
|
|
|
/* */
|
|
/* check whether the new node is on the same side of i1 and i2 as the */
|
|
/* old nodes */
|
|
/* */
|
|
if (gt(VroniMax(r1, r2), ZERO)) {
|
|
if (r1 >= r2) q3 = q1;
|
|
else q3 = q2;
|
|
if (t1 != PNT) d3 = NodeSidednessClassificator(i1, t1, q3, p);
|
|
else d3 = 0.0;
|
|
if (t2 != PNT) d4 = NodeSidednessClassificator(i2, t2, q3, p);
|
|
else d4 = 0.0;
|
|
}
|
|
else {
|
|
d3 = d4 = 0.0;
|
|
}
|
|
|
|
#ifdef TRACE
|
|
printf("e = %d, i1/t1 = %d/%d, i2/t2 = %d/%d\n", e, i1, t1, i2, t2);
|
|
printf("q1 = (%20.16f %20.16f)\n", q1.x, q1.y);
|
|
printf("q2 = (%20.16f %20.16f)\n", q2.x, q2.y);
|
|
printf("p = (%20.16f %20.16f)\n", p.x, p.y);
|
|
printf("d1 = %20.16f, d2 = %20.16f\n", d1, d2);
|
|
printf("d3 = %20.16f, d4 = %20.16f\n", d3, d4);
|
|
#endif
|
|
|
|
d1 = Abs(d1);
|
|
d2 = Abs(d2);
|
|
|
|
return Max4(d1, d2, d3, d4);
|
|
}
|
|
|
|
|
|
|
|
|
|
void vroniObject::SplitAtIntersection(int i1, int i2, t_site t1, t_site t2,
|
|
coord w)
|
|
{
|
|
int i3;
|
|
#ifdef GRAPHICS
|
|
int i4;
|
|
#endif
|
|
|
|
#ifdef EXT_APPL_PNTS
|
|
i3 = HandlePnt(w.x, w.y, eap_NIL);
|
|
#else
|
|
i3 = HandlePnt(w.x, w.y);
|
|
#endif
|
|
|
|
if (t1 == SEG) {
|
|
HandleSplitSeg(i1, i3, i4);
|
|
}
|
|
#ifdef GENUINE_ARCS
|
|
else {
|
|
assert(t1 == ARC);
|
|
HandleSplitArc(i1, i3, i4);
|
|
}
|
|
#endif
|
|
|
|
if (t2 == SEG) {
|
|
HandleSplitSeg(i2, i3, i4);
|
|
}
|
|
#ifdef GENUINE_ARCS
|
|
else if (t2 == ARC) {
|
|
HandleSplitArc(i2, i3, i4);
|
|
}
|
|
#endif
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
vr_bool vroniObject::IsPntOnPnt(int i1, int i2, double eps)
|
|
{
|
|
if (CheckPntPnt(i1, i2, eps)) {
|
|
IntWarning("pnt", i1, "pnt", i2);
|
|
MergePoints(i1, i2);
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
vr_bool vroniObject::IsPntOnSeg(int i1, int i2, double eps)
|
|
{
|
|
#ifdef GRAPHICS
|
|
int i3;
|
|
#endif
|
|
|
|
if (CheckPntOnSeg(i1, i2, eps)) {
|
|
HandleSplitSeg(i1, i2, i3);
|
|
ExtApplSegPntIntersection; /* external-application macro */
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
|
|
|
|
#ifdef GENUINE_ARCS
|
|
vr_bool vroniObject::IsPntOnArc(int i1, int i2, double eps)
|
|
{
|
|
#ifdef GRAPHICS
|
|
int i3;
|
|
#endif
|
|
|
|
if (CheckPntOnArc(i1, i2, eps)) {
|
|
HandleSplitArc(i1, i2, i3);
|
|
ExtApplArcPntIntersection; /* external-application macro */
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
#endif
|
|
|
|
|
|
|
|
|
|
/* */
|
|
/* check (and compute) the intersection of seg i1 and seg i2, and split */
|
|
/* the sites accordingly. */
|
|
/* */
|
|
/* note: (1) emphasis is placed on reliability rather than speed! */
|
|
/* (2) an iterative solver is used if the analytical computation of */
|
|
/* the points of intersection does not yield accurate results. */
|
|
/* (3) it is assumed that a pnt-on-seg test has been carried out prior */
|
|
/* to calling this routine. */
|
|
/* */
|
|
vr_bool vroniObject::IsSegSegIntersection(int i1, int i2, double eps)
|
|
{
|
|
coord w;
|
|
vr_bool ident = false;
|
|
|
|
if (GetSegSegIntersection(i1, i2, &w, eps, &ident)) {
|
|
ExtApplSegSegIntersection; /* external-application macro */
|
|
SplitAtIntersection(i1, i2, SEG, SEG, w);
|
|
return true;
|
|
}
|
|
else if (ident) {
|
|
/* */
|
|
/* oops, this seg is stored twice! we remove one copy. */
|
|
/* */
|
|
IntWarning("seg", i1, "seg", i2);
|
|
ExtApplSegSegIntersection; /* external-application macro */
|
|
RemoveSegment(i2);
|
|
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
|
|
|
|
/* */
|
|
/* check (and compute) the intersection of seg i1 and arc i2, and split */
|
|
/* the sites accordingly. */
|
|
/* */
|
|
/* note: (1) emphasis is placed on reliability rather than speed! */
|
|
/* (2) an iterative solver is used if the analytical computation of */
|
|
/* the points of intersection does not yield accurate results. */
|
|
/* (3) it is assumed that a pnt-on-seg and pnt-on-arc test has been */
|
|
/* carried out. */
|
|
/* */
|
|
#ifdef GENUINE_ARCS
|
|
vr_bool vroniObject::IsSegArcIntersection(int i1, int i2, double eps)
|
|
{
|
|
coord w1, w2;
|
|
|
|
if (GetSegArcIntersection(i1, i2, &w1, &w2, eps) > 0) {
|
|
SplitAtIntersection(i1, i2, SEG, ARC, w1);
|
|
ExtApplSegArcIntersection; /* external-application macro */
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
#endif
|
|
|
|
|
|
|
|
/* */
|
|
/* check (and compute) the intersection of arc i1 and arc i2, and split */
|
|
/* the sites accordingly. */
|
|
/* */
|
|
/* note: (1) emphasis is placed on reliability rather than speed! */
|
|
/* (2) an iterative solver is used if the analytical computation of */
|
|
/* the points of intersection does not yield accurate results. */
|
|
/* (3) it is assumed that a pnt-on-arc test has been carried out. */
|
|
/* */
|
|
#ifdef GENUINE_ARCS
|
|
vr_bool vroniObject::IsArcArcIntersection(int i1, int i2, double eps)
|
|
{
|
|
coord w1, w2;
|
|
vr_bool ident = false;
|
|
|
|
if (GetArcArcIntersection(i1, i2, &w1, &w2, eps, &ident) > 0) {
|
|
SplitAtIntersection(i1, i2, ARC, ARC, w1);
|
|
ExtApplArcArcIntersection; /* external-application macro */
|
|
return true;
|
|
}
|
|
else if (ident) {
|
|
/* */
|
|
/* oops, this arc is stored twice! we remove one copy. */
|
|
/* */
|
|
IntWarning("arc", i1, "arc", i2);
|
|
RemoveArc(i2);
|
|
ExtApplArcArcIntersection; /* external-application macro */
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
#endif
|
|
|
|
|
|
|
|
|
|
void vroniObject::SetInvalidSites(int i1, t_site t1, int i2, t_site t2,
|
|
double eps)
|
|
{
|
|
invalid_i1 = i1;
|
|
invalid_t1 = t1;
|
|
invalid_i2 = i2;
|
|
invalid_t2 = t2;
|
|
invalid_eps = eps;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
vr_bool vroniObject::IsInvalidData(vr_bool critical)
|
|
{
|
|
vr_bool invalid_data = false;
|
|
|
|
if ((invalid_i1 != NIL) && (invalid_i2 != NIL)) {
|
|
VD_Dbg_Warning("IsInvalidData() - invalid data set (pre-determined)!");
|
|
|
|
#ifdef GENUINE_ARCS
|
|
assert((invalid_t1 == PNT) || (invalid_t1 == SEG) ||
|
|
(invalid_t1 == ARC));
|
|
assert((invalid_t2 == PNT) || (invalid_t2 == SEG) ||
|
|
(invalid_t2 == ARC));
|
|
assert((invalid_eps >= ZERO) && (invalid_eps <= ZERO_MAX));
|
|
#else
|
|
assert((invalid_t1 == PNT) || (invalid_t1 == SEG));
|
|
assert((invalid_t2 == PNT) || (invalid_t2 == SEG));
|
|
assert((invalid_eps >= ZERO) && (invalid_eps <= ZERO_MAX));
|
|
#endif
|
|
|
|
if (invalid_t1 == PNT) {
|
|
assert(invalid_t2 == PNT);
|
|
invalid_data = IsPntOnPnt(invalid_i1, invalid_i2, invalid_eps);
|
|
}
|
|
else if (invalid_t1 == SEG) {
|
|
if (invalid_t2 == PNT) {
|
|
invalid_data = IsPntOnSeg(invalid_i1, invalid_i2, invalid_eps);
|
|
}
|
|
else if (invalid_t2 == SEG) {
|
|
invalid_data = IsSegSegIntersection(invalid_i1, invalid_i2,
|
|
invalid_eps);
|
|
}
|
|
}
|
|
#ifdef GENUINE_ARCS
|
|
else if (invalid_t1 == ARC) {
|
|
if (invalid_t2 == PNT) {
|
|
invalid_data = IsPntOnArc(invalid_i1, invalid_i2, invalid_eps);
|
|
}
|
|
else if (invalid_t2 == SEG) {
|
|
invalid_data = IsSegArcIntersection(invalid_i2, invalid_i1,
|
|
invalid_eps);
|
|
}
|
|
else if (invalid_t2 == ARC) {
|
|
invalid_data = IsArcArcIntersection(invalid_i1, invalid_i2,
|
|
invalid_eps);
|
|
}
|
|
}
|
|
#endif
|
|
|
|
invalid_i1 = NIL;
|
|
invalid_i2 = NIL;
|
|
invalid_eps = ZERO;
|
|
}
|
|
|
|
if (invalid_data) {
|
|
restart_due_to_intersection = restart = true;
|
|
return true;
|
|
}
|
|
|
|
while(critical && !ThresholdReached()) {
|
|
if (CheckIntersections()) {
|
|
restart_due_to_intersection = restart = true;
|
|
return true;
|
|
}
|
|
//critical = false;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
|
|
|
|
|
|
void vroniObject::SubdivideLongEdges(void)
|
|
{
|
|
coord p1, p2, cent;
|
|
int i, e, n, e0, i1, k;
|
|
t_site t1;
|
|
double a, b, c, dist3, dist4, r3, r4, r;
|
|
int k1;
|
|
coord p3, p4;
|
|
|
|
|
|
for (i = 0; i < num_segs; ++i) {
|
|
e = GetVDPtr(i, SEG);
|
|
assert(InEdgesList(e));
|
|
p1 = GetSegStartCoord(i);
|
|
p2 = GetSegEndCoord(i);
|
|
GetSegEqnData(i, &a, &b, &c);
|
|
assert(IsLftSite(e, i, SEG) || IsRgtSite(e, i, SEG));
|
|
if (IsRgtSite(e, i, SEG)) k = GetEndNode(e);
|
|
else k = GetStartNode(e);
|
|
e0 = e;
|
|
do {
|
|
GetOtherSiteData(e, i, SEG, &i1, &t1);
|
|
if (t1 == PNT) {
|
|
if (IsSegStartPnt(i, i1) || IsSegEndPnt(i, i1)) {
|
|
k1 = GetOtherNode(e, k);
|
|
GetNodeData(k, &p3, &r3);
|
|
GetNodeData(k1, &p4, &r4);
|
|
if ((r3 > 0.0) && (r4 > 0.0)) {
|
|
dist3 = PntLineDist(a, b, c, p3);
|
|
dist4 = PntLineDist(a, b, c, p4);
|
|
if (dist3 * dist4 < 0.0) {
|
|
if (IsSegStartPnt(i, i1))
|
|
n = StoreNode(p1.x, p1.y, 0.0);
|
|
else
|
|
n = StoreNode(p2.x, p2.y, 0.0);
|
|
InsertDummyNode(e, n, false);
|
|
MarkNodeUnchecked(n);
|
|
SetNodeSite(n, i1);
|
|
SetPntNode(i1, n);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
e = GetCCWEdge(e, k);
|
|
k = GetOtherNode(e, k);
|
|
} while (e != e0);
|
|
}
|
|
|
|
|
|
//Check the VD-cells of every arc for long edges
|
|
for (i = 0; i < num_arcs; ++i)
|
|
{
|
|
e = GetVDPtr(i, ARC);
|
|
if( !InEdgesList(e))
|
|
continue;
|
|
|
|
p1 = GetArcStartCoord(i);
|
|
p2 = GetArcEndCoord(i);
|
|
cent = GetArcCenter(i);
|
|
r = GetArcRadius(i);
|
|
assert(IsLftSite(e, i, ARC) || IsRgtSite(e, i, ARC));
|
|
|
|
if (IsRgtSite(e, i, ARC)) k = GetEndNode(e);
|
|
else k = GetStartNode(e);
|
|
|
|
e0 = e;
|
|
do
|
|
{
|
|
GetOtherSiteData(e, i, ARC, &i1, &t1);
|
|
//We are only interested in edges between the arc and its
|
|
//endpoints.
|
|
if (t1 == PNT && (IsArcStartPnt(i, i1) || IsArcEndPnt(i, i1)) )
|
|
{
|
|
k1 = GetOtherNode(e, k);
|
|
GetNodeData(k, &p3, &r3);
|
|
GetNodeData(k1, &p4, &r4);
|
|
|
|
if ((r3 > 0.0) && (r4 > 0.0))
|
|
{
|
|
//Signed distance to arc (<0 means inner side)
|
|
dist3 = PntPntDist(cent, p3) - r;
|
|
dist4 = PntPntDist(cent, p4) - r;
|
|
|
|
//Long edge, since different sides on arc
|
|
if (dist3 * dist4 < 0.0)
|
|
{
|
|
if (IsArcStartPnt(i, i1))
|
|
n = StoreNode(p1.x, p1.y, 0.0);
|
|
else
|
|
n = StoreNode(p2.x, p2.y, 0.0);
|
|
InsertDummyNode(e, n, false);
|
|
MarkNodeUnchecked(n);
|
|
SetNodeSite(n, i1);
|
|
SetPntNode(i1, n);
|
|
}
|
|
}
|
|
}
|
|
|
|
e = GetCCWEdge(e, k);
|
|
k = GetOtherNode(e, k);
|
|
} while (e != e0);
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
double vroniObject::NodeRadiiClassificator(int e, coord p)
|
|
{
|
|
int i, n1, n2;
|
|
t_site t;
|
|
double a, b, c, radius1, radius2, dist, ri;
|
|
coord q, ci;
|
|
|
|
n1 = GetStartNode(e);
|
|
n2 = GetEndNode(e);
|
|
radius1 = GetNodeParam(n1);
|
|
radius2 = GetNodeParam(n2);
|
|
if (radius2 < radius1) VroniSwap(radius1, radius2, dist);
|
|
|
|
GetLftSiteData(e, &i, &t);
|
|
if (t != PNT) GetRgtSiteData(e, &i, &t);
|
|
|
|
if (t == PNT) {
|
|
q = GetPntCoords(i);
|
|
dist = PntPntDist(p, q);
|
|
}
|
|
else if (t == SEG) {
|
|
GetSegEqnData(i, &a, &b, &c);
|
|
dist = AbsPntLineDist(a, b, c, p);
|
|
}
|
|
else {
|
|
assert(t == ARC);
|
|
ci = GetArcCenter(i);
|
|
ri = GetArcRadius(i);
|
|
dist = AbsPntCircleDist(ci, ri, p);
|
|
}
|
|
|
|
if (dist < radius1) return (radius1 - dist);
|
|
else if (dist > radius2) return (dist - radius2);
|
|
else return 0.0;
|
|
}
|
|
|
|
|
|
|
|
/** Classify the solution p with clearance clear with respect to arc i */
|
|
double vroniObject::ClassifySolArc(int i, const coord & p, double_arg clear)
|
|
{
|
|
double distarc, qual;
|
|
|
|
assert(InArcsList(i));
|
|
|
|
qual = PntSiteConeClassificator(i, ARC, GetArcStartCoord(i),
|
|
GetArcEndCoord(i), p, ZERO);
|
|
|
|
if (qual == 0.0) {
|
|
const coord c = GetArcCenter(i);
|
|
const double r = GetArcRadius(i);
|
|
distarc = AbsPntCircleDist(c,r,p) - clear;
|
|
}
|
|
else if (qual < 0.0) {
|
|
distarc = PntPntDist(GetArcStartCoord(i), p) - clear;
|
|
}
|
|
else {
|
|
distarc = PntPntDist(GetArcEndCoord(i), p) - clear;
|
|
}
|
|
|
|
return (Abs(qual) + Abs(distarc));
|
|
}
|
|
|
|
|
|
/** Classify the solution p with clearance clear with respect to seg i */
|
|
double vroniObject::ClassifySolSeg(int i, const coord & p, double_arg clear)
|
|
{
|
|
double a, b, c;
|
|
double distseg, qual;
|
|
|
|
assert( InSegsList(i) );
|
|
|
|
qual = PntSiteConeClassificator(i, SEG, GetSegStartCoord(i),
|
|
GetSegEndCoord(i), p, ZERO);
|
|
|
|
if (qual == 0.0) {
|
|
GetSegEqnData(i, &a, &b, &c);
|
|
distseg = Abs(PntLineDist(a,b,c,p)) - clear;
|
|
}
|
|
else if (qual < 0.0) {
|
|
distseg = PntPntDist(GetSegStartCoord(i), p) - clear;
|
|
}
|
|
else {
|
|
distseg = PntPntDist(GetSegEndCoord(i), p) - clear;
|
|
}
|
|
|
|
return (Abs(qual) + Abs(distseg));
|
|
}
|
|
|
|
|
|
/** Classify the solution p with clearance clear with respect to pnt i */
|
|
double vroniObject::ClassifySolPnt(int i, const coord & p, double_arg clear)
|
|
{
|
|
const coord c = GetPntCoords(i);
|
|
|
|
return Abs(PntPntDist(p,c)-clear);
|
|
}
|
|
|
|
|