/*****************************************************************************/ /* */ /* 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 #include #include #include /* */ /* get my header files */ /* */ #include "fpkernel.h" #include "vronivector.h" #include "vroni_object.h" #include "defs.h" #define PAGE_SIZE 32768 #define NotIdenticalPoint(I, J) \ ((pnts[I].p.x != pnts[J].p.x) || (pnts[I].p.y != pnts[J].p.y)) #define StorePIndex(I, J, K, T) \ {\ assert(I < max_num_p_indices); \ assert(InPntsList(J)); \ p_indices[I].site = K; \ p_indices[I].type = T; \ p_indices[I].pnt_data = pnts[J]; \ } void vroniObject::ResetCleanStatus(void) { data_sorted = false; clean_initialized = false; return; } vr_bool vroniObject::InReverseIndList(int i) { return ((i >= 0) && (i < max_num_reverse_ind)); } inline void vroniObject::InsertReverseIndex(const int ipnt, const int isite, const index_type tsite) { assert(InPntsList(ipnt)); assert(InReverseIndList(ipnt)); if (reverse_ind[ipnt].type == ISO_PNT) { assert(reverse_ind[ipnt].next == NIL); reverse_ind[ipnt].site = isite; reverse_ind[ipnt].type = tsite; } else { assert((reverse_ind[ipnt].type == SEG_START) || (reverse_ind[ipnt].type == SEG_END) || (reverse_ind[ipnt].type == ARC_START) || (reverse_ind[ipnt].type == ARC_END)); if (num_reverse_ind >= max_num_reverse_ind) { max_num_reverse_ind += PAGE_SIZE; gentlyResizeSTLVector(reverse_ind, max_num_reverse_ind, "clean_data:reverse_ind"); } reverse_ind[num_reverse_ind].site = isite; reverse_ind[num_reverse_ind].type = tsite; reverse_ind[num_reverse_ind].next = reverse_ind[ipnt].next; reverse_ind[ipnt].next = num_reverse_ind; ++num_reverse_ind; } } #define GetReverseSite(I) (assert(InReverseIndList(I)), reverse_ind[I].site) #define GetReverseType(I) (assert(InReverseIndList(I)), reverse_ind[I].type) #define GetReverseNext(I) (assert(InReverseIndList(I)), reverse_ind[I].next) #define SetReverseSite(I, S) (assert(InReverseIndList(I)), \ reverse_ind[I].site = S) #define SetReverseType(I, T) (assert(InReverseIndList(I)), \ reverse_ind[I].type = T) #define SetReverseNext(I, N) (assert(InReverseIndList(I)), \ reverse_ind[I].next = N) int p_comp(const void *a, const void *b) { if (((pnt*)a)->p.x < ((pnt*)b)->p.x) return -1; else if (((pnt*)a)->p.x > ((pnt*)b)->p.x) return 1; else { if (((pnt*)a)->p.y < ((pnt*)b)->p.y) return -1; else if (((pnt*)a)->p.y > ((pnt*)b)->p.y) return 1; else return 0; } } /* * Defines a lexicographic order on segment indices. The first part is formed * by the smaller index of the two segment points, the second is formed by the * larger index. */ int s_comp(const void *a, const void *b) { if (((seg*)a)->i1 < ((seg*)a)->i2) { if (((seg*)b)->i1 < ((seg*)b)->i2) { if (((seg*)a)->i1 < ((seg*)b)->i1) return -1; else if (((seg*)a)->i1 > ((seg*)b)->i1) return 1; else { if (((seg*)a)->i2 < ((seg*)b)->i2) return -1; else if (((seg*)a)->i2 > ((seg*)b)->i2) return 1; else return 0; } } else { if (((seg*)a)->i1 < ((seg*)b)->i2) return -1; else if (((seg*)a)->i1 > ((seg*)b)->i2) return 1; else { if (((seg*)a)->i2 < ((seg*)b)->i1) return -1; else if (((seg*)a)->i2 > ((seg*)b)->i1) return 1; else return 0; } } } else { if (((seg*)b)->i1 < ((seg*)b)->i2) { if (((seg*)a)->i2 < ((seg*)b)->i1) return -1; else if (((seg*)a)->i2 > ((seg*)b)->i1) return 1; else { if (((seg*)a)->i1 < ((seg*)b)->i2) return -1; else if (((seg*)a)->i1 > ((seg*)b)->i2) return 1; else return 0; } } else { if (((seg*)a)->i2 < ((seg*)b)->i2) return -1; else if (((seg*)a)->i2 > ((seg*)b)->i2) return 1; else { if (((seg*)a)->i1 < ((seg*)b)->i1) return -1; else if (((seg*)a)->i1 > ((seg*)b)->i1) return 1; else return 0; } } } } inline bool s_equal(const seg & a, const seg & b) { return ((a.i1 == b.i1 && a.i2 == b.i2) || (a.i1 == b.i2 && a.i2 == b.i1)); } int a_comp(const void *a, const void *b) { if (((arc*)a)->i1 < ((arc*)b)->i1) return -1; else if (((arc*)a)->i1 > ((arc*)b)->i1) return 1; else { if (((arc*)a)->i2 < ((arc*)b)->i2) return -1; else if (((arc*)a)->i2 > ((arc*)b)->i2) return 1; else { if (((arc*)a)->c.x < ((arc*)b)->c.x) return -1; else if (((arc*)a)->c.x > ((arc*)b)->c.x) return 1; else { if (((arc*)a)->c.y < ((arc*)b)->c.y) return -1; else if (((arc*)a)->c.y > ((arc*)b)->c.y) return 1; else return 0; } } } } inline bool a_equal(const arc & a, const arc & b) { return ((a.i1 == b.i1) && (a.i2 == b.i2) && (a.c.x == b.c.x) && (a.c.y == b.c.y)); } vr_bool vroniObject::GetDataSorted(void) { return data_sorted; } void vroniObject::FreeReverseIndex(void) { reverse_ind.clear(); max_num_reverse_ind = 0; num_reverse_ind = 0; reverse_index_exists = false; return; } void vroniObject::SetUpReverseIndex(int number_of_segs, int number_of_arcs, vr_bool set_idx) { int number, i, j, k; /* */ /* make sure that every point knows all its incident segs and arcs. */ /* */ number = num_pnts + number_of_segs + number_of_arcs; if (number >= max_num_reverse_ind) { max_num_reverse_ind = number; gentlyResizeSTLVector(reverse_ind, max_num_reverse_ind, "clean_data:reverse_ind"); } assert(number >= num_pnts); for (i = 0; i < num_pnts; ++i) { SetReverseType(i, ISO_PNT); SetReverseNext(i, NIL); SetReverseSite(i, i); } num_reverse_ind = num_pnts; if (set_idx) { for (i = 0; i < num_pnts; ++i) { SetPntVDPtr(i, i); } } for (j = 0; j < number_of_segs; ++j) { k = Get1stVtxSeg(j); assert(InPntsList(k)); InsertReverseIndex(k, j, SEG_START); k = Get2ndVtxSeg(j); assert(InPntsList(k)); InsertReverseIndex(k, j, SEG_END); } for (j = 0; j < number_of_arcs; ++j) { k = Get1stVtxArc(j); assert(InPntsList(k)); InsertReverseIndex(k, j, ARC_START); k = Get2ndVtxArc(j); assert(InPntsList(k)); InsertReverseIndex(k, j, ARC_END); } reverse_index_exists = true; return; } /* */ /* this routine sorts all points and vertices in lexicographic order, */ /* eliminates duplicate points/vertices, and discards zero-length segs/arcs. */ /* */ void vroniObject::CleanData(int *removed, int *removed_segs, int *removed_arcs, vr_bool discard_duplicate_sites) { int i, j, k, num_help, nn, number; index_type tsite; int isite, s; if (!clean_initialized) { clean_initialized = true; if (!discard_duplicate_sites) { /* */ /* no need to sort the data; identical points will be discovered on */ /* the fly! */ /* */ *removed = *removed_segs = *removed_arcs = 0; data_sorted = false; reverse_index_exists = false; #ifdef GRAPHICS if (graphics) UpdateBuffer(); #endif return; } num_help = num_pnts; } else { isolated_pnts = false; num_help = num_pnts; } /* */ /* make sure that every point knows all its incident segs and arcs. */ /* */ if ((num_segs > 0) || (num_arcs > 0)) SetUpReverseIndex(num_segs, num_arcs, true); /* */ /* sort pnts[] according to lexicographical order */ /* */ qsort(&(pnts[0]), num_pnts, sizeof(pnt), p_comp); data_sorted = true; /* */ /* re-number the vertices of the data */ /* */ if ((num_segs == 0) && (num_arcs == 0)) { j = 0; for (i = 1; i < num_pnts; ++i) { if (!IsDeletedPnt(i)) { if (NotIdenticalPoint(i, j)) { ++j; pnts[j] = pnts[i]; } #ifdef ORDERED else if (pnts[j].key > pnts[i].key) { pnts[j].key = pnts[i].key; } #endif } } isolated_pnts = true; ++j; num_pnts = j; *removed = num_help - num_pnts; #ifdef GRAPHICS /* */ /* update the drawing buffer accordingly */ /* */ if (graphics) UpdateBuffer(); #endif return; } j = 0; number = num_pnts - 2; for (i = 0; i < num_pnts; ++i) { s = GetPntVDPtr(i); SetPntVDPtr(i, NIL); if (!IsDeletedPnt(i)) { if (NotIdenticalPoint(i, j)) { ++j; pnts[j] = pnts[i]; } #ifdef ORDERED else if (pnts[j].key > pnts[i].key) { pnts[j].key = pnts[i].key; } #endif while (s != NIL) { tsite = GetReverseType(s); isite = GetReverseSite(s); switch(tsite) { case ISO_PNT: if ((i >= 2) && (i < number)) isolated_pnts = true; break; case SEG_START: assert(InSegsList(isite)); Set1stVtxSeg(isite, j); break; case SEG_END: assert(InSegsList(isite)); Set2ndVtxSeg(isite, j); break; case ARC_START: assert(InArcsList(isite)); Set1stVtxArc(isite, j); break; case ARC_END: assert(InArcsList(isite)); Set2ndVtxArc(isite, j); break; default: assert((tsite == SEG_START) || (tsite == SEG_END) || (tsite == ARC_START) || (tsite == ARC_END) || (tsite == ISO_PNT)); break; } s = GetReverseNext(s); } } } ++j; num_pnts = j; *removed = num_help - num_pnts; /* */ /* discard zero-length segs */ /* */ if (num_segs > 0) { i = 0; nn = num_segs; while ((i < num_segs) && (num_segs > 0)) { j = Get1stVtxSeg(i); assert(InPntsList(j)); k = Get2ndVtxSeg(i); assert(InPntsList(k)); if (j == k) { j = num_segs - 1; CopySegData(i, j); num_segs = j; } else { ++i; } } if (discard_duplicate_sites && (num_segs > 0)) { /* */ /* sort segs according to lexicographical order */ /* */ qsort(&(segs[0]), num_segs, sizeof(seg), s_comp); /* */ /* eliminate duplicate segs */ /* */ i = 0; for (j = 1; j < num_segs; ++j) { if (!s_equal(segs[i], segs[j])){ ++i; CopySegData(i, j); } } num_segs = i + 1; } *removed_segs = nn - num_segs; } else { *removed_segs = 0; } #ifdef GENUINE_ARCS /* */ /* discard zero-length arcs */ /* */ if (num_arcs > 0) { i = 0; nn = num_arcs; while ((i < num_arcs) && (num_arcs > 0)) { j = Get1stVtxArc(i); assert(InPntsList(j)); k = Get2ndVtxArc(i); assert(InPntsList(k)); if (j == k) { j = num_arcs - 1; CopyArcData(i, j); num_arcs = j; } else { ++i; } } if (discard_duplicate_sites && (num_arcs > 0)) { /* */ /* sort arcs according to lexicographical order */ /* */ qsort(&(arcs[0]), num_arcs, sizeof(arc), a_comp); /* */ /* eliminate duplicate arcs */ /* */ i = 0; for (j = 1; j < num_arcs; ++j) { if (!a_equal(arcs[i], arcs[j])) { ++i; CopyArcData(i, j); } } num_arcs = i + 1; } *removed_arcs = nn - num_arcs; } else { *removed_arcs = 0; } #else *removed_arcs = 0; #endif FreeReverseIndex(); #ifdef GRAPHICS /* */ /* update the drawing buffer accordingly */ /* */ if (graphics) UpdateBuffer(); #endif return; } void vroniObject::RepairPntLinks(int i_del, int i_old, vr_bool repair_now) { int isite, s, t, tsite; int curr_num_arcs; if (i_old == i_del) return; if (data_sorted && !repair_now) { restart = true; return; } if (!reverse_index_exists) { curr_num_arcs = num_arcs; /* */ /* make sure that every point knows all its incident segs and */ /* arcs. */ /* */ SetUpReverseIndex(num_segs, curr_num_arcs, false); } assert(reverse_index_exists); assert(InPntsList(i_del)); assert(InPntsList(i_old)); /* */ /* reset all links in segs[] and arcs[] that refer to pnts[i_del]. */ /* */ s = i_del; while (s != NIL) { tsite = GetReverseType(s); isite = GetReverseSite(s); switch(tsite) { case SEG_START: assert(InSegsList(isite)); Set1stVtxSeg(isite, i_old); break; case SEG_END: assert(InSegsList(isite)); Set2ndVtxSeg(isite, i_old); break; case ARC_START: assert(InArcsList(isite)); Set1stVtxArc(isite, i_old); break; case ARC_END: assert(InArcsList(isite)); Set2ndVtxArc(isite, i_old); break; default: assert((tsite == SEG_START) || (tsite == SEG_END) || (tsite == ARC_START) || (tsite == ARC_END) || (tsite == ISO_PNT)); break; } s = GetReverseNext(s); } s = i_old; while (s != NIL) { t = GetReverseNext(s); if (t == NIL) SetReverseNext(s, i_del); s = t; } return; }