/*****************************************************************************/ /* */ /* Copyright (C) 2002--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 #include /* */ /* get my header files */ /* */ #include "vroni_object.h" #include "fpkernel.h" #include "numerics.h" #include "approx.h" #define SAMPLE_RATE 0.1 #define PAGE_SIZE 32768 #define UpdateBoundingBox(XC, YC) \ {\ if (XC > bb_max.x) bb_max.x = XC; \ else if (XC < bb_min.x) bb_min.x = XC; \ if (YC > bb_max.y) bb_max.y = YC; \ else if (YC < bb_min.y) bb_min.y = YC; \ } void vroniObject::ApproxArcsHeuristic(int approx) { int i1, i2, i3, i4; double xc1, yc1, xc3, yc3, angle_s, angle_e; double x_dist, y_dist, dist, min, radius, incr, alpha; coord p1, p2, p3; int i; #ifdef EXT_APPL_SITES eas_type ext_appl; #endif assert(approx > 0); x_dist = bb_max.x - bb_min.x; y_dist = bb_max.y - bb_min.y; dist = VroniMax(x_dist, y_dist); assert(dist > 0.0); if (eq(dist, ZERO)) dist = 1.0; for (i = 0; i < num_arcs; ++i) { /* */ /* obtain the arc data. */ /* */ p1 = GetArcStartCoord(i); p2 = GetArcEndCoord(i); p3 = GetArcCenter(i); radius = GetArcRadius(i); #ifdef EXT_APPL_SITES ext_appl = GetExtApplArc(i); #endif /* */ /* discretize the arc and replace it by line segments. */ /* */ if (GetArcOrientation(i)) { /* */ /* the original orientation of the arc was CCW. note that we */ /* store all input arcs as CCW arcs! */ /* */ i1 = Get1stVtx(i, ARC); i2 = Get2ndVtx(i, ARC); xc1 = p1.x; yc1 = p1.y; xc3 = p3.x; yc3 = p3.y; angle_s = atan2(yc1 - yc3, xc1 - xc3); angle_e = atan2(p2.y - yc3, p2.x - xc3); 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; if (gt(radius, ZERO)) incr = M_2PI * dist / (radius * approx); else incr = M_2PI; min = (angle_e - angle_s) / 2.99; incr = VroniMin(incr, min); angle_e -= incr; alpha = angle_s + incr; while (alpha < angle_e) { xc1 = xc3 + radius * cos(alpha); yc1 = yc3 + radius * sin(alpha); #ifdef EXT_APPL_PNTS i4 = StorePnt(xc1, yc1, eap_NIL); #else i4 = StorePnt(xc1, yc1); #endif UpdateBoundingBox(xc1, yc1); #ifdef EXT_APPL_SITES i3 = StoreSeg(i1, i4, ext_appl); #else i3 = StoreSeg(i1, i4); #endif #ifdef GRAPHICS if (graphics) { AddSegToBuffer(i3, ArcColor); AddPntToBuffer(i4, ArcColor); } #endif i1 = i4; alpha += incr; } alpha = alpha + (angle_e - alpha) / 2.0; xc1 = xc3 + radius * cos(alpha); yc1 = yc3 + radius * sin(alpha); #ifdef EXT_APPL_PNTS i4 = StorePnt(xc1, yc1, eap_NIL); #else i4 = StorePnt(xc1, yc1); #endif UpdateBoundingBox(xc1, yc1); #ifdef EXT_APPL_SITES i3 = StoreSeg(i1, i4, ext_appl); #else i3 = StoreSeg(i1, i4); #endif #ifdef GRAPHICS if (graphics) { AddSegToBuffer(i3, ArcColor); AddPntToBuffer(i4, ArcColor); } #endif #ifdef EXT_APPL_SITES i3 = StoreSeg(i4, i2, ext_appl); #else i3 = StoreSeg(i4, i2); #endif #ifdef GRAPHICS if (graphics) { AddSegToBuffer(i3, ArcColor); } #endif } else { /* */ /* the original orientation of the arc was CW. note that we */ /* store all input arcs as CCW arcs! */ /* */ i1 = Get1stVtx(i, ARC); i2 = Get2ndVtx(i, ARC); xc1 = p1.x; yc1 = p1.y; xc3 = p3.x; yc3 = p3.y; angle_s = atan2(yc1 - yc3, xc1 - xc3); angle_e = atan2(p2.y - yc3, p2.x - xc3); 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; if (gt(radius, ZERO)) incr = M_2PI * dist / (radius * approx); else incr = M_2PI; min = (angle_e - angle_s) / 2.99; incr = VroniMin(incr, min); angle_s += incr; alpha = angle_e - incr; while (alpha > angle_s) { xc1 = xc3 + radius * cos(alpha); yc1 = yc3 + radius * sin(alpha); #ifdef EXT_APPL_PNTS i4 = StorePnt(xc1, yc1, eap_NIL); #else i4 = StorePnt(xc1, yc1); #endif UpdateBoundingBox(xc1, yc1); #ifdef EXT_APPL_SITES i3 = StoreSeg(i2, i4, ext_appl); #else i3 = StoreSeg(i2, i4); #endif #ifdef GRAPHICS if (graphics) { AddSegToBuffer(i3, ArcColor); AddPntToBuffer(i4, ArcColor); } #endif i2 = i4; alpha -= incr; } alpha = alpha + (angle_s - alpha) / 2.0; xc1 = xc3 + radius * cos(alpha); yc1 = yc3 + radius * sin(alpha); #ifdef EXT_APPL_PNTS i4 = StorePnt(xc1, yc1, eap_NIL); #else i4 = StorePnt(xc1, yc1); #endif UpdateBoundingBox(xc1, yc1); #ifdef EXT_APPL_SITES i3 = StoreSeg(i2, i4, ext_appl); #else i3 = StoreSeg(i2, i4); #endif #ifdef GRAPHICS if (graphics) { AddSegToBuffer(i3, ArcColor); AddPntToBuffer(i4, ArcColor); } #endif #ifdef EXT_APPL_SITES i3 = StoreSeg(i4, i1, ext_appl); #else i3 = StoreSeg(i4, i1); #endif #ifdef GRAPHICS if (graphics) { AddSegToBuffer(i3, ArcColor); } #endif } } /* */ /* no circular arcs left! */ /* */ num_arcs = 0; return; } /* */ /* this routine allows to replace (input) circular arcs by polygonal */ /* approximations. let A be an arc with center C and radius R. */ /* a polygonal approximation APX of A is considered valid with respect */ /* to the user-specified (non-negative) parameter apx_absolute if the */ /* following inequality holds for all points P of APX: */ /* R <= d(C,P) <= R + apx_absolute, */ /* where d(C,P) denotes the Euclidean distance between C and P. */ /* similarly, APX is valid with respect to apx_relative if */ /* R <= d(C,P) <= R * (1 + apx_relative) */ /* for all P of APX. */ /* */ /* the polygonal approximation APX is obtained as a sequence of line */ /* segments that are tangent to A. furthermore, all line segments of APX */ /* are assigned the index of A in order to facilitate the computation of */ /* the VD and to help with the subsequent recovery of the approximate VD of */ /* the original arcs. while this routine may be used as a blueprint for */ /* modeling your own arc approximation, the flag arcs_apx may >>only<< be */ /* set if exactly this approximation mechanism has been used -- the validity */ /* of the simplified computations carried out by VRONI if two segments are */ /* derived from the same arc depends on the properties of my approximation */ /* mechanism!!!! */ /* */ /* furthermore, please be warned that the simplified VD computation is bound */ /* to run into problems if the radii of an arc's start point and end point */ /* differ! for this reason, AdjustArcs() is called in order to adapt the */ /* radii and adjust the center, if needed. obviously, adjusting the center */ /* will destroy tangency properties between subsequent arcs. since there is */ /* no obviously correct way to deal with inconsistent radii, the user is */ /* strongly urged to supply the coordinates of the start point, end point */ /* and center of every arc with >maximum< (double) precision, and to */ /* re-compute this data prior to calling VRONI (if needed), rather than to */ /* force VRONI to adjust the center and radii in its own way!!! */ /* */ /* note: if the input data is scaled by VRONI to make it fit into the unit */ /* square, then the thresholds apx_absolute and apx_relative are adjusted */ /* appropriately by VRONI. thus, if scaling was performed then the */ /* thresholds used within this routine need not equal the thresholds input */ /* by the user. */ /* */ void vroniObject::ApproxArcsBounded(double apx_absolute, double apx_relative) { #ifndef ARC_APX if ((num_arcs > 0) && ((apx_absolute > 0.0) || (apx_relative > 0.0))) { VD_Warning("ApproxArcsBounded() - compile-time option `-DARC_APX' not used!\n"); return; } #else int i, i1, i2, i3, i4, k, number; double xc3, yc3, xc4, yc4; double radius, max_incr; coord p1, p2, p3; int num_critical_arcs; vr_bool ccw_orientation; #ifdef EXT_APPL_SITES eas_type ext_appl; #endif vronivector apx_vtx; int max_num_apx_vtx = 0; /* */ /* memorize the number of input points and line segments! (approximating */ /* the circular arcs will add a few line segments...) */ /* */ SetOriginalSegNumber(); SetOriginalPntNumber(); /* make sure that all circular arcs have consistent radii. if necessary, */ /* we'll adjust the centers!! */ /* */ PreprocessArcs(&num_critical_arcs); /* */ /* compute the maximum angular increment if relative errors are to be */ /* used */ /* */ assert((apx_absolute > 0.0) || (apx_relative > 0.0)); if (apx_relative > 0.0) { apx_absolute = 0.0; if (apx_relative > (M_SQRT2 - 1.0)) { apx_relative = M_SQRT2 - 1.0; max_incr = M_PI_4 / 4.0; } else { max_incr = acos(1.0 / (1.0 + apx_relative)); } } else if (apx_absolute <= 0.0) { return; } else { if (data_scaled) { assert(gt(scale_factor, ZERO)); apx_absolute *= scale_factor; } max_incr = M_PI_4 / 4.0; } for (i = 0; i < num_arcs; ++i) { /* */ /* obtain the arc data. */ /* */ p1 = GetArcStartCoord(i); p2 = GetArcEndCoord(i); p3 = GetArcCenter(i); radius = GetArcRadius(i); assert(gt(radius, ZERO)); xc3 = p3.x; yc3 = p3.y; #ifdef EXT_APPL_SITES ext_appl = GetExtApplArc(i); #endif /* */ /* discretize the arc and replace it by line segments. */ /* */ if (GetArcOrientation(i)) { /* */ /* the original orientation of the arc was CCW. note that we */ /* store all input arcs as CCW arcs! */ /* */ i1 = Get1stVtx(i, ARC); i2 = Get2ndVtx(i, ARC); ccw_orientation = true; } else { /* */ /* the original orientation of the arc was CW. */ /* */ i2 = Get1stVtx(i, ARC); i1 = Get2ndVtx(i, ARC); ccw_orientation = false; } /* */ /* compute the new pnts and segs */ /* */ ApproxArc(p1, p2, xc3, yc3, radius, ccw_orientation, apx_absolute, apx_vtx, max_num_apx_vtx, max_incr, number); /* */ /* store the new pnts and segs */ /* */ for (k = 0; k < number; ++k) { xc4 = apx_vtx[k].x; yc4 = apx_vtx[k].y; #ifdef EXT_APPL_PNTS i4 = StorePnt(xc4, yc4, eap_NIL); #else i4 = StorePnt(xc4, yc4); #endif SetPntArc(i4, i); UpdateBoundingBox(xc4, yc4); #ifdef EXT_APPL_SITES i3 = StoreSeg(i1, i4, ext_appl); #else i3 = StoreSeg(i1, i4); #endif SetSegArc(i3, i); #ifdef GRAPHICS if (graphics) { AddSegToBuffer(i3, ArcColor); AddPntToBuffer(i4, ArcColor); } #endif i1 = i4; } #ifdef EXT_APPL_SITES i3 = StoreSeg(i1, i2, ext_appl); #else i3 = StoreSeg(i1, i2); #endif SetSegArc(i3, i); #ifdef GRAPHICS if (graphics) AddSegToBuffer(i3, ArcColor); #endif } /* */ /* no circular arcs left! */ /* */ apx_vtx.clear(); SetOriginalArcNumber(); num_arcs = 0; return; #endif } void vroniObject::SampleData(int sample) { int i, i4; double radius, sample_rate, xc1, yc1, xc3, yc3, angle_s, angle_e; coord vec, a, p1, p2, p3; double incr, min, x_dist, y_dist, dist, delta, alpha; assert(sample > 0); isolated_pnts = true; x_dist = bb_max.x - bb_min.x; y_dist = bb_max.y - bb_min.y; dist = VroniMax(x_dist, y_dist); assert(dist > 0.0); if (eq(dist, ZERO)) dist = 1.0; sample_rate = dist * SAMPLE_RATE / sample; for (i = 0; i < num_segs; ++i) { p1 = GetSegStartCoord(i); p2 = GetSegEndCoord(i); vec = VecSub(p2, p1); delta = VecLen(vec); if (gt(delta, ZERO) && (sample_rate < delta)) { vec = VecDiv(delta, vec); incr = sample_rate; delta -= sample_rate; while (incr < delta) { a = RayPnt(p1, vec, incr); #ifdef EXT_APPL_PNTS i4 = StorePnt(a.x, a.y, eap_NIL); #else i4 = StorePnt(a.x, a.y); #endif #ifdef GRAPHICS if (graphics) AddPntToBuffer(i4, SegColor); #endif incr += sample_rate; } incr = incr + (delta - incr) / 2.0; a = RayPnt(p1, vec, incr); #ifdef EXT_APPL_PNTS i4 = StorePnt(a.x, a.y, eap_NIL); #else i4 = StorePnt(a.x, a.y); #endif #ifdef GRAPHICS if (graphics) AddPntToBuffer(i4, SegColor); #endif } } sample_rate /= 2.0; for (i = 0; i < num_arcs; ++i) { p1 = GetArcStartCoord(i); p2 = GetArcEndCoord(i); p3 = GetArcCenter(i); radius = GetArcRadius(i); xc1 = p1.x; yc1 = p1.y; xc3 = p3.x; yc3 = p3.y; angle_s = atan2(yc1 - yc3, xc1 - xc3); angle_e = atan2(p2.y - yc3, p2.x - xc3); 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; if (gt(radius, ZERO)) incr = 2.0 * asin(sample_rate / radius); else incr = M_2PI; min = (angle_e - angle_s) / 2.99; incr = VroniMin(incr, min); angle_e -= incr; alpha = angle_s + incr; while (alpha < angle_e) { xc1 = xc3 + radius * cos(alpha); yc1 = yc3 + radius * sin(alpha); #ifdef EXT_APPL_PNTS i4 = StorePnt(xc1, yc1, eap_NIL); #else i4 = StorePnt(xc1, yc1); #endif UpdateBoundingBox(xc1, yc1); #ifdef GRAPHICS if (graphics) AddPntToBuffer(i4, ArcColor); #endif alpha += incr; } alpha = alpha + (angle_e - alpha) / 2.0; xc1 = xc3 + radius * cos(alpha); yc1 = yc3 + radius * sin(alpha); #ifdef EXT_APPL_PNTS i4 = StorePnt(xc1, yc1, eap_NIL); #else i4 = StorePnt(xc1, yc1); #endif UpdateBoundingBox(xc1, yc1); #ifdef GRAPHICS if (graphics) AddPntToBuffer(i4, ArcColor); #endif } /* */ /* no line segments and circular arcs left! reset the counters. */ /* */ num_arcs = 0; num_segs = 0; return; }