SaraP
1908 lines
58 KiB
C++
1908 lines
58 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-611 */
|
|
/* 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 "offset.h"
|
|
|
|
|
|
#define BLOCK_SIZE 1024
|
|
#define MINI 16
|
|
#define PAGE_SIZE 65536
|
|
|
|
|
|
#ifdef VRONI_INFO
|
|
void vroniObject::InitRelaxationMemory(double_arg t)
|
|
{
|
|
max_relaxation = curr_relaxation = t;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
void vroniObject::UpdateRelaxationMemory(double_arg t)
|
|
{
|
|
curr_relaxation = VroniMax(curr_relaxation, t);
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
void vroniObject::ConfirmRelaxationMemory()
|
|
{
|
|
max_relaxation = VroniMax(max_relaxation, curr_relaxation);
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
double vroniObject::ReportRelaxationMemory()
|
|
{
|
|
return max_relaxation;
|
|
}
|
|
#endif
|
|
|
|
|
|
void vroniObject::SetRootTooLarge(double_arg t)
|
|
{
|
|
too_large = t;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
void vroniObject::SetDeg2Flag(void)
|
|
{
|
|
deg2_nodes_inserted = true;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
vr_bool vroniObject::GetDeg2Flag(void)
|
|
{
|
|
return deg2_nodes_inserted;
|
|
}
|
|
|
|
|
|
void vroniObject::SetNodesSqdFlag()
|
|
{
|
|
VD_nodes_squared = false;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
vr_bool vroniObject::GetNodesSqdFlag(void)
|
|
{
|
|
return VD_nodes_squared;
|
|
}
|
|
|
|
|
|
void vroniObject::PrintVDCounters(void)
|
|
{
|
|
printf("\nnum_free_nodes: %d\n", num_free_nodes);
|
|
printf("num_free_edges: %d\n", num_free_edges);
|
|
printf("num_nodes: %d\n", num_nodes);
|
|
printf("num_edges: %d\n", num_edges);
|
|
printf("nodes used: %d\n", num_nodes - num_free_nodes);
|
|
printf("edges used: %d\n", num_edges - num_free_edges);
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
#ifdef GRAPHICS
|
|
|
|
void vroniObject::FindClosestNode(double_arg x1, double_arg y1)
|
|
{
|
|
double dist_min, dist, x, y;
|
|
int i, i_min, n1;
|
|
coord p;
|
|
|
|
dist_min = VroniMax(bb_max.x - bb_min.x, bb_max.y - bb_min.y);
|
|
dist_min = VroniMax(dist_min, 1.0);
|
|
dist_min = dist_min * dist_min;
|
|
i_min = 0;
|
|
|
|
for (i = 4; i < num_edges; ++i) {
|
|
if (! IsEdgeDeleted(i) ) {
|
|
n1 = GetStartNode(i);
|
|
p = GetNodeCoord(n1);
|
|
x = p.x - x1;
|
|
y = p.y - y1;
|
|
dist = x * x + y * y;
|
|
if (dist < dist_min) {
|
|
dist_min = dist;
|
|
i_min = n1;
|
|
}
|
|
n1 = GetEndNode(i);
|
|
p = GetNodeCoord(n1);
|
|
x = p.x - x1;
|
|
y = p.y - y1;
|
|
dist = x * x + y * y;
|
|
if (dist < dist_min) {
|
|
dist_min = dist;
|
|
i_min = n1;
|
|
}
|
|
}
|
|
}
|
|
|
|
AddToCurBuffer(i_min, VDN, AlertColor);
|
|
#ifdef VR_TRACE
|
|
PrintNodeData(i_min, "closest");
|
|
#endif
|
|
|
|
return;
|
|
}
|
|
#endif
|
|
|
|
|
|
|
|
int vroniObject::GetVDIdentifier(void)
|
|
{
|
|
return VD_identifier;
|
|
}
|
|
|
|
|
|
|
|
vr_bool vroniObject::GetVDStatus(void)
|
|
{
|
|
return VD_computed;
|
|
}
|
|
|
|
|
|
void vroniObject::ResetVDStatus(void)
|
|
{
|
|
VD_computed = false;
|
|
}
|
|
|
|
|
|
void vroniObject::SetVDStatusTrue(void)
|
|
{
|
|
VD_computed = true;
|
|
}
|
|
|
|
|
|
int vroniObject::GetNumberOfNodes(void)
|
|
{
|
|
return num_nodes;
|
|
}
|
|
|
|
|
|
|
|
int vroniObject::GetNumberOfEdges(void)
|
|
{
|
|
return num_edges;
|
|
}
|
|
|
|
|
|
|
|
void vroniObject::DeleteNode(int n)
|
|
{
|
|
assert(InNodesList(n));
|
|
if (num_free_nodes >= max_num_free_nodes) {
|
|
// MODIF modifico quantità di memoria richiesta dall'allocazione in analogia con std::vector
|
|
// max_num_free_nodes += BLOCK_SIZE;
|
|
max_num_free_nodes = ( num_free_nodes + 1) * 2 ;
|
|
gentlyResizeSTLVector(free_nodes, max_num_free_nodes, "vd:free_nodes");
|
|
}
|
|
free_nodes[num_free_nodes] = n;
|
|
SetNodeStatus(n, DELETED);
|
|
++num_free_nodes;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
void vroniObject::DeleteEdge(int e)
|
|
{
|
|
assert(InEdgesList(e));
|
|
edges[e].lft = NIL;
|
|
edges[e].rgt = NIL;
|
|
MarkEdgeDeleted(e);
|
|
if (num_free_edges >= max_num_free_edges) {
|
|
// MODIF modifico quantità di memoria richiesta dall'allocazione in analogia con std::vector
|
|
// max_num_free_edges += BLOCK_SIZE;
|
|
max_num_free_edges = ( num_free_edges + 1) * 2 ;
|
|
gentlyResizeSTLVector(free_edges, max_num_free_edges, "vd:free_edges");
|
|
}
|
|
|
|
free_edges[num_free_edges] = e;
|
|
++num_free_edges;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
int vroniObject::StoreNode(double_arg x, double_arg y, double_arg r2)
|
|
{
|
|
int i;
|
|
node *ptr;
|
|
|
|
if (num_free_nodes > 0) {
|
|
--num_free_nodes;
|
|
i = free_nodes[num_free_nodes];
|
|
if (i >= num_nodes) num_nodes = i + 1;
|
|
assert(InNodesList(i));
|
|
assert(IsNodeDeleted(i));
|
|
}
|
|
else {
|
|
if (num_nodes >= max_num_nodes) {
|
|
// MODIF modifico quantità di memoria richiesta dall'allocazione in analogia con std::vector
|
|
// max_num_nodes += PAGE_SIZE;
|
|
max_num_nodes = ( num_nodes + 1) * 2 ;
|
|
gentlyResizeSTLVector(nodes, max_num_nodes, "vd:nodes");
|
|
}
|
|
i = num_nodes;
|
|
++num_nodes;
|
|
}
|
|
ptr = &(nodes[i]);
|
|
ptr->p.x = x;
|
|
ptr->p.y = y;
|
|
ptr->r2 = r2;
|
|
ptr->status = UNCHECKED;
|
|
ptr->edge = NIL;
|
|
ptr->site = NIL;
|
|
ptr->deg2 = false;
|
|
#ifdef EXT_APPL_VD
|
|
ptr->ext_appl = ean_NIL;
|
|
#endif
|
|
#ifdef WRITE_VD
|
|
ptr->idx = NIL;
|
|
#endif
|
|
|
|
return i;
|
|
}
|
|
|
|
|
|
|
|
void vroniObject::InitNodes(int number)
|
|
{
|
|
if (max_num_nodes < number) {
|
|
max_num_nodes = number;
|
|
gentlyResizeSTLVector(nodes, max_num_nodes, "vd:nodes");
|
|
}
|
|
num_nodes = 0;
|
|
if (max_num_free_nodes < number) {
|
|
// MODIF modifico quantità di memoria richiesta dall'allocazione
|
|
// max_num_free_nodes = BLOCK_SIZE;
|
|
max_num_free_nodes = number;
|
|
gentlyResizeSTLVector(free_nodes, max_num_free_nodes, "vd:free_nodes");
|
|
}
|
|
num_free_nodes = 0;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
int vroniObject::StoreEdge(int n1, int n2, int lft, int rgt, t_site ltype, t_site rtype)
|
|
{
|
|
int i;
|
|
edge *ptr;
|
|
|
|
if (num_free_edges > 0) {
|
|
--num_free_edges;
|
|
i = free_edges[num_free_edges];
|
|
if (i >= num_edges) num_edges = i + 1;
|
|
assert(InEdgesList(i));
|
|
assert(IsEdgeDeleted(i));
|
|
}
|
|
else {
|
|
if (num_edges >= max_num_edges) {
|
|
// MODIF modifico quantità di memoria richiesta dall'allocazione in analogia con std::vector
|
|
// max_num_edges += PAGE_SIZE;
|
|
max_num_edges = ( num_edges + 1) * 2 ;
|
|
gentlyResizeSTLVector(edges, max_num_edges, "vd:edges");
|
|
}
|
|
i = num_edges;
|
|
++num_edges;
|
|
}
|
|
ptr = &(edges[i]);
|
|
ptr->n1 = n1;
|
|
ptr->n2 = n2;
|
|
ptr->lft = lft;
|
|
ptr->rgt = rgt;
|
|
ptr->ltype = ltype;
|
|
ptr->rtype = rtype;
|
|
ptr->s_ccw = NIL;
|
|
ptr->e_ccw = NIL;
|
|
ptr->s_cw = NIL;
|
|
ptr->e_cw = NIL;
|
|
ptr->del = false;
|
|
#ifdef EXT_APPL_VD
|
|
ptr->ext_appl = eae_NIL;
|
|
#endif
|
|
|
|
return i;
|
|
}
|
|
|
|
|
|
|
|
void vroniObject::InitEdges(int number)
|
|
{
|
|
if (max_num_edges < number) {
|
|
max_num_edges = number;
|
|
gentlyResizeSTLVector(edges, max_num_edges, "vd:edges");
|
|
}
|
|
num_edges = 0;
|
|
if (max_num_free_edges < number) {
|
|
// MODIF modifico quantità di memoria richiesta dall'allocazione
|
|
// max_num_free_edges = BLOCK_SIZE;
|
|
max_num_free_edges = number;
|
|
gentlyResizeSTLVector(free_edges, max_num_free_edges, "vd:free_edges");
|
|
}
|
|
num_free_edges = 0;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
void vroniObject::FreeVDData()
|
|
{
|
|
nodes.clear();
|
|
edges.clear();
|
|
free_nodes.clear();
|
|
free_edges.clear();
|
|
FreeMemory((void**) &dummies, "vd:dummies");
|
|
|
|
max_num_nodes = 0;
|
|
num_nodes = 0;
|
|
max_num_edges = 0;
|
|
num_edges = 0;
|
|
max_num_free_nodes = 0;
|
|
num_free_nodes = 0;
|
|
max_num_free_edges = 0;
|
|
num_free_edges = 0;
|
|
max_num_dummies = 0;
|
|
num_dummies = 0;
|
|
VD_computed = false;
|
|
deg2_nodes_inserted = false;
|
|
VD_nodes_squared = true;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
void vroniObject::ResetVDData(void)
|
|
{
|
|
num_nodes = 0;
|
|
num_edges = 0;
|
|
num_free_nodes = 0;
|
|
num_free_edges = 0;
|
|
num_dummies = 0;
|
|
VD_computed = false;
|
|
deg2_nodes_inserted = false;
|
|
VD_nodes_squared = true;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
vr_bool vroniObject::InEdgesList(int index)
|
|
{
|
|
return ((index >= 0) && (index < num_edges) &&
|
|
(num_edges <= max_num_edges));
|
|
}
|
|
|
|
|
|
|
|
vr_bool vroniObject::InNodesList(int index)
|
|
{
|
|
return ((index >= 0) && (index < num_nodes) &&
|
|
(num_nodes <= max_num_nodes));
|
|
}
|
|
|
|
|
|
|
|
void vroniObject::ComputeInitialVD(void)
|
|
{
|
|
coord n4, n5, n6, n7;
|
|
double r4, r5, r6, r7, infty, dist_min;
|
|
int i, j, number, k;
|
|
|
|
assert(num_edges == 0);
|
|
assert(num_nodes == 0);
|
|
assert(num_pnts > 4);
|
|
VD_computed = false;
|
|
IncrementVDIdentifier();
|
|
|
|
/* */
|
|
/* reserve enough memory for the Voronoi nodes and edges. note that we */
|
|
/* need more nodes and edges than predicted by theory since we subdivide */
|
|
/* conic edges at their apices. */
|
|
/* */
|
|
number = VroniMax(num_pnts, num_segs);
|
|
InitNodes(4 * number);
|
|
InitEdges(6 * number);
|
|
|
|
i = num_pnts - 2;
|
|
j = num_pnts - 1;
|
|
assert(pnts[0].p.x == pnts[1].p.x);
|
|
assert(pnts[0].p.y < pnts[1].p.y);
|
|
assert(pnts[i].p.x == pnts[j].p.x);
|
|
assert(pnts[i].p.y < pnts[j].p.y);
|
|
assert(pnts[0].p.x < pnts[i].p.x);
|
|
assert(pnts[0].p.y == pnts[i].p.y);
|
|
assert(pnts[1].p.x < pnts[j].p.x);
|
|
assert(pnts[1].p.y == pnts[j].p.y);
|
|
assert(pnts[0].p.x < pnts[2].p.x);
|
|
assert(pnts[j].p.x > pnts[2].p.x);
|
|
assert(pnts[0].p.y < pnts[2].p.y);
|
|
assert(pnts[j].p.y > pnts[2].p.y);
|
|
|
|
/* */
|
|
/* compute the four Voronoi nodes of the Voronoi cell of pnts[2] w.r.t. */
|
|
/* the four dummy corner points pnts[0[,pnts[1],pnts[i],pnts[j]. */
|
|
/* */
|
|
if (!PntPntPntCntr(0, 1, 2, &n4, &r4)) {
|
|
VD_Warning("GetInitialVD() - serious numerical problems!\n");
|
|
}
|
|
if (!PntPntPntCntr(1, 2, j, &n5, &r5)) {
|
|
VD_Warning("GetInitialVD() - serious numerical problems!\n");
|
|
}
|
|
if (!PntPntPntCntr(2, i, j, &n6, &r6)) {
|
|
VD_Warning("GetInitialVD() - serious numerical problems!\n");
|
|
}
|
|
if (!PntPntPntCntr(0, 2, i, &n7, &r7)) {
|
|
VD_Warning("GetInitialVD() - serious numerical problems!\n");
|
|
}
|
|
|
|
/* */
|
|
/* compute dummy x,y-coordinates for the "end" nodes n0,...n3 of the */
|
|
/* four rays originating at n4,...,n7. */
|
|
/* */
|
|
infty = sqrt(DBL_MAX / 10.0);
|
|
|
|
/* */
|
|
/* store the four dummy Voronoi nodes. */
|
|
/* */
|
|
k = StoreNode(n4.x - infty, n4.y, infty);
|
|
assert(k == 0);
|
|
k = StoreNode(n5.x, n5.y + infty, infty);
|
|
assert(k == 1);
|
|
k = StoreNode(n6.x + infty, n6.y, infty);
|
|
assert(k == 2);
|
|
k = StoreNode(n7.x, n7.y - infty, infty);
|
|
assert(k == 3);
|
|
|
|
/* */
|
|
/* store the four true Voronoi nodes. */
|
|
/* */
|
|
k = StoreNode(n4.x, n4.y, r4);
|
|
assert(k == 4);
|
|
k = StoreNode(n5.x, n5.y, r5);
|
|
assert(k == 5);
|
|
k = StoreNode(n6.x, n6.y, r6);
|
|
assert(k == 6);
|
|
k = StoreNode(n7.x, n7.y, r7);
|
|
assert(k == 7);
|
|
|
|
/* */
|
|
/* store the four Voronoi rays. */
|
|
/* */
|
|
k = StoreEdge(0, 4, 1, 0, PNT, PNT);
|
|
assert(k == 0);
|
|
k = StoreEdge(1, 5, j, 1, PNT, PNT);
|
|
assert(k == 1);
|
|
k = StoreEdge(2, 6, i, j, PNT, PNT);
|
|
assert(k == 2);
|
|
k = StoreEdge(3, 7, 0, i, PNT, PNT);
|
|
assert(k == 3);
|
|
|
|
/* */
|
|
/* store the four true Voronoi edges (which bound the Voronoi cell of the */
|
|
/* point pnts[2]). */
|
|
/* */
|
|
k = StoreEdge(4, 5, 1, 2, PNT, PNT);
|
|
assert(k == 4);
|
|
#ifdef GRAPHICS
|
|
if (graphics) AddToCurBuffer(k, VDE, VDCurrColor);
|
|
#endif
|
|
k = StoreEdge(5, 6, j, 2, PNT, PNT);
|
|
assert(k == 5);
|
|
#ifdef GRAPHICS
|
|
if (graphics) AddToCurBuffer(k, VDE, VDCurrColor);
|
|
#endif
|
|
k = StoreEdge(6, 7, i, 2, PNT, PNT);
|
|
assert(k == 6);
|
|
#ifdef GRAPHICS
|
|
if (graphics) AddToCurBuffer(k, VDE, VDCurrColor);
|
|
#endif
|
|
k = StoreEdge(7, 4, 0, 2, PNT, PNT);
|
|
assert(k == 7);
|
|
#ifdef GRAPHICS
|
|
if (graphics) AddToCurBuffer(k, VDE, VDCurrColor);
|
|
#endif
|
|
|
|
/* */
|
|
/* store four dummy Voronoi edges (which "bound" the Voronoi cells of the */
|
|
/* points pnts[0], pnts[1], pnts[i], pnts[j]). */
|
|
/* */
|
|
k = StoreEdge(0, 1, NIL, 1, UNKNOWN, PNT);
|
|
assert(k == 8);
|
|
k = StoreEdge(1, 2, NIL, j, UNKNOWN, PNT);
|
|
assert(k == 9);
|
|
k = StoreEdge(2, 3, NIL, i, UNKNOWN, PNT);
|
|
assert(k == 10);
|
|
k = StoreEdge(3, 0, NIL, 0, UNKNOWN, PNT);
|
|
assert(k == 11);
|
|
|
|
/* */
|
|
/* add all CCW/CW pointers */
|
|
/* */
|
|
edges[0].e_ccw = 7;
|
|
edges[0].e_cw = 4;
|
|
edges[0].s_ccw = 8;
|
|
edges[0].s_cw = 11;
|
|
|
|
edges[1].e_ccw = 4;
|
|
edges[1].e_cw = 5;
|
|
edges[1].s_ccw = 9;
|
|
edges[1].s_cw = 8;
|
|
|
|
edges[2].e_ccw = 5;
|
|
edges[2].e_cw = 6;
|
|
edges[2].s_ccw = 10;
|
|
edges[2].s_cw = 9;
|
|
|
|
edges[3].e_ccw = 6;
|
|
edges[3].e_cw = 7;
|
|
edges[3].s_ccw = 11;
|
|
edges[3].s_cw = 10;
|
|
|
|
edges[4].s_ccw = 0;
|
|
edges[4].s_cw = 7;
|
|
edges[4].e_ccw = 5;
|
|
edges[4].e_cw = 1;
|
|
|
|
edges[5].s_ccw = 1;
|
|
edges[5].s_cw = 4;
|
|
edges[5].e_ccw = 6;
|
|
edges[5].e_cw = 2;
|
|
|
|
edges[6].s_ccw = 2;
|
|
edges[6].s_cw = 5;
|
|
edges[6].e_ccw = 7;
|
|
edges[6].e_cw = 3;
|
|
|
|
edges[7].s_ccw = 3;
|
|
edges[7].s_cw = 6;
|
|
edges[7].e_ccw = 4;
|
|
edges[7].e_cw = 0;
|
|
|
|
edges[8].s_ccw = 11;
|
|
edges[8].s_cw = 0;
|
|
edges[8].e_ccw = 1;
|
|
edges[8].e_cw = 9;
|
|
|
|
edges[9].s_ccw = 8;
|
|
edges[9].s_cw = 1;
|
|
edges[9].e_ccw = 2;
|
|
edges[9].e_cw = 10;
|
|
|
|
edges[10].s_ccw = 9;
|
|
edges[10].s_cw = 2;
|
|
edges[10].e_ccw = 3;
|
|
edges[10].e_cw = 11;
|
|
|
|
edges[11].s_ccw = 10;
|
|
edges[11].s_cw = 3;
|
|
edges[11].e_ccw = 0;
|
|
edges[11].e_cw = 8;
|
|
|
|
/* */
|
|
/* set pointers from the five points to edges of their Voronoi cells. */
|
|
/* */
|
|
pnts[0].vd = 11;
|
|
pnts[1].vd = 8;
|
|
pnts[2].vd = 4;
|
|
pnts[j].vd = 9;
|
|
pnts[i].vd = 10;
|
|
|
|
/* */
|
|
/* store an incident Voronoi edge with every node. */
|
|
/* */
|
|
nodes[0].edge = 0;
|
|
nodes[1].edge = 1;
|
|
nodes[2].edge = 2;
|
|
nodes[3].edge = 3;
|
|
nodes[4].edge = 0;
|
|
nodes[5].edge = 1;
|
|
nodes[6].edge = 2;
|
|
nodes[7].edge = 3;
|
|
|
|
/* */
|
|
/* insert point pnt[2] into the grid. */
|
|
/* */
|
|
|
|
(void) InsertPntIntoGrid(2, &dist_min);
|
|
|
|
/* */
|
|
/* mark the five points for drawing. */
|
|
/* */
|
|
#ifdef GRAPHICS
|
|
if (graphics) {
|
|
pnts[0].draw = true;
|
|
pnts[1].draw = true;
|
|
pnts[2].draw = true;
|
|
pnts[i].draw = true;
|
|
pnts[j].draw = true;
|
|
AddToCurBuffer(2, PNT, SiteCurrColor);
|
|
}
|
|
#endif
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
#ifdef GRAPHICS
|
|
|
|
// MODIF : alla funzione AddEdgeToBuffer sono passati anche i parametri in cui viengono calcolati i due punti del bisettore
|
|
void vroniObject::AddVDEdgeToBuffer(int i)
|
|
{
|
|
int n1, n2;
|
|
double t1, t2;
|
|
coord u, v;
|
|
|
|
n1 = GetStartNode(i);
|
|
n2 = GetEndNode(i);
|
|
|
|
// MODIF : lo step size viene modificato come in AddVDToBuffer
|
|
double delta_x = bb_max.x - bb_min.x ;
|
|
double delta_y = bb_max.y - bb_min.y ;
|
|
double delta = VroniMax(delta_x, delta_y) ;
|
|
if (le(delta, ZERO)) delta = ZERO ;
|
|
SetStepSize(delta) ;
|
|
|
|
switch(edges[i].ltype) {
|
|
case(PNT):
|
|
switch(edges[i].rtype) {
|
|
case(PNT): /* PNT-PNT: line bisector */
|
|
GetNodeData(n1, &u, &t1);
|
|
GetNodeData(n2, &v, &t2);
|
|
AddEdgeToBuffer(nodes[n1].p.x, nodes[n1].p.y,
|
|
nodes[n2].p.x, nodes[n2].p.y,
|
|
VDColor, t1, t2);
|
|
break;
|
|
case(SEG): /* PNT-SEG: parabola bisector */
|
|
GetNodeData(n1, &u, &t1);
|
|
GetNodeData(n2, &v, &t2);
|
|
AddParabolaToBuffer(i, t1, t2, u, v, VDColor);
|
|
break;
|
|
case(ARC):
|
|
#ifdef GENUINE_ARCS
|
|
GetNodeData(n1, &u, &t1);
|
|
GetNodeData(n2, &v, &t2);
|
|
AddHyperbolaEllipseToBuffer(i, t1, t2, u, v, VDColor);
|
|
#endif
|
|
break;
|
|
default:
|
|
break;
|
|
}
|
|
break;
|
|
case(SEG):
|
|
switch(edges[i].rtype) {
|
|
case(PNT): /* SEG-PNT: parabola bisector */
|
|
GetNodeData(n1, &u, &t1);
|
|
GetNodeData(n2, &v, &t2);
|
|
AddParabolaToBuffer(i, t1, t2, u, v, VDColor);
|
|
break;
|
|
case(SEG): /* SEG-SEG: line bisector */
|
|
GetNodeData(n1, &u, &t1);
|
|
GetNodeData(n2, &v, &t2);
|
|
AddEdgeToBuffer(nodes[n1].p.x, nodes[n1].p.y,
|
|
nodes[n2].p.x, nodes[n2].p.y,
|
|
VDColor, t1, t2);
|
|
break;
|
|
case(ARC):
|
|
#ifdef GENUINE_ARCS
|
|
GetNodeData(n1, &u, &t1);
|
|
GetNodeData(n2, &v, &t2);
|
|
AddParabolaToBuffer(i, t1, t2, u, v, VDColor);
|
|
#endif
|
|
break;
|
|
default:
|
|
break;
|
|
}
|
|
break;
|
|
case(ARC):
|
|
switch(edges[i].rtype) {
|
|
case(PNT):
|
|
#ifdef GENUINE_ARCS
|
|
GetNodeData(n1, &u, &t1);
|
|
GetNodeData(n2, &v, &t2);
|
|
AddHyperbolaEllipseToBuffer(i, t1, t2, u, v, VDColor);
|
|
#endif
|
|
break;
|
|
case(SEG):
|
|
#ifdef GENUINE_ARCS
|
|
GetNodeData(n1, &u, &t1);
|
|
GetNodeData(n2, &v, &t2);
|
|
AddParabolaToBuffer(i, t1, t2, u, v, VDColor);
|
|
#endif
|
|
break;
|
|
case(ARC):
|
|
#ifdef GENUINE_ARCS
|
|
GetNodeData(n1, &u, &t1);
|
|
GetNodeData(n2, &v, &t2);
|
|
AddHyperbolaEllipseToBuffer(i, t1, t2, u, v, VDColor);
|
|
#endif
|
|
break;
|
|
default:
|
|
break;
|
|
}
|
|
break;
|
|
default:
|
|
break;
|
|
}
|
|
|
|
// MODIF : non serve allocare il buffer dei nodi ( eviti problemi di memory leak)
|
|
// AddNodeToBuffer(n1, VDColor);
|
|
// AddNodeToBuffer(n2, VDColor);
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
void vroniObject::AddVDToBuffer(vr_bool left_vd, vr_bool right_vd)
|
|
{
|
|
int i, j, not_needed;
|
|
double delta_x, delta_y, delta;
|
|
vr_bool unrestricted;
|
|
///void SetStepSize(double_arg delta);
|
|
|
|
/* */
|
|
/* delete all VD edges currently stored in the graphics buffer */
|
|
/* */
|
|
assert(num_edges > 11);
|
|
assert(num_nodes > 7);
|
|
ResetVDBuffer();
|
|
|
|
/* */
|
|
/* are we required to output the VD only on the "left" or right side of */
|
|
/* the input segments/arcs? */
|
|
/* */
|
|
if (left_vd && right_vd) {
|
|
left_vd = right_vd = false;
|
|
}
|
|
unrestricted = !(left_vd || right_vd);
|
|
|
|
/* */
|
|
/* compute the discretization threshold for approximating non-linear */
|
|
/* bisectors. */
|
|
/* */
|
|
delta_x = bb_max.x - bb_min.x;
|
|
delta_y = bb_max.y - bb_min.y;
|
|
delta = VroniMax(delta_x, delta_y);
|
|
if (le(delta, ZERO)) delta = ZERO;
|
|
SetStepSize(delta);
|
|
|
|
/* */
|
|
/* terminate the four VD rays within a region that can be handled. */
|
|
/* */
|
|
delta_x = 10.0 * (pnts[num_pnts-1].p.x - pnts[0].p.x);
|
|
delta_y = 10.0 * (pnts[num_pnts-1].p.y - pnts[0].p.y);
|
|
|
|
if (unrestricted) {
|
|
AddEdgeToBuffer(nodes[edges[0].n2].p.x, nodes[edges[0].n2].p.y,
|
|
nodes[edges[0].n2].p.x-delta_x, nodes[edges[0].n1].p.y,
|
|
VDColor);
|
|
AddEdgeToBuffer(nodes[edges[2].n2].p.x, nodes[edges[2].n2].p.y,
|
|
nodes[edges[2].n2].p.x+delta_x, nodes[edges[2].n1].p.y,
|
|
VDColor);
|
|
AddEdgeToBuffer(nodes[edges[1].n2].p.x, nodes[edges[1].n2].p.y,
|
|
nodes[edges[1].n1].p.x, nodes[edges[1].n2].p.y+delta_y,
|
|
VDColor);
|
|
AddEdgeToBuffer(nodes[edges[3].n2].p.x, nodes[edges[3].n2].p.y,
|
|
nodes[edges[3].n1].p.x, nodes[edges[3].n2].p.y-delta_y,
|
|
VDColor);
|
|
|
|
for (i = 4; i < num_edges; ++i) {
|
|
if ((! IsEdgeDeleted(i) ) &&
|
|
(edges[i].lft != NIL) && (edges[i].rgt != NIL)) {
|
|
AddVDEdgeToBuffer(i);
|
|
}
|
|
}
|
|
}
|
|
else {
|
|
/* */
|
|
/* find those VD edges that are to be output */
|
|
/* */
|
|
InitializeEdgeData(unrestricted, left_vd, false, ¬_needed);
|
|
|
|
j = -1;
|
|
AdvanceActiveEdge(i, j, false);
|
|
while (i != NIL) {
|
|
switch(i) {
|
|
case 0:
|
|
AddEdgeToBuffer(nodes[edges[0].n2].p.x, nodes[edges[0].n2].p.y,
|
|
nodes[edges[0].n2].p.x-delta_x,
|
|
nodes[edges[0].n1].p.y,
|
|
VDColor);
|
|
break;
|
|
case 1:
|
|
AddEdgeToBuffer(nodes[edges[2].n2].p.x, nodes[edges[2].n2].p.y,
|
|
nodes[edges[2].n2].p.x+delta_x,
|
|
nodes[edges[2].n1].p.y,
|
|
VDColor);
|
|
break;
|
|
case 2:
|
|
AddEdgeToBuffer(nodes[edges[1].n2].p.x, nodes[edges[1].n2].p.y,
|
|
nodes[edges[1].n1].p.x,
|
|
nodes[edges[1].n2].p.y+delta_y,
|
|
VDColor);
|
|
break;
|
|
case 3:
|
|
AddEdgeToBuffer(nodes[edges[3].n2].p.x, nodes[edges[3].n2].p.y,
|
|
nodes[edges[3].n1].p.x,
|
|
nodes[edges[3].n2].p.y-delta_y,
|
|
VDColor);
|
|
break;
|
|
default:
|
|
AddVDEdgeToBuffer(i);
|
|
break;
|
|
}
|
|
AdvanceActiveEdge(i, j, false);
|
|
}
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
void vroniObject::AddDelToBuffer(void)
|
|
{
|
|
int i;
|
|
|
|
assert(num_edges > 11);
|
|
assert(num_nodes > 7);
|
|
|
|
for (i = 4; i < num_edges; ++i) {
|
|
if ((! IsEdgeDeleted(i) ) &&
|
|
( edges[i].lft >= 2) && (edges[i].lft < (num_pnts - 2)) &&
|
|
(edges[i].rgt >= 2) && (edges[i].rgt < (num_pnts - 2))) {
|
|
switch(edges[i].ltype) {
|
|
case(PNT):
|
|
switch(edges[i].rtype) {
|
|
case(PNT): /* PNT-PNT: line bisector */
|
|
AddEdgeToBuffer(pnts[edges[i].lft].p.x, pnts[edges[i].lft].p.y,
|
|
pnts[edges[i].rgt].p.x, pnts[edges[i].rgt].p.y,
|
|
DTColor);
|
|
break;
|
|
default:
|
|
break;
|
|
}
|
|
break;
|
|
default:
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
#define PrintNodeStatus(N) \
|
|
{ \
|
|
if (nodes[N].deg2) { \
|
|
if (nodes[N].status == UNCHECKED) \
|
|
fprintf(stderr, \
|
|
"CheckVDCell - deg-2 node %d has status UNCHECKED\n", N); \
|
|
else if (nodes[N].status == CHECKED) \
|
|
fprintf(stderr, \
|
|
"CheckVDCell - deg-2 node %d has status CHECKED\n", N); \
|
|
else if (nodes[N].status == DELETED) \
|
|
fprintf(stderr, \
|
|
"CheckVDCell - deg-2 node %d has status DELETED\n", N); \
|
|
else if (nodes[N].status == VISITED) \
|
|
fprintf(stderr, \
|
|
"CheckVDCell - deg-2 node %d has status VISITED\n", N); \
|
|
else if (nodes[N].status == DUMMY) \
|
|
fprintf(stderr, \
|
|
"CheckVDCell - deg-2 node %d has status DUMMY\n", N); \
|
|
else if (nodes[N].status == MISC) \
|
|
fprintf(stderr, \
|
|
"CheckVDCell - deg-2 node %d has status MISC\n", N); \
|
|
} \
|
|
else { \
|
|
if (nodes[N].status == UNCHECKED) \
|
|
fprintf(stderr, \
|
|
"CheckVDCell - deg-3 node %d has status UNCHECKED\n", N); \
|
|
else if (nodes[N].status == CHECKED) \
|
|
fprintf(stderr, \
|
|
"CheckVDCell - deg-3 node %d has status CHECKED\n", N); \
|
|
else if (nodes[N].status == DELETED) \
|
|
fprintf(stderr, \
|
|
"CheckVDCell - deg-3 node %d has status DELETED\n", N); \
|
|
else if (nodes[N].status == VISITED) \
|
|
fprintf(stderr, \
|
|
"CheckVDCell - deg-3 node %d has status VISITED\n", N); \
|
|
else if (nodes[N].status == DUMMY) \
|
|
fprintf(stderr, \
|
|
"CheckVDCell - deg-3 node %d has status DUMMY\n", N); \
|
|
else if (nodes[N].status == MISC) \
|
|
fprintf(stderr, \
|
|
"CheckVDCell - deg-3 node %d has status MISC\n", N); \
|
|
} \
|
|
}
|
|
|
|
|
|
vr_bool vroniObject::CheckVDCell(int i, int e0, t_site t, vr_bool arcs_recovered)
|
|
{
|
|
int e, e1, n, n1, n2, cntr = 0;
|
|
vr_bool success = true;
|
|
|
|
e = e0;
|
|
|
|
if (IsLftSite(e, i, t)) {
|
|
n = edges[e].n1;
|
|
}
|
|
else if (IsRgtSite(e, i, t)) {
|
|
n = edges[e].n2;
|
|
}
|
|
else {
|
|
fprintf(stderr,
|
|
"CheckVDCell - site %d of type %d not lft/rgt of edge %d\n",
|
|
i, t, e);
|
|
#ifdef VR_TRACE
|
|
PrintSiteData(i, t, "CheckVD");
|
|
#endif
|
|
return false;
|
|
}
|
|
|
|
arcs_recovered = false;
|
|
|
|
do {
|
|
#ifdef VR_TRACE
|
|
if (proto) printf("checking edge %2d of site %2d (site type %d)\n",
|
|
e, i, t);
|
|
#endif
|
|
if (!InEdgesList(e)) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - edge %d is not in the edge list\n", e);
|
|
success = false;
|
|
}
|
|
if ( IsEdgeDeleted(e) ) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - edge %d is marked as deleted\n", e);
|
|
success = false;
|
|
}
|
|
if (!IsLftSite(e, i, t) && !IsRgtSite(e, i, t)) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - site %d of type %d not lft/rgt of edge %d\n",
|
|
i, t, e);
|
|
success = false;
|
|
}
|
|
n1 = edges[e].n1;
|
|
if (!InNodesList(n1)) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - start node %d of edge %d not in list\n", n1, e);
|
|
success = false;
|
|
}
|
|
if ((n1 > 3) && (nodes[n1].r2 == 0.0) && (nodes[n1].site == NIL)) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - node %d has radius 0.0 but does not coincide with point\n", n1);
|
|
|
|
success = false;
|
|
}
|
|
if (!(nodes[n1].deg2 || (nodes[n1].status == UNCHECKED))) {
|
|
PrintNodeStatus(n1);
|
|
success = false;
|
|
}
|
|
if (!((nodes[n1].edge == e) || (nodes[n1].edge == edges[e].s_ccw) ||
|
|
(nodes[n1].edge == edges[e].s_cw))) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - edge %d not incident at its start node %d - %d\n",
|
|
e, n1, nodes[n1].edge);
|
|
success = false;
|
|
}
|
|
if (nodes[n1].deg2) {
|
|
if (edges[e].s_ccw != edges[e].s_cw) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - deg-2 start node %d of edge %d has more than two incident edges!\n",
|
|
n1, e);
|
|
success = false;
|
|
}
|
|
}
|
|
else {
|
|
if (edges[e].s_ccw == edges[e].s_cw) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - deg-3 start node %d of edge %d has only two incident edges!\n",
|
|
n1, e);
|
|
success = false;
|
|
}
|
|
}
|
|
n2 = edges[e].n2;
|
|
if (!InNodesList(n2)) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - end node %d of edge %d not in list\n", n2, e);
|
|
success = false;
|
|
}
|
|
if ((n2 > 3) && (nodes[n2].r2 == 0.0) && (nodes[n2].site == NIL)) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - node %d has radius 0.0 but does not coincide with point\n", n2);
|
|
|
|
success = false;
|
|
}
|
|
if (!(nodes[n2].deg2 || (nodes[n2].status == UNCHECKED))) {
|
|
PrintNodeStatus(n2);
|
|
success = false;
|
|
}
|
|
if (!((nodes[n2].edge == e) || (nodes[n2].edge == edges[e].e_ccw) ||
|
|
(nodes[n2].edge == edges[e].e_cw))) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - edge %d not incident at its end node %d - %d\n",
|
|
e, n2, nodes[n2].edge);
|
|
success = false;
|
|
}
|
|
if (nodes[n2].deg2) {
|
|
if (edges[e].e_ccw != edges[e].e_cw) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - deg-2 start node %d of edge %d has more than two incident edges!\n",
|
|
n2, e);
|
|
success = false;
|
|
}
|
|
}
|
|
else {
|
|
if (edges[e].e_ccw == edges[e].e_cw) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - deg-3 start node %d of edge %d has only two incident edges!\n",
|
|
n2, e);
|
|
success = false;
|
|
}
|
|
}
|
|
e1 = edges[e].s_cw;
|
|
if (!InEdgesList(e1)) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - edge %d ptd s_cw by edge %d not in list\n",
|
|
e1, e);
|
|
success = false;
|
|
}
|
|
if (!((edges[e1].s_ccw == e) || (edges[e1].e_ccw == e))) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - edge %d does not ptr back ccw (s_cw) to %d\n",
|
|
e1, e);
|
|
fprintf(stderr,
|
|
"CheckVDCell - edges[%d].s_ccw = %d, edges[%d].e_ccw = %d\n",
|
|
e1, edges[e1].s_ccw, e1, edges[e1].e_ccw);
|
|
fprintf(stderr,
|
|
"CheckVDCell - edges[%d].s_cw = %d, edges[%d].e_cw = %d\n",
|
|
e1, edges[e1].s_cw, e1, edges[e1].e_cw);
|
|
success = false;
|
|
}
|
|
e1 = edges[e].e_cw;
|
|
if (!InEdgesList(e1)) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - edge %d ptd e_cw by edge %d not in list\n",
|
|
e1, e);
|
|
success = false;
|
|
}
|
|
if (!((edges[e1].s_ccw == e) || (edges[e1].e_ccw == e))) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - edge %d does not ptr back ccw (e_cw) to %d\n",
|
|
e1, e);
|
|
fprintf(stderr,
|
|
"CheckVDCell - edges[%d].s_ccw = %d, edges[%d].e_ccw = %d\n",
|
|
e1, edges[e1].s_ccw, e1, edges[e1].e_ccw);
|
|
fprintf(stderr,
|
|
"CheckVDCell - edges[%d].s_cw = %d, edges[%d].e_cw = %d\n",
|
|
e1, edges[e1].s_cw, e1, edges[e1].e_cw);
|
|
success = false;
|
|
}
|
|
e1 = edges[e].s_ccw;
|
|
if (!InEdgesList(e1)) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - edge %d ptd s_ccw by edge %d not in list\n",
|
|
e1, e);
|
|
success = false;
|
|
}
|
|
if (!((edges[e1].s_cw == e) || (edges[e1].e_cw == e))) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - edge %d does not ptr back cw (s_ccw) to %d\n",
|
|
e1, e);
|
|
fprintf(stderr,
|
|
"CheckVDCell - edges[%d].s_ccw = %d, edges[%d].e_ccw = %d\n",
|
|
e1, edges[e1].s_ccw, e1, edges[e1].e_ccw);
|
|
fprintf(stderr,
|
|
"CheckVDCell - edges[%d].s_cw = %d, edges[%d].e_cw = %d\n",
|
|
e1, edges[e1].s_cw, e1, edges[e1].e_cw);
|
|
success = false;
|
|
}
|
|
e1 = edges[e].e_ccw;
|
|
if (!InEdgesList(e1)) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - edge %d ptd e_ccw by edge %d not in list\n",
|
|
e1, e);
|
|
success = false;
|
|
}
|
|
if (!((edges[e1].s_cw == e) || (edges[e1].e_cw == e))) {
|
|
fprintf(stderr,
|
|
"CheckVDCell - edge %d does not ptr back cw (e_ccw) to %d\n",
|
|
e1, e);
|
|
fprintf(stderr,
|
|
"CheckVDCell - edges[%d].s_ccw = %d, edges[%d].e_ccw = %d\n",
|
|
e1, edges[e1].s_ccw, e1, edges[e1].e_ccw);
|
|
fprintf(stderr,
|
|
"CheckVDCell - edges[%d].s_cw = %d, edges[%d].e_cw = %d\n",
|
|
e1, edges[e1].s_cw, e1, edges[e1].e_cw);
|
|
success = false;
|
|
}
|
|
|
|
e = GetCCWEdge(e, n);
|
|
n = GetOtherNode(e, n);
|
|
|
|
++cntr;
|
|
} while ((e != e0) && (cntr < num_edges));
|
|
|
|
if (!success) {
|
|
if (t == PNT)
|
|
fprintf(stderr,
|
|
"CheckVDCell - the error(s) occurred for pnt %d\n", i);
|
|
else if (t == SEG)
|
|
fprintf(stderr,
|
|
"CheckVDCell - the error(s) occurred for seg %d\n", i);
|
|
else if (t == ARC)
|
|
fprintf(stderr,
|
|
"CheckVDCell - the error(s) occurred for seg %d\n", i);
|
|
else {
|
|
fprintf(stderr,
|
|
"CheckVDCell - the error(s) occurred for site %d ", i);
|
|
fprintf(stderr,
|
|
"of unknown type\n");
|
|
}
|
|
}
|
|
return success;
|
|
}
|
|
#endif
|
|
|
|
|
|
|
|
vr_bool vroniObject::CheckVD(vr_bool arcs_recovered)
|
|
{
|
|
#ifdef GRAPHICS
|
|
int i, e;
|
|
vr_bool success = true;
|
|
|
|
for (i = 0; i < num_pnts; ++i) {
|
|
if (pnts[i].draw && !IsDeletedPnt(i)) {
|
|
e = GetVDPtr(i, PNT);
|
|
if ((e == NIL) || IsEdgeDeleted(e)) {
|
|
AddToCurBuffer(i, PNT, AlertColor);
|
|
fprintf(stderr, "CheckVDCell - pnt %d has no VD edge!\n", i);
|
|
success = false;
|
|
}
|
|
else {
|
|
if (!CheckVDCell(i, e, PNT, arcs_recovered)) {
|
|
AddToCurBuffer(i, PNT, AlertColor);
|
|
success = false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
for (i = 0; i < num_segs; ++i) {
|
|
if (segs[i].draw) {
|
|
e = GetVDPtr(i, SEG);
|
|
if ((e == NIL) || IsEdgeDeleted(e)) {
|
|
AddToCurBuffer(i, SEG, AlertColor);
|
|
fprintf(stderr, "CheckVDCell - seg %d has no VD edge!\n", i);
|
|
success = false;
|
|
}
|
|
else {
|
|
if (!CheckVDCell(i, e, SEG, arcs_recovered)) {
|
|
AddToCurBuffer(i, SEG, AlertColor);
|
|
success = false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
for (i = 0; i < num_arcs; ++i) {
|
|
if (arcs[i].draw) {
|
|
e = GetVDPtr(i, ARC);
|
|
if ((e == NIL) || IsEdgeDeleted(e)) {
|
|
AddToCurBuffer(i, ARC, AlertColor);
|
|
fprintf(stderr, "CheckVDCell - arc %d has no VD edge!\n", i);
|
|
success = false;
|
|
}
|
|
else {
|
|
if (!CheckVDCell(i, e, ARC, arcs_recovered)) {
|
|
AddToCurBuffer(i, ARC, AlertColor);
|
|
success = false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
#ifdef VR_TRACE
|
|
if (proto) {
|
|
for (i = 0; i < num_edges; ++i) {
|
|
if (! IsEdgeDeleted(i) ) {
|
|
printf("edges[%2d] - lft = %2d, rgt = %2d, start = %2d, end = %2d, ltyp = %1d, rtyp = %1d\n",
|
|
i, edges[i].lft, edges[i].rgt, edges[i].n1, edges[i].n2,
|
|
edges[i].ltype, edges[i].rtype);
|
|
printf(" s_ccw = %2d, s_cw = %2d, e_ccw = %2d, e_cw = %2d\n",
|
|
edges[i].s_ccw, edges[i].s_cw, edges[i].e_ccw, edges[i].e_cw);
|
|
}
|
|
else {
|
|
printf("edges[%2d] - deleted!\n", i);
|
|
}
|
|
}
|
|
for (i = 0; i < num_nodes; ++i) {
|
|
if (!((nodes[i].status == DELETED) || (nodes[i].status == MISC))) {
|
|
printf("nodes[%2d] - (%f,%f)\n", i, nodes[i].p.x, nodes[i].p.y);
|
|
}
|
|
else {
|
|
printf("nodes[%2d] - deleted!\n", i);
|
|
}
|
|
}
|
|
}
|
|
#endif
|
|
|
|
#ifdef VRONI_WARN
|
|
if (!success && verbose) {
|
|
printf("\nnum_pnts = %d; num_segs = %d; num_arcs = %d\n", num_pnts,
|
|
num_segs, num_arcs);
|
|
}
|
|
#endif
|
|
|
|
return success;
|
|
#else
|
|
arcs_recovered = false;
|
|
|
|
return true;
|
|
#endif
|
|
}
|
|
|
|
|
|
|
|
|
|
void vroniObject::InsertDummyNode(int e, int n, vr_bool store)
|
|
{
|
|
int i1, i2, n2, e1, e0;
|
|
t_site t1, t2;
|
|
|
|
GetLftSiteData(e, &i1, &t1);
|
|
GetRgtSiteData(e, &i2, &t2);
|
|
n2 = GetEndNode(e);
|
|
e1 = StoreEdge(n, n2, i1, i2, t1, t2);
|
|
#ifdef VR_TRACE
|
|
if (center) {
|
|
printf("InsertDummyNode - edge e = %d, new edge e1 = %d, ", e, e1);
|
|
printf("endnode = %d, new node n = %d\n", n2, n);
|
|
}
|
|
#endif
|
|
SetIncidentEdge(n, e);
|
|
if (GetIncidentEdge(n2) == e) SetIncidentEdge(n2, e1);
|
|
|
|
e0 = GetCCWEdge(e, n2);
|
|
SetCCWEdge(e1, n2, e0);
|
|
SetCWEdge(e0, n2, e1);
|
|
e0 = GetCWEdge(e, n2);
|
|
SetCWEdge(e1, n2, e0);
|
|
SetCCWEdge(e0, n2, e1);
|
|
|
|
SetEndNode(e, n);
|
|
SetCWEdge(e, n, e1);
|
|
SetCCWEdge(e, n, e1);
|
|
|
|
SetCWEdge(e1, n, e);
|
|
SetCCWEdge(e1, n, e);
|
|
|
|
if (store) {
|
|
if (num_dummies >= max_num_dummies) {
|
|
max_num_dummies += MINI;
|
|
dummies = (dummy_node*) ReallocateArray(dummies, max_num_dummies,
|
|
sizeof(dummy_node),
|
|
"vd:dummies");
|
|
}
|
|
dummies[num_dummies].e1 = e;
|
|
dummies[num_dummies].e2 = e1;
|
|
dummies[num_dummies].n = n;
|
|
++num_dummies;
|
|
MarkNodeDummy(n);
|
|
}
|
|
|
|
SetNodeDegree(n, true);
|
|
|
|
ExtApplInsertDummyNode; /* let the user add user-specific code */
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
void vroniObject::DeleteDummyNodes(void)
|
|
{
|
|
int e1, e2, n, e, i, n2, j;
|
|
t_site t;
|
|
|
|
for (j = 0; j < num_dummies; ++j) {
|
|
e1 = dummies[j].e1;
|
|
e2 = dummies[j].e2;
|
|
n = dummies[j].n;
|
|
assert(IsNodeDummy(n));
|
|
|
|
if (GetStartNode(e1) == n) {
|
|
VroniSwap(e1, e2, e);
|
|
}
|
|
assert(GetEndNode(e1) == n);
|
|
assert(GetStartNode(e2) == n);
|
|
assert(GetCCWEdge(e1, n) == e2);
|
|
assert(GetCWEdge(e1, n) == e2);
|
|
assert(GetCCWEdge(e2, n) == e1);
|
|
assert(GetCWEdge(e2, n) == e1);
|
|
|
|
n2 = GetEndNode(e2);
|
|
SetEndNode(e1, n2);
|
|
|
|
if (GetIncidentEdge(n2) == e2) SetIncidentEdge(n2, e1);
|
|
|
|
e = GetCCWEdge(e2, n2);
|
|
SetCCWEdge(e1, n2, e);
|
|
SetCWEdge(e, n2, e1);
|
|
e = GetCWEdge(e2, n2);
|
|
SetCWEdge(e1, n2, e);
|
|
SetCCWEdge(e, n2, e1);
|
|
|
|
GetLftSiteData(e2, &i, &t);
|
|
SetVDPtr(i, t, e1);
|
|
GetRgtSiteData(e2, &i, &t);
|
|
SetVDPtr(i, t, e1);
|
|
|
|
DeleteNode(n);
|
|
DeleteEdge(e2);
|
|
}
|
|
|
|
num_dummies = 0;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
void vroniObject::TakeSquareOfNodes(void)
|
|
{
|
|
int i;
|
|
|
|
for (i = 0; i < num_nodes; ++i) {
|
|
assert(nodes[i].r2 >= 0.0);
|
|
nodes[i].r2 = sqrt(nodes[i].r2);
|
|
}
|
|
|
|
SetNodesSqdFlag();
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
void vroniObject::PrintNodeData(int n, const char *string)
|
|
{
|
|
assert(InNodesList(n));
|
|
|
|
FP_printf("%s, node %d: (%24.20f,%24.20f), radius = %24.20f\n",
|
|
string, n, FP_PRNTARG(nodes[n].p.x), FP_PRNTARG(nodes[n].p.y), FP_PRNTARG(nodes[n].r2));
|
|
switch(nodes[n].status) {
|
|
case(UNCHECKED):
|
|
printf(" status UNCHECKED, ");
|
|
break;
|
|
case(CHECKED):
|
|
printf(" status CHECKED, ");
|
|
break;
|
|
case(DELETED):
|
|
printf(" status DELETED, ");
|
|
break;
|
|
case(VISITED):
|
|
printf(" status VISITED, ");
|
|
break;
|
|
case(DUMMY):
|
|
printf(" status DUMMY, ");
|
|
break;
|
|
case(MISC):
|
|
printf(" status MISC, ");
|
|
break;
|
|
default:
|
|
printf(" status Unknown!, ");
|
|
break;
|
|
}
|
|
printf("edge: %d, site: %d, ", nodes[n].edge, nodes[n].site);
|
|
if (nodes[n].deg2) printf("degree-2 node.\n");
|
|
else printf("degree-3 node.\n");
|
|
fflush(stdout);
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
void vroniObject::PrintEdgeData(int e, const char *string)
|
|
{
|
|
assert(InEdgesList(e));
|
|
|
|
printf("%s, edge %d: n1=%d, n2=%d\n",
|
|
string, e, edges[e].n1, edges[e].n2);
|
|
FP_printf("n1: (%f, %f); n2: (%f, %f)\n",
|
|
FP_PRNTARG(nodes[edges[e].n1].p.x), FP_PRNTARG(nodes[edges[e].n1].p.y),
|
|
FP_PRNTARG(nodes[edges[e].n2].p.x), FP_PRNTARG(nodes[edges[e].n2].p.y));
|
|
printf(" lft = %d, rgt = %d, ltype = %d, rtype = %d\n",
|
|
edges[e].lft, edges[e].rgt, edges[e].ltype, edges[e].rtype);
|
|
printf(" s_ccw = %d, s_cw = %d, e_ccw = %d, e_cw = %d",
|
|
edges[e].s_ccw, edges[e].s_cw, edges[e].e_ccw, edges[e].e_cw);
|
|
if ( IsEdgeDeleted(e) ) printf(", deleted.\n");
|
|
else printf(".\n");
|
|
fflush(stdout);
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
void vroniObject::PrintVDData(const char *string)
|
|
{
|
|
int n, e;
|
|
|
|
printf("\nVD data printed from within %s:\n", string);
|
|
|
|
for (n = 4; n < num_nodes; ++n) PrintNodeData(n, string);
|
|
|
|
for (e = 0; e < num_edges; ++e) PrintEdgeData(e, string);
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
inline double vroniObject::ClassifySolSite(int i, t_site i_type,
|
|
coord c, double r)
|
|
{
|
|
if (i_type == PNT)
|
|
return ClassifySolPnt(i, c, r);
|
|
else if (i_type == SEG)
|
|
return ClassifySolSeg(i, c, r);
|
|
else
|
|
return ClassifySolArc(i, c, r);
|
|
}
|
|
|
|
|
|
int vroniObject::ClassifySolutions(int i, int j, int k, int e,
|
|
t_site i_type, t_site j_type,
|
|
t_site k_type, vr_bool i_is_old,
|
|
vr_bool j_is_old, vr_bool k_is_old,
|
|
coord *centers, double *radii,
|
|
int *num_sol, double eps,
|
|
vr_bool *problematic)
|
|
{
|
|
int m, m1, n1, n2, best_sol, new_site;
|
|
t_site new_site_type;
|
|
double best_qual, qual;
|
|
coord c, old_node, sv, ev, p;
|
|
vr_bool check_sidedness = false;
|
|
double seg_a, seg_b, seg_c, seg_l;
|
|
double ai = 0.0, bi = 0.0, ci = 0.0, ri = 0.0;
|
|
coord q1, q2, q3, sp, ep, arc_c, pi;
|
|
double r1, r2;
|
|
int i1, i2, i3;
|
|
t_site t1, t2, t3;
|
|
double d1, d2, d3, d4, rad1, rad2;
|
|
double cs1, cs2, cs3;
|
|
double r;
|
|
|
|
assert((*num_sol+2) < VRONI_MAXSOL);
|
|
|
|
*problematic = false;
|
|
|
|
/* */
|
|
/* Get start and end nodes (and their coordinates) of edge */
|
|
/* */
|
|
n1 = GetStartNode(e);
|
|
n2 = GetEndNode(e);
|
|
GetNodeData(n1, &q1, &r1);
|
|
GetNodeData(n2, &q2, &r2);
|
|
if (r1 > r2) {
|
|
rad1 = r2;
|
|
rad2 = r1;
|
|
q3 = q1;
|
|
}
|
|
else {
|
|
rad1 = r1;
|
|
rad2 = r2;
|
|
q3 = q2;
|
|
}
|
|
|
|
/* */
|
|
/* get the defining sites of this VD edge */
|
|
/* */
|
|
GetLftSiteData(e, &i1, &t1);
|
|
GetRgtSiteData(e, &i2, &t2);
|
|
if (t1 == PNT) {
|
|
i3 = i1;
|
|
t3 = t1;
|
|
}
|
|
else {
|
|
i3 = i2;
|
|
t3 = t2;
|
|
}
|
|
if (t3 == PNT) {
|
|
pi = GetPntCoords(i3);
|
|
}
|
|
else if (t3 == SEG) {
|
|
GetSegEqnData(i3, &ai, &bi, &ci);
|
|
}
|
|
else {
|
|
assert(t3 == ARC);
|
|
pi = GetArcCenter(i3);
|
|
ri = GetArcRadius(i3);
|
|
}
|
|
|
|
/* */
|
|
/* add old nodes as potential candidates for a center */
|
|
/* */
|
|
centers[*num_sol] = q1;
|
|
radii[*num_sol] = r1;
|
|
++(*num_sol);
|
|
centers[*num_sol] = q2;
|
|
radii[*num_sol] = r2;
|
|
++(*num_sol);
|
|
if (IsNodeDeleted(n1)) old_node = q2; /* old node that is not deleted */
|
|
else old_node = q1; /* old node that is not deleted */
|
|
|
|
d1 = PntPntDist(q1, q2);
|
|
if (le(d1, eps)) {
|
|
/* */
|
|
/* if the old bisector edge is tiny then we simply return the old node */
|
|
/* */
|
|
if (IsNodeDeleted(n1)) return (*num_sol-1);
|
|
else return (*num_sol-2);
|
|
}
|
|
|
|
/* */
|
|
/* get newly inserted site */
|
|
/* */
|
|
if (!i_is_old) {
|
|
new_site = i;
|
|
new_site_type = i_type;
|
|
}
|
|
else if (!j_is_old) {
|
|
new_site = j;
|
|
new_site_type = i_type;
|
|
}
|
|
else {
|
|
assert(!k_is_old);
|
|
new_site = k;
|
|
new_site_type = k_type;
|
|
}
|
|
|
|
/* */
|
|
/* check whether the old node lies within the cone of influence of the */
|
|
/* new site */
|
|
/* */
|
|
if (new_site_type == SEG) {
|
|
GetSegEqnData(new_site, &seg_a, &seg_b, &seg_c);
|
|
seg_l = GetSegLgth(new_site);
|
|
sp = GetSegStartCoord(new_site);
|
|
ep = GetSegEndCoord(new_site);
|
|
check_sidedness =
|
|
(IsInSegCone(sp, old_node, seg_a, seg_b, seg_l) == 0);
|
|
}
|
|
else if (new_site_type == ARC) {
|
|
arc_c = GetArcCenter(new_site);
|
|
sp = GetArcStartCoord(new_site);
|
|
sv = VecSub(sp, arc_c);
|
|
ep = GetArcEndCoord(new_site);
|
|
ev = VecSub(ep, arc_c);
|
|
p = VecSub(old_node, arc_c);
|
|
check_sidedness = (IsInArcCone(sv, ev, p) == 0);
|
|
}
|
|
|
|
best_sol = NIL;
|
|
best_qual = LARGE;
|
|
|
|
/* */
|
|
/* classify the solutions relative to the old VD edge, the radii of */
|
|
/* the old VD nodes, and relative to the input sites */
|
|
/* */
|
|
m1 = *num_sol - 3;
|
|
for (m = 0; m < *num_sol; ++m) {
|
|
c = centers[m];
|
|
r = radii[m];
|
|
|
|
if ((r < too_large) || (best_qual > r)) {
|
|
/* */
|
|
/* carry out checks only if a better solution might be found */
|
|
/* */
|
|
if (r > too_large) qual = r;
|
|
else qual = 0.0;
|
|
|
|
/* node-edge classification: check whether the new node is in the */
|
|
/* cones/strips defined by the old nodes */
|
|
/* */
|
|
d1 = PntSiteConeClassificator(i1, t1, q2, q1, c, eps);
|
|
d1 = Abs(d1);
|
|
d2 = PntSiteConeClassificator(i2, t2, q1, q2, c, eps);
|
|
d2 = Abs(d2);
|
|
|
|
/* */
|
|
/* check whether the new node is on the same side of i1 and i2 */
|
|
/* as the old nodes */
|
|
/* */
|
|
if (gt(rad2, ZERO)) {
|
|
if (t1 != PNT) d3 = NodeSidednessClassificator(i1, t1, q3, c);
|
|
else d3 = 0.0;
|
|
if (t2 != PNT) d4 = NodeSidednessClassificator(i2, t2, q3, c);
|
|
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
|
|
qual += Max4(d1, d2, d3, d4);
|
|
|
|
/* */
|
|
/* node-sidedness classification */
|
|
/* */
|
|
if (check_sidedness)
|
|
qual += NodeSidednessClassificator(new_site, new_site_type,
|
|
old_node, c);
|
|
#ifdef VR_TRACE
|
|
if ((i == 4) && (j == 2) && (k == 2)) {
|
|
printf("q1 = (%20.16f %20.16f)\n", q1.x, q1.y);
|
|
printf("q2 = (%20.16f %20.16f)\n", q2.x, q2.y);
|
|
printf("c = (%20.16f %20.16f)\n", c.x, c.y);
|
|
printf("d1 = %20.16f, d2 = %20.16f\n", d1, d2);
|
|
printf("d3 = %20.16f, d4 = %20.16f\n", d3, d4);
|
|
}
|
|
#endif
|
|
|
|
/* */
|
|
/* node-site classification */
|
|
/* */
|
|
/*
|
|
qual +=
|
|
ClassifySolSite(i, i_type, c, r) +
|
|
ClassifySolSite(j, j_type, c, r) +
|
|
ClassifySolSite(k, k_type, c, r);
|
|
*/
|
|
cs1 = ClassifySolSite(i, i_type, c, r);
|
|
cs2 = ClassifySolSite(j, j_type, c, r);
|
|
cs3 = ClassifySolSite(k, k_type, c, r);
|
|
qual += Max3(cs1, cs2, cs3);
|
|
|
|
/* */
|
|
/* node-radii classification */
|
|
/* */
|
|
if (t3 == PNT) d1 = PntPntDist(c, pi);
|
|
else if (t3 == SEG) d1 = AbsPntLineDist(ai, bi, ci, c);
|
|
else d1 = AbsPntCircleDist(pi, ri, c);
|
|
if (d1 < rad1) qual += rad1 - d1;
|
|
else if (d1 > rad2) qual += d1 - rad2;
|
|
|
|
if (qual < best_qual) {
|
|
best_qual = qual;
|
|
best_sol = m;
|
|
}
|
|
#ifdef VR_TRACE
|
|
if ((i == 6) && (j == 10) && (k == 11)) {
|
|
printf("pot sol[%d] (2): (%20.16f, %20.16f)\nr=%20.16f, q=%20.16f\n",
|
|
m, centers[m].x, centers[m].y, radii[m], qualities[m]);
|
|
}
|
|
#endif
|
|
}
|
|
if ((m == m1) && le(best_qual, DECENT)) break;
|
|
}
|
|
|
|
if (gt(best_qual, GRAZE)) *problematic = true;
|
|
|
|
#ifdef VRONI_INFO
|
|
UpdateRelaxationMemory(VroniMax(eps, best_qual));
|
|
#endif
|
|
|
|
return best_sol;
|
|
}
|
|
|
|
|
|
/* */
|
|
/* intersects the ray originating at pnts[i1], with direction vector v, */
|
|
/* with the bisector e. note that e is defined by i1 and by one other */
|
|
/* site. if an intersection is found then it computes the intersection point */
|
|
/* w and returns true. */
|
|
/* */
|
|
/* note: we assume that v is a unit vector! */
|
|
/* */
|
|
vr_bool vroniObject::IntersectRayBisector(int i1, const coord & v, int e,
|
|
coord *w, double *r2)
|
|
{
|
|
int i2, j;
|
|
t_site t2;
|
|
double t, lgth, a, b, c;
|
|
coord p, q, u;
|
|
double radii[16], rr, qual1, qual2;
|
|
coord centers[16], cc;
|
|
#ifdef GENUINE_ARCS
|
|
double rr2;
|
|
#endif
|
|
int numsol;
|
|
|
|
assert(InPntsList(i1));
|
|
assert(InEdgesList(e));
|
|
assert(IsLftSite(e, i1, PNT) || IsRgtSite(e, i1, PNT));
|
|
assert(eq(VecLen(v) - 1.0, ZERO));
|
|
|
|
if (IsLftSite(e, i1, PNT)) {GetRgtSiteData(e, &i2, &t2);}
|
|
else {GetLftSiteData(e, &i2, &t2);}
|
|
|
|
p = GetPntCoords(i1);
|
|
|
|
switch(t2) {
|
|
case(PNT):
|
|
assert(InPntsList(i2));
|
|
q = GetPntCoords(i2);
|
|
u = VecSub(q, p);
|
|
lgth = VecLenSq(u);
|
|
t = VecDotProd(u, v);
|
|
if (!eq(t, ZERO)) {
|
|
t = lgth / (2.0 * t);
|
|
if (ge(t, ZERO)) {
|
|
*w = RayPnt(p, v, t);
|
|
*r2 = Abs(t);
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
case(SEG):
|
|
assert(InSegsList(i2));
|
|
if (IsSegStartPnt(i2, i1) || IsSegEndPnt(i2, i1)) {
|
|
*w = p;
|
|
*r2 = 0.0;
|
|
return true;
|
|
}
|
|
GetSegEqnData(i2, &a, &b, &c);
|
|
if (!IntersectRayOffsetSeg(p, v, a, b, c, 1, 1, centers, radii,
|
|
&numsol)) {
|
|
/* */
|
|
/* point i1 is too close to (supporting line of) i2 */
|
|
/* */
|
|
SetInvalidSites(i1, PNT, i2, SEG, ZERO_MAX);
|
|
restart = true;
|
|
return false;
|
|
}
|
|
*r2 = -1.0;
|
|
c = VecDotProd(v, p);
|
|
|
|
//Check solutions
|
|
for (j = 0; j < numsol; ++j) {
|
|
cc = centers[j];
|
|
rr = radii[j];
|
|
|
|
/* */
|
|
/* we are interested in a point which is in CI of seg and in the */
|
|
/* positive half-plane defined by the line and which lies on the */
|
|
/* old VD edge */
|
|
/* */
|
|
if (VecDotProd(v, cc) >= c) {
|
|
if( *r2 >= 0.0 ) {
|
|
qual1 = NodeEdgeClassificator(e, *w, ZERO) +
|
|
ClassifySolSite(i1, PNT, *w, *r2) +
|
|
ClassifySolSite(i2, SEG, *w, *r2);
|
|
qual2 = NodeEdgeClassificator(e, cc, ZERO) +
|
|
ClassifySolSite(i1, PNT, cc, rr) +
|
|
ClassifySolSite(i2, SEG, cc, rr);
|
|
if (qual2 < qual1) {
|
|
*r2 = rr;
|
|
*w = cc;
|
|
}
|
|
}
|
|
else {
|
|
*r2 = rr;
|
|
*w = cc;
|
|
}
|
|
}
|
|
}
|
|
return (*r2 >= 0.0) ? true : false;
|
|
#ifdef GENUINE_ARCS
|
|
case(ARC):
|
|
assert(InArcsList(i2));
|
|
|
|
//this is the line orthogonal to v and through the point p.
|
|
|
|
c = VecDotProd(v, p);
|
|
//The arc's circle
|
|
q = GetArcCenter(i2);
|
|
rr2 = GetArcRadius(i2);
|
|
|
|
//Get all points equidistant to the circle, point and line
|
|
numsol = CircCircSegCenters(q, p, rr2, 0, v.x, v.y, c, centers, radii,
|
|
ZERO);
|
|
*r2 = -1.0;
|
|
|
|
//Check solutions
|
|
for(j=0; j<numsol; j++) {
|
|
cc = centers[j];
|
|
rr = radii[j];
|
|
|
|
/* */
|
|
/* we are interested in a point which is in CI of arc and in the */
|
|
/* positive half-plane defined by the line and which lies on the */
|
|
/* old VD edge */
|
|
/* */
|
|
if (VecDotProd(v, cc) >= c) {
|
|
if ( *r2 >= 0.0 ) {
|
|
qual1 = NodeEdgeClassificator(e, *w, ZERO) +
|
|
ClassifySolSite(i1, PNT, *w, *r2) +
|
|
ClassifySolSite(i2, ARC, *w, *r2);
|
|
qual2 = NodeEdgeClassificator(e, cc, ZERO) +
|
|
ClassifySolSite(i1, PNT, cc, rr) +
|
|
ClassifySolSite(i2, ARC, cc, rr);
|
|
if (qual2 < qual1) {
|
|
*r2 = rr;
|
|
*w = cc;
|
|
}
|
|
}
|
|
else {
|
|
*r2 = rr;
|
|
*w = cc;
|
|
}
|
|
}
|
|
}
|
|
|
|
return (*r2 >= 0.0) ? true : false;
|
|
#endif
|
|
|
|
default:
|
|
VD_Warning("IntersectRayBisector() - unrecognized site type");
|
|
return false;
|
|
}
|
|
}
|
|
|
|
|
|
#include "ext_appl_vd.cc"
|
|
|