SaraP
cbec90699f
- creato il progetto in Visual Studio per compilare come libreria statica - modifiche al codice originale per integrarlo nelle nostre librerie.
447 lines
12 KiB
C++
447 lines
12 KiB
C++
/*****************************************************************************/
|
|
/* */
|
|
/* 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 i/o library */
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <assert.h>
|
|
|
|
/* get my header file */
|
|
#include "fpkernel.h"
|
|
#include "martin.h"
|
|
#include "defs.h"
|
|
#include "header.h"
|
|
#include "basic.h"
|
|
|
|
/* */
|
|
/* function prototypes of functions provided in this file */
|
|
/* */
|
|
void InitHeapDefaults(heapdef *hp);
|
|
void FreeHeap(heapdef *hp);
|
|
boolean InHeap(heapdef *hp, list_ind ind);
|
|
void DumpOnHeap(heapdef *hp, machine_double ratio, list_ind ind, list_ind prev,
|
|
list_ind next);
|
|
void InsertIntoHeap(heapdef *hp, machine_double ratio, list_ind ind,
|
|
list_ind prev,
|
|
list_ind next);
|
|
boolean DeleteFromHeap(heapdef *hp, list_ind *ind, list_ind *prev,
|
|
list_ind *next);
|
|
void InitHeap(heapdef *hp, datadef *data);
|
|
void MakeHeap(heapdef *hp);
|
|
|
|
#ifdef PARTITION_FIST
|
|
void InitPartitionedHeap(global_struct *all);
|
|
#endif
|
|
|
|
#define BLOCK_SIZE 65536
|
|
|
|
|
|
#define StoreHeapData(addr, s_ratio, s_ind, s_prev, s_next) \
|
|
{ \
|
|
addr->ratio = s_ratio; \
|
|
addr->index = s_ind; \
|
|
addr->prev = s_prev; \
|
|
addr->next = s_next; \
|
|
}
|
|
|
|
|
|
|
|
#define GetHeapData(addr, s_ind, s_prev, s_next) \
|
|
{ \
|
|
s_ind = addr->index; \
|
|
s_prev = addr->prev; \
|
|
s_next = addr->next; \
|
|
}
|
|
|
|
|
|
|
|
void InitHeapDefaults(heapdef *hp)
|
|
{
|
|
hp->heap = (heap_node*)NULL;
|
|
hp->num_heap = 0;
|
|
hp->max_num_heap = 0;
|
|
hp->num_zero = 0;
|
|
|
|
hp->deleted = false;
|
|
hp->not_updated = false;
|
|
hp->sorted = false;
|
|
hp->ear_right = true;
|
|
}
|
|
|
|
boolean InHeap(heapdef *hp, list_ind ind)
|
|
{
|
|
return ((ind >= 0) && (ind < hp->num_heap));
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void FreeHeap(heapdef *heap)
|
|
{
|
|
#ifdef PARTITION_FIST
|
|
char name[14];
|
|
sprintf(name,"heap:heap%04i",heap->heap_idx);
|
|
FreeMemory(heap->memptr, (void**) &heap->heap, name);
|
|
#else
|
|
FreeMemory(heap->memptr, (void**) &heap->heap, "heap:heap");
|
|
#endif
|
|
|
|
heap->max_num_heap = 0;
|
|
heap->num_heap = 0;
|
|
heap->num_zero = 0;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
void DumpOnHeap(heapdef *hp, machine_double ratio, list_ind ind, list_ind prev,
|
|
list_ind next)
|
|
{
|
|
heap_node *addr;
|
|
|
|
if (hp->num_heap >= hp->max_num_heap) {
|
|
hp->max_num_heap += BLOCK_SIZE;
|
|
#ifdef PARTITION_FIST
|
|
char name[14];
|
|
sprintf(name,"heap:heap%04i",hp->heap_idx);
|
|
hp->heap = (heap_node*) ReallocateArray(hp->memptr, hp->heap, hp->max_num_heap,
|
|
sizeof(heap_node), name);
|
|
#else
|
|
hp->heap = (heap_node*) ReallocateArray(hp->memptr, hp->heap, hp->max_num_heap,
|
|
sizeof(heap_node), "heap:heap");
|
|
#endif
|
|
}
|
|
if (ratio == 0.0) {
|
|
if (hp->num_zero < hp->num_heap) hp->heap[hp->num_heap] = hp->heap[hp->num_zero];
|
|
addr = &(hp->heap[hp->num_zero]);
|
|
++hp->num_zero;
|
|
}
|
|
else {
|
|
addr = &(hp->heap[hp->num_heap]);
|
|
}
|
|
|
|
StoreHeapData(addr, ratio, ind, prev, next);
|
|
++hp->num_heap;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
void UpdateHeap(heapdef *hp, machine_double ratio, list_ind ind, list_ind prev,
|
|
list_ind next)
|
|
{
|
|
int i, j, j1, j2;
|
|
heap_node *addr;
|
|
|
|
i = 0;
|
|
j1 = 2 * i + 1;
|
|
j2 = j1 + 1;
|
|
|
|
while (j2 < hp->num_heap) {
|
|
if (hp->heap[j1].ratio < hp->heap[j2].ratio) j = j1;
|
|
else j = j2;
|
|
|
|
if (hp->heap[j].ratio < ratio) {
|
|
hp->heap[i] = hp->heap[j];
|
|
i = j;
|
|
j1 = 2 * i + 1;
|
|
j2 = j1 + 1;
|
|
}
|
|
else {
|
|
j1 = j2 = hp->num_heap;
|
|
}
|
|
}
|
|
|
|
if (j1 < hp->num_heap) {
|
|
if (hp->heap[j1].ratio < ratio) {
|
|
hp->heap[i] = hp->heap[j1];
|
|
addr = &(hp->heap[j1]);
|
|
StoreHeapData(addr, ratio, ind, prev, next);
|
|
}
|
|
else {
|
|
addr = &(hp->heap[i]);
|
|
StoreHeapData(addr, ratio, ind, prev, next);
|
|
}
|
|
}
|
|
else {
|
|
addr = &(hp->heap[i]);
|
|
StoreHeapData(addr, ratio, ind, prev, next);
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
void ExtendHeap(heapdef *hp, machine_double ratio, list_ind ind, list_ind prev,
|
|
list_ind next)
|
|
{
|
|
int i, j;
|
|
heap_node *addr;
|
|
|
|
if (hp->num_heap == 0) hp->sorted = true;
|
|
else assert(hp->sorted);
|
|
j = hp->num_heap;
|
|
++hp->num_heap;
|
|
|
|
if (hp->num_heap >= hp->max_num_heap) {
|
|
hp->max_num_heap += BLOCK_SIZE;
|
|
#ifdef PARTITION_FIST
|
|
char name[14];
|
|
sprintf(name,"heap:heap%04i",hp->heap_idx);
|
|
hp->heap = (heap_node*) ReallocateArray(hp->memptr, hp->heap, hp->max_num_heap,
|
|
sizeof(heap_node), name);
|
|
#else
|
|
hp->heap = (heap_node*) ReallocateArray(hp->memptr, hp->heap, hp->max_num_heap,
|
|
sizeof(heap_node), "heap:heap");
|
|
#endif
|
|
}
|
|
|
|
while (j > 0) {
|
|
i = (j - 1) / 2;
|
|
if (hp->heap[i].ratio > ratio) {
|
|
hp->heap[j] = hp->heap[i];
|
|
j = i;
|
|
}
|
|
else {
|
|
addr = &(hp->heap[j]);
|
|
StoreHeapData(addr, ratio, ind, prev, next);
|
|
return;
|
|
}
|
|
}
|
|
|
|
addr = &(hp->heap[0]);
|
|
StoreHeapData(addr, ratio, ind, prev, next);
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
void InsertIntoHeap(heapdef *hp, machine_double ratio, list_ind ind, list_ind prev,
|
|
list_ind next)
|
|
{
|
|
if (hp->ears_sorted) {
|
|
if (hp->deleted) {
|
|
UpdateHeap(hp, ratio, ind, prev, next);
|
|
}
|
|
else {
|
|
ExtendHeap(hp, ratio, ind, prev, next);
|
|
}
|
|
hp->deleted = false;
|
|
hp->not_updated = false;
|
|
}
|
|
else {
|
|
DumpOnHeap(hp, ratio, ind, prev, next);
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
boolean DeleteFromHeap(heapdef *hp, list_ind *ind, list_ind *prev, list_ind *next)
|
|
{
|
|
heap_node *addr;
|
|
int rnd_ind, macro_var;
|
|
|
|
if (hp->ears_sorted) {
|
|
/* */
|
|
/* clip ears according to my quality heuristic */
|
|
/* this corresponds to the run-time flags "--sorted", "--fancy", or */
|
|
/* "--top" */
|
|
/* */
|
|
if (hp->deleted && hp->not_updated) {
|
|
if (hp->num_heap <= 1) {
|
|
hp->num_heap = 0;
|
|
return false;
|
|
}
|
|
--hp->num_heap;
|
|
assert(hp->sorted);
|
|
addr = &(hp->heap[hp->num_heap]);
|
|
UpdateHeap(hp, addr->ratio, addr->index, addr->prev, addr->next);
|
|
hp->not_updated = false;
|
|
hp->deleted = false;
|
|
}
|
|
else if (hp->num_heap <= 0)
|
|
return false;
|
|
|
|
assert(hp->sorted);
|
|
addr = &(hp->heap[0]);
|
|
GetHeapData(addr, *ind, *prev, *next);
|
|
hp->not_updated = true;
|
|
hp->deleted = true;
|
|
|
|
return true;
|
|
}
|
|
else if (hp->num_zero > 0) {
|
|
/* */
|
|
/* if we don't use sorted or fancy clipping then I make sure to clip */
|
|
/* degenerate ears first. such ears have 0.0 as their quality! */
|
|
/* */
|
|
assert(hp->num_heap >= hp->num_zero);
|
|
--hp->num_zero;
|
|
--hp->num_heap;
|
|
addr = &(hp->heap[hp->num_zero]);
|
|
GetHeapData(addr, *ind, *prev, *next);
|
|
hp->heap[hp->num_zero] = hp->heap[hp->num_heap];
|
|
return true;
|
|
}
|
|
else if (hp->ears_random) {
|
|
/* */
|
|
/* clip ears in random order. */
|
|
/* this corresponds to the run-time flag "--random" */
|
|
/* */
|
|
if (hp->num_heap <= 0) {
|
|
hp->num_heap = 0;
|
|
return false;
|
|
}
|
|
rnd_ind = RandomInteger(macro_var,hp->num_heap);
|
|
assert((rnd_ind >= 0) && (rnd_ind < hp->num_heap));
|
|
--hp->num_heap;
|
|
addr = &(hp->heap[rnd_ind]);
|
|
GetHeapData(addr, *ind, *prev, *next);
|
|
hp->heap[rnd_ind] = hp->heap[hp->num_heap];
|
|
|
|
return true;
|
|
}
|
|
else {
|
|
/* */
|
|
/* let's clip the ears in the inverse order as we find them. */
|
|
/* this corresponds to the run-time flag "--sequen" */
|
|
/* */
|
|
if (hp->num_heap <= 0) {
|
|
hp->num_heap = 0;
|
|
return false;
|
|
}
|
|
--hp->num_heap;
|
|
addr = &(hp->heap[hp->num_heap]);
|
|
GetHeapData(addr, *ind, *prev, *next);
|
|
|
|
return true;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|
|
void InitHeap(heapdef *hp, datadef *data)
|
|
{
|
|
if (hp->heap == (heap_node*)NULL) hp->max_num_heap = 0;
|
|
if ((2 * data->num_pnts) > hp->max_num_heap) {
|
|
hp->max_num_heap = 2 * data->num_pnts;
|
|
#ifdef PARTITION_FIST
|
|
char name[14];
|
|
sprintf(name,"heap:heap%04i",hp->heap_idx);
|
|
hp->heap = (heap_node*) ReallocateArray(hp->memptr, hp->heap, hp->max_num_heap,
|
|
sizeof(heap_node), name);
|
|
#else
|
|
hp->heap = (heap_node*) ReallocateArray(hp->memptr, hp->heap, hp->max_num_heap,
|
|
sizeof(heap_node), "heap:heap");
|
|
#endif
|
|
}
|
|
hp->num_heap = 0;
|
|
hp->deleted = false;
|
|
hp->not_updated = false;
|
|
hp->sorted = false;
|
|
hp->num_zero = 0;
|
|
hp->ear_right = true;
|
|
|
|
return;
|
|
}
|
|
|
|
#ifdef PARTITION_FIST
|
|
void InitPartitionedHeap(global_struct *all) {
|
|
heapdef *hp;
|
|
|
|
all->c_heap = (heapdef*)NULL;
|
|
all->corner_nodes = (list_ind*)NULL;
|
|
|
|
all->c_heap = (heapdef*) ReallocateArray((debug_memdef*)&all->c_mem, all->c_heap,
|
|
all->number_of_heaps,
|
|
sizeof(heapdef), "all:heaps");
|
|
|
|
all->corner_nodes = (list_ind*) ReallocateArray((debug_memdef*)&all->c_mem,
|
|
all->corner_nodes,
|
|
all->number_of_heaps,
|
|
sizeof(list_ind), "all:corners");
|
|
|
|
for(int i = 0; i < all->number_of_heaps; ++i) {
|
|
hp = &all->c_heap[i];
|
|
hp->heap_idx = i;
|
|
hp->heap = (heap_node*)NULL;
|
|
}
|
|
}
|
|
#endif
|
|
|
|
|
|
void MakeHeap(heapdef *hp)
|
|
{
|
|
int h_comp(const void *, const void *);
|
|
|
|
if (!hp->ears_sorted) return;
|
|
|
|
/* */
|
|
/* sort the heap entries according to their ratios */
|
|
/* */
|
|
qsort(hp->heap, hp->num_heap, sizeof(heap_node), &h_comp);
|
|
hp->sorted = true;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
int h_comp(const void *a, const void *b)
|
|
{
|
|
if (((heap_node*)a)->ratio < ((heap_node*)b)->ratio) return -1;
|
|
else if (((heap_node*)a)->ratio > ((heap_node*)b)->ratio) return 1;
|
|
else return 0;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void TestTree(heapdef *hp)
|
|
{
|
|
int i, i1, i2, bound;
|
|
|
|
if (hp->num_heap <= 1) return;
|
|
|
|
bound = (hp->num_heap + 1) / 2 - 1;
|
|
|
|
for (i = 0; i < bound; ++i) {
|
|
i1 = 2 * i + 1;
|
|
i2 = i1 + 1;
|
|
assert(hp->heap[i1].ratio >= hp->heap[i].ratio);
|
|
assert(hp->heap[i2].ratio >= hp->heap[i].ratio);
|
|
}
|
|
|
|
i = bound;
|
|
i1 = 2 * i + 1;
|
|
i2 = i1 + 1;
|
|
|
|
if (i1 < hp->num_heap) assert(hp->heap[i1].ratio >= hp->heap[i].ratio);
|
|
if (i2 < hp->num_heap) assert(hp->heap[i2].ratio >= hp->heap[i].ratio);
|
|
|
|
return;
|
|
}
|