Egalware/fist
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
fist/bridge.cpp
T
SaraP cbec90699f FIST 6.8 : 
- creato il progetto in Visual Studio per compilare come libreria statica
- modifiche al codice originale per integrarlo nelle nostre librerie.
2025-03-04 16:19:35 +01:00

483 lines
18 KiB
C++
Raw Permalink Blame History

/*****************************************************************************/
/* */
/* F I S T : Fast, Industrial-Strength Triangulation */
/* */
/*****************************************************************************/
/* */
/* (C) Martin Held */
/* (C) Universitaet Salzburg, Salzburg, Austria */
/* */
/* This code is not in the public domain. All rights reserved! Please make */
/* sure to read the full copyright statement contained in api_functions.cpp. */
/* */
/*****************************************************************************/
/* */
/* get standard libraries */
/* */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
/* */
/* get my header files */
/* */
#include "fpkernel.h"
#include "martin.h"
#include "defs.h"
#include "list.h"
#include "header.h"
#include "basic.h"
#include "numerics.h"
#include "bv_tree.h"
#ifdef GRAPHICS
#include "graphics.h"
#endif
/* */
/* function prototypes of functions provided in this file */
/* */
void FindLeftMostVertex(listdef* list, list_ind ind, list_ind *left_ind, int *left_i);
void ConstructBridges(global_struct* all, int i1, int i2);
boolean FindBridge(global_struct *all, list_ind ind, int i, int start, list_ind *ind1, int *i1);
void InsertBridge(global_struct *all, list_ind ind1, int i1, list_ind ind3, int i3);
void SimpleBridge(global_struct *all, list_ind ind1, list_ind ind2);
void FreeBridges(bridgedef* bridge);
int d_comp(const void *a, const void *);
int l_comp(const void *a, const void *);
#define BLOCK_SIZE 65536
void InitBridgeDefaults(bridgedef* bridge)
{
bridge->distances = (distance*)NULL;
bridge->max_num_dist = 0;
bridge->left_most = (left*)NULL;
bridge->max_num_left_most = 0;
}
/* */
/* This routine constructs bridges for a multiply-connected polygon. */
/* A "bridge" is nothing but a pair of segments that is used for linking an */
/* island loop with a boundary loop. That is, it transforms a */
/* multiply-connected polygon into a simply-connected polygon. Formally */
/* speaking, the resulting polygon isn't truly simple as part of its */
/* boundary overlaps (at the bridges). */
/* */
/* Of course, the bridge routines also have a "desperate mode"!! E.g., we */
/* have to handle islands whose left-most point lies outside of the boundary */
/* polygon, and similar problems... */
/* */
void ConstructBridges(global_struct* all, int loop_min, int loop_max)
{
#ifndef NDEBUG
griddef *grid = &all->c_grid;
#endif
listdef *list = &all->c_list;
bridgedef *bridge = &all->c_bridge;
datadef *data = &all->c_data;
int i0, i, j, i1, num_dist, num_left_most;
int ind0, ind1;
assert(!grid->no_grid_yet);
assert(loop_max > loop_min);
assert(loop_min >= 0);
assert(loop_max <= all->c_list.num_loops);
num_left_most = loop_max - loop_min - 1;
if (num_left_most > bridge->max_num_left_most) {
bridge->max_num_left_most = num_left_most;
bridge->left_most =
(left*) ReallocateArray(bridge->memptr, bridge->left_most,
bridge->max_num_left_most,
sizeof(left), "bridge:left_most");
}
/* */
/* insert all vertices of the outer loop into a grid structure */
/* */
BuildBridgeBuckets(all, list->loops[loop_min], true);
/* */
/* for each contour, find the left-most vertex. (we will use the fact */
/* that the vertices appear in sorted order!) */
/* */
FindLeftMostVertex(list, list->loops[loop_min], &ind0, &i0);
j = 0;
for (i = loop_min + 1; i < loop_max; ++i) {
FindLeftMostVertex(list, list->loops[i], &(bridge->left_most[j].ind),
&(bridge->left_most[j].index));
++j;
}
/* */
/* sort the inner contours according to their left-most vertex */
/* */
qsort(bridge->left_most, num_left_most, sizeof(left), &l_comp);
/* */
/* construct bridges. every bridge will eminate at the left-most point of */
/* its corresponding inner loop. */
/* */
num_dist = data->num_pnts + 2 * list->num_loops;
if (num_dist > bridge->max_num_dist) {
bridge->distances = CORE_ReallocateArray(bridge->memptr,
bridge->distances,
bridge->max_num_dist,
num_dist, distance,
"bridge:distances");
bridge->max_num_dist = num_dist;
}
for (j = 0; j < num_left_most; ++j) {
if (!FindBridge(all, ind0, i0, bridge->left_most[j].index, &ind1, &i1)) {
if (all->rt_opt.verbose)
FIST_Warning("ConstructBridges() -- the contour loops intersect!\n");
}
/* */
/* insert all vertices of the current hole loop into a grid structure */
/* */
BuildBridgeBuckets(all, bridge->left_most[j].ind, false);
if (i1 == bridge->left_most[j].index)
/* */
/* the left-most node of the hole coincides with a node of the */
/* boundary */
/* */
SimpleBridge(all, ind1, bridge->left_most[j].ind);
else
/* */
/* two bridge edges need to be inserted */
/* */
InsertBridge(all, ind1, i1, bridge->left_most[j].ind,
bridge->left_most[j].index);
}
return;
}
void SimpleBridge(global_struct *all, list_ind ind1, list_ind ind2)
{
listdef *list = &all->c_list;
datadef *data = &all->c_data;
list_ind prev, next;
int i1, i2, prv, nxt;
int angle;
/* */
/* change the links */
/* */
RotateLinks(list, ind1, ind2);
/* */
/* reset the angles */
/* */
i1 = GetIndex(list, ind1);
next = GetNextNode(list, ind1);
nxt = GetIndex(list, next);
prev = GetPrevNode(list, ind1);
prv = GetIndex(list, prev);
angle = IsConvexAngle(list, data, prv, i1, nxt, ind1);
SetAngle(list, ind1, angle);
#ifdef GRAPHICS
if (all->rt_opt.graphics) {
if (angle == 1) DrawPnt(data->points[i1], ConvexColor);
else if (angle == 2) DrawPnt(data->points[i1], ZeroColor);
else if (angle == 0) DrawPnt(data->points[i1], TangentColor);
}
#endif
i2 = GetIndex(list, ind2);
next = GetNextNode(list, ind2);
nxt = GetIndex(list, next);
prev = GetPrevNode(list, ind2);
prv = GetIndex(list, prev);
angle = IsConvexAngle(list, data, prv, i2, nxt, ind2);
SetAngle(list, ind2, angle);
SetBridgeNodePair(list, ind1, ind2);
return;
}
void InsertBridge(global_struct *all, list_ind ind1, int i1, list_ind ind3, int i3) {
griddef *grid = &all->c_grid;
listdef *list = &all->c_list;
datadef *data = &all->c_data;
list_ind ind2, ind4, prev, next;
int prv, nxt, angle;
bounding_box bb;
/* */
/* duplicate nodes in order to form end points of the bridge edges */
/* */
ind2 = MakeNode(list, i1);
InsertAfter(list, ind1, ind2);
SetOriginal(list, ind2, GetOriginal(list, ind1));
ind4 = MakeNode(list, i3);
InsertAfter(list, ind3, ind4);
SetOriginal(list, ind4, GetOriginal(list, ind3));
/* */
/* insert the bridge edges into the boundary loops */
/* */
SplitSplice(list, ind1, ind2, ind3, ind4);
#ifdef GRAPHICS
/* */
/* update the graphics */
/* */
if (all->rt_opt.graphics) {
DrawSeg(data->points[i1], data->points[i3], BridgeColor);
AddEdgeToBuffer(&all->c_redraw, i1, i3, BridgeColor);
}
#endif
/* */
/* reset the angles */
/* */
next = GetNextNode(list, ind1);
nxt = GetIndex(list, next);
prev = GetPrevNode(list, ind1);
prv = GetIndex(list, prev);
angle = IsConvexAngle(list, data, prv, i1, nxt, ind1);
SetAngle(list, ind1, angle);
#ifdef GRAPHICS
if (all->rt_opt.graphics) {
if (angle == 1) DrawPnt(data->points[i1], ConvexColor);
else if (angle == 2) DrawPnt(data->points[i1], ZeroColor);
else if (angle == 0) DrawPnt(data->points[i1], TangentColor);
}
#endif
next = GetNextNode(list, ind2);
nxt = GetIndex(list, next);
prev = GetPrevNode(list, ind2);
prv = GetIndex(list, prev);
angle = IsConvexAngle(list, data, prv, i1, nxt, ind2);
SetAngle(list, ind2, angle);
next = GetNextNode(list, ind3);
nxt = GetIndex(list, next);
prev = GetPrevNode(list, ind3);
prv = GetIndex(list, prev);
angle = IsConvexAngle(list, data, prv, i3, nxt, ind3);
SetAngle(list, ind3, angle);
#ifdef GRAPHICS
if (all->rt_opt.graphics) {
if (angle == 1) DrawPnt(data->points[i3], ConvexColor);
else if (angle == 2) DrawPnt(data->points[i3], ZeroColor);
else if (angle == 0) DrawPnt(data->points[i3], TangentColor);
}
#endif
next = GetNextNode(list, ind4);
nxt = GetIndex(list, next);
prev = GetPrevNode(list, ind4);
prv = GetIndex(list, prev);
angle = IsConvexAngle(list, data, prv, i3, nxt, ind4);
SetAngle(list, ind4, angle);
BBox(data, i1, i3, bb);
if(!grid->no_grid_yet)
InsertSegmentIntoGrid(data, grid, bb);
SetBridgeNodePair(list, ind1, ind2);
SetBridgeNodePair(list, ind3, ind4);
return;
}
/* */
/* we try to find a vertex i1 on the loop which contains i such that i1 */
/* is close to start, and such that i1, start is a valid diagonal */
/* */
boolean FindBridge(global_struct *all, list_ind ind, int i, int start, list_ind *ind1, int *i1)
{
datadef *data = &all->c_data;
listdef *list = &all->c_list;
bridgedef *bridge = &all->c_bridge;
tmp_data_def tmp_data;
int i0, i2, j, num_dist, grid_offset, number_of_tries;
list_ind ind0, ind2;
bounding_box bb;
boolean convex, cone_ok, grid_exhausted, check_cone, cone_strict;
#ifdef GRAZING
machine_double x_start;
#endif
/* */
/* sort the points according to their distance from start. */
/* */
*ind1 = ind;
*i1 = i;
if (*i1 == start) return true;
cone_strict = true;
check_cone = true;
cone_ok = true;
number_of_tries = 0;
do {
num_dist = 0;
grid_offset = 0;
#ifdef GRAZING
x_start = data->points[start].x + EPS;
#endif
do {
/* */
/* find a valid diagonal. note that no node with index i1 > start */
/* can be feasible! (if --DGRAZING is specified at compile time */
/* then we also consider points i1 with x-coordinate similar to */
/* that of start. */
/* */
#ifdef GRAZING
ScanBridgeBuckets(all, start, grid_offset, bridge->distances,
&num_dist, &grid_exhausted, x_start);
#else
ScanBridgeBuckets(all, start, grid_offset, bridge->distances,
&num_dist, &grid_exhausted);
#endif
qsort(bridge->distances, num_dist, sizeof(distance), &d_comp);
for (j = 0; j < num_dist; ++j) {
*ind1 = bridge->distances[j].ind;
*i1 = GetIndex(list,*ind1);
if (*i1 == start) return true;
ind0 = GetPrevNode(list,*ind1);
i0 = GetIndex(list,ind0);
ind2 = GetNextNode(list,*ind1);
i2 = GetIndex(list,ind2);
convex = GetAngle(list,*ind1) > 0;
if (check_cone) {
#ifdef GRAZING
IsInConeEps(data, tmp_data, i0, *i1, i2, start, convex,
cone_ok);
#else
if (cone_strict) {
IsInConeStrict(data, tmp_data, i0, *i1, i2, start, convex,
cone_ok, THRES);
}
else {
IsInCone(data, tmp_data, i0, *i1, i2, start, convex,
cone_ok);
}
#endif
}
if (cone_ok) {
BBox(data, *i1, start, bb);
if (!GridIntersectionExists(all, bb, -1, -1, *ind1, -1)) {
return check_cone;
}
}
}
++grid_offset;
} while (!grid_exhausted);
/* */
/* the left-most point of the hole does not lie within the outer */
/* boundary! what is the best bridge in this case??? we'll make a */
/* brute-force decision... */
/* */
++number_of_tries;
if (number_of_tries == 1) {
cone_strict = false;
cone_ok = true;
}
else if (number_of_tries == 2) {
check_cone = false;
cone_ok = true;
}
} while (number_of_tries <= 3);
/* */
/* still no diagonal??? yikes! oh well, this polygon is messed up badly! */
/* time for genuine desperate mode... */
/* */
*ind1 = ind;
*i1 = i;
return false;
}
void FindLeftMostVertex(listdef* list, list_ind ind, list_ind *left_ind, int *left_i)
{
list_ind ind1;
int i1;
i1 = GetIndex(list,ind);
*left_ind = ind;
*left_i = i1;
ind1 = GetNextNode(list,ind);
i1 = GetIndex(list,ind1);
while (ind1 != ind) {
if (i1 < *left_i) {
*left_ind = ind1;
*left_i = i1;
}
else if (i1 == *left_i) {
if (GetAngle(list,ind1) < 0) {
*left_ind = ind1;
*left_i = i1;
}
}
ind1 = GetNextNode(list,ind1);
i1 = GetIndex(list,ind1);
}
return;
}
int l_comp(const void *a, const void *b)
{
if (((left*)a)->index < ((left*)b)->index) return -1;
else if (((left*)a)->index > ((left*)b)->index) return 1;
else return 0;
}
int d_comp(const void *a, const void *b)
{
if (((distance*)a)->dist < ((distance*)b)->dist) return -1;
else if (((distance*)a)->dist > ((distance*)b)->dist) return 1;
else return 0;
}
void FreeBridges(bridgedef* bridge)
{
bridge->max_num_dist = 0;
bridge->max_num_left_most = 0;
FreeMemory(bridge->memptr, (void**) &bridge->left_most, "bridge:left_most");
CORE_FreeMemory(bridge->memptr, &bridge->distances, "bridge:distances");
return;
}
Reference in New Issue View Git Blame Copy Permalink