/*****************************************************************************/ /* */ /* Copyright (C) 1999-2023 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-172 */ /* Voice Mail: (+43 662) 8044-6304 */ /* Snail Mail: Martin Held */ /* FB Informatik */ /* Universitaet Salzburg */ /* A-5020 Salzburg, Austria */ /* */ /*****************************************************************************/ #ifndef VRONI_OBJECT_H #define VRONI_OBJECT_H #include #include #include #include #include #ifndef NO_CPUTIME #ifdef CPUTIME_BY_CHRONO #include #endif #endif #ifdef CPUTIME_VIA_CLOCK #include #endif #ifdef OGL_GRAPHICS #ifdef __APPLE__ #include #else #include /* glut.h includes gl.h and glu.h */ #endif #endif // da heap.cc #define HEAP_BLOCK_SIZE 32768 #include "coord.h" #include "vddata.h" #include "vronivector.h" #include "ext_appl_inout.h" #include "defs.h" #include "offset.h" #include "util.h" /* */ /* class predeclarations to avoid having more inclusions */ /* */ /* */ /* types: classes, enums, typedefs */ /* */ /* from data_off.cc */ #define STACK_INCR 32768 #define STACK_TYPE int #define STACK_STRING "data_off:stack" /* from vd_basic.cc */ #define VRONI_MAXSOL 80 /* from header.h */ typedef enum {vroniCHARS, vroniINTEGER, vroniDOUBLE, vroniBOOLEAN, vroniCOORD, vroniN_STATUS, vroniT_SITE, vroniPNTS} my_types; /* from intersections.cc - type definitions for grid for geometric hashing */ struct grid_cell; typedef struct point_entry { int num; std::set cells; } point_entry; struct comp_seg_iscoord { comp_seg_iscoord(double val) { eps = val; } bool operator()(const coord& a, const coord& b) const { return (lt(a.x - b.x, eps) || (eq(a.x - b.x, eps) && (a.y < b.y))); } double eps; private: comp_seg_iscoord(); }; typedef struct seg_entry { seg_entry(double val) { intersections.reset( new std::set(comp_seg_iscoord(val)) ); } int num; std::unique_ptr> intersections; private: seg_entry(); } seg_entry; #ifdef GENUINE_ARCS typedef struct arc_intersection { coord c; double alpha; } arc_intersection; struct comp_arc_iscoord { bool operator()(const arc_intersection& a, const arc_intersection& b) const { return a.alpha < b.alpha; } }; typedef struct arc_entry { int num; std::set intersections; } arc_entry; #endif typedef struct grid_cell { int i, j; double x_min, x_max; double y_min, y_max; std::set points; std::set segs; #ifdef GENUINE_ARCS std::set arcs; #endif } grid_cell; typedef struct grid { grid_cell** cells; int n_x, n_y; double d_x, d_y; double *x_min, *y_min, *x_max, *y_max; std::map points; std::map segs; #ifdef GENUINE_ARCS std::map arcs; #endif } grid; /* */ /* global variables */ /* */ /* */ /* VRONI object base class declaration */ /* */ class vroniObject { public: // // CONSTRUCTOR / DESTRUCTOR // vroniObject(); virtual ~vroniObject(); // // API FUNCTIONS // void apiHandleError(void); /* VRONI exception handling */ void apiInitializeProgram(void); /* call this routine once prior */ /* calling any other routine of */ /* VRONI */ void apiResetAll(void); /* call this routine whenever */ /* new data is to be input and */ /* VRONI's data structures are */ /* to be reset; note that this */ /* function won't free memory */ /* allocated */ void apiTerminateProgram(void); /* call this routine to release */ /* all memory allocated by VRONI*/ void apiHandleInput(char input_file[], /* name of the input file */ vr_bool *new_input, /* true if new data has been */ /* read */ vr_bool read_polygon, /* read ".dat" format */ vr_bool read_poly, /* read ".poly" format */ vr_bool read_sites, /* read ".site" format */ vr_bool read_xdr, /* read ".xdr" format */ vr_bool read_e00, /* read ".e00" format */ vr_bool read_polylines,/* read ".polylines" format */ vr_bool read_usgs, /* read ".usgs" format */ vr_bool read_dxf, /* read ".dxf" format */ vr_bool read_pnts, /* read ".pnt" format */ vr_bool read_graphml);/* read ".graphml" format */ void apiFileInput(char input_file[], /* name of the input file */ vr_bool *new_input); /* true if new data has been */ /* read */ /* this function requires the */ /* user to stick to my naming */ /* convention for the extension */ /* of the input file relative */ /* to the data format used */ void apiArrayInput(int number_of_points, /* data in point_data[0,..,k] */ /* for k := number_of_points-1 */ in_pnts *point_data, /* see ext_appl_inout.h */ int number_of_segments, in_segs *segment_data, /* see ext_appl_inout.h */ int number_of_arcs, in_arcs *arc_data, /* see ext_appl_inout.h */ vr_bool *new_input); void apiComputeVD(vr_bool save_data, /* save input data to file? */ vr_bool new_data, /* first call for this data? */ vr_bool time, /* do you want to time the */ /* computation? */ int bound, /* scale factor for bounding */ /* box; default value: 3 */ int sample, /* sampling factor for sampling */ /* segs/arcs; default: 0; */ /* see SampleData() in */ /* approx.cc */ int approx, /* approximation factor for */ /* circular arcs; default: 0; */ /* see ApproxArcsHeuristic() in */ /* approx.cc. obsolet by now! */ char output_file[], /* name of the output file; */ /* irrelevant if save_data is */ /* false */ vr_bool discard_duplicate_sites, /* shall the code check prior */ /* to the computation whether */ /* duplicate segs/arcs have */ /* been input? default: false. */ vr_bool pnts_only, /* compute VD/DT of points only */ vr_bool write_vd_dt, /* output point VD/DT */ char vd_dt_file[], /* output file for point VD/DT */ vr_bool clean_up); /* shall we clean up the data */ /* prior to the VD computation? */ void apiComputeOff(vr_bool time, /* do you want to time the */ /* computation? */ char off_file[], /* name of the file that will */ /* contain the offsets computed */ vr_bool write_off, /* shall we output the offsets */ /* to off_file[]? */ vr_bool dxf_format, /* if offsets are to be output: */ /* shall we use DXF format? */ double t_offset, /* compute offset curve(s) for */ /* offset distance t_offset */ double d_offset, /* incremental step-over */ /* distance for further offset */ /* curves */ vr_bool auto_offset, /* shall we use my heuristic */ /* for finding offset distances */ /* that create a family of */ /* offsets? */ vr_bool left_offset, /* true if offsets are to be */ /* computed only on the left */ /* side of input segments */ vr_bool right_offset); /* true if offsets are to be */ /* computed only on the right */ /* side of input segments */ #ifdef MAT void apiComputeWMAT(vr_bool auto_wmat, /* shall we use my heuristic */ /* for finding nice WMAT */ /* thresholds? */ double wmat_angle, /* angle threshold for WMAT */ /* computation;in radians, out */ /* of the interval [0, pi] */ double wmat_dist, /* distance threshold for WMAT */ /* computation */ vr_bool time, /* do you want to time the */ /* computation? */ vr_bool left_wmat, /* true if WMAT is to be */ /* computed only on the left */ /* side of input segments */ vr_bool right_wmat); /* true if WMAT is to be */ /* computed only on the right */ /* side of input segments */ #endif #ifdef WRITE_VD void apiOutput_VD(char vd_file[], /* name of the file that will */ /* contain the VD polygons */ double vd_apx_dist, /* sampling distance used for */ /* approximating conic VD edges */ vr_bool left_vd, /* true if VD is to be */ /* output only on the left */ /* side of input segments */ vr_bool right_vd); /* true if VD is to be */ /* output on the right */ /* side of input segments */ #endif void apiComputeOutputMIC(vr_bool time, /* do you want to time the */ /* computation? */ vr_bool lft_mic, /* true if MIC is to be */ /* computed only on the left */ /* side of input segments */ vr_bool rgt_mic, /* true if MIC is to be */ /* computed only on the right */ /* side of input segments */ coord *center, /* x,y-coordinates of a MIC */ /* center */ double *radius); /* radius of a MIC circle */ void apiResetOffsetData(void); /* discard all offsets computed */ /* so far */ const char* apiGetProgName(); const char* apiGetProgVersion(); const char* apiGetProgYear(); /* */ /* API function apiOutputOffsets() allows a user to traverse my offset */ /* data structure and extract the offset data and "write" it to an entity */ /* "output". See WriteOffsets() in offsets.cc for a sample use. Needless */ /* to say, it is the user's responsibility to provide apiOutputOffsets() */ /* with the adequate function arguments. */ /* */ void apiOutputOffsets(void *output, /* this is a pointer to a */ /* user-defined object, such as */ /* a file or a structure; */ void (vroniObject::*StartOffsetsFuncPtr)( void *output, int num_offset_loops), void (vroniObject::*StartOffsetLoopFuncPtr)( void *output, int num_offset_elements), void (vroniObject::*WriteOffSetSegFuncPtr)( void *output, #ifdef EXT_APPL_OFF eao_type ext_appl_off, #endif double_arg x1, double_arg y1, double_arg x2, double_arg y2), void (vroniObject::*WriteOffsetArcFuncPtr)( void *output, #ifdef EXT_APPL_OFF eao_type ext_appl_off, #endif double_arg x1, double_arg y1, double_arg x2, double_arg y2, double_arg xc, double_arg yc, vr_bool ccw), void (vroniObject::*EndOffsetLoopFuncPtr)( void *output, int num_offset_segs, int num_offset_arcs, double x0, double y0), void (vroniObject::*EndOffsetsFuncPtr)( void *output, int num_offset_loops, int num_offset_segs, int num_offset_arcs)); // // INPUT GEOMETRY // /* data.cc: */ int GetNumberOfPoints(void); int GetNumberOfSegments(void); int GetNumberOfArcs(void); #ifdef EXT_APPL_SITES void AddSeg(int *i1, double_arg xc2, double_arg yc2, eas_type ext_appl); void AddArc(int *i1, double_arg xc3, double_arg yc3, double_arg xc2, double_arg yc2, int last_attr, eas_type ext_appl); #else void AddSeg(int *i1, double_arg xc2, double_arg yc2); void AddArc(int *i1, double_arg xc3, double_arg yc3, double_arg xc2, double_arg yc2, int last_attr); #endif #ifdef EXT_APPL_SITES void CloseSeg(int i1, int i2, eas_type ext_appl); void CloseArc(int i1, int i2, double_arg xc2, double_arg yc2, int last_attr, eas_type ext_appl); #else void CloseSeg(int i1, int i2); void CloseArc(int i1, int i2, double_arg xc2, double_arg yc2, int last_attr); #endif #ifdef EXT_APPL_PNTS int HandlePnt(double_arg xc1, double_arg yc1, eap_type ext_appl); eap_type GetExtApplPnt(int i); void SetExtApplPnt(int i, eap_type x); #else int HandlePnt(double_arg xc1, double_arg yc1); #endif #ifdef EXT_APPL_SITES void HandleSeg(double_arg xc1, double_arg yc1, double_arg xc2, double_arg yc2, eas_type ext_appl); void HandleArc(double_arg xc1, double_arg yc1, double_arg xc2, double_arg yc2, double_arg xc3, double_arg yc3, int attr, eas_type ext_appl); eas_type GetExtApplSeg(int s); void SetExtApplSeg(int s, eas_type t); eas_type GetExtApplArc(int s); void SetExtApplArc(int s, eas_type t); #else void HandleSeg(double_arg xc1, double_arg yc1, double_arg xc2, double_arg yc2); void HandleArc(double_arg xc1, double_arg yc1, double_arg xc2, double_arg yc2, double_arg xc3, double_arg yc3, int attr); #endif // // ACCESS VD NODES AND EDGES // /* vd_basic.cc: */ vr_bool GetVDStatus(void); int GetNumberOfNodes(void); int GetNumberOfEdges(void); void InitStorageNodes(int number); void InitStorageEdges(int number); inline void IncrementVDIdentifier() { ++VD_identifier; } void PrintVDCounters(void); double ClassifySolSite(int i, t_site i_type, coord c, double r); /* vddata.cc: */ #ifdef EXT_APPL_VD ean_type GetExtApplNode(int i); void SetExtApplNode(int i, ean_type ext_appl); eae_type GetExtApplEdge(int i); void SetExtApplEdge(int i, eae_type ext_appl); #endif /** Get first vertex of given site of given type */ int Get1stVtx(int site, int type); /** Get second vertex of given site of given type */ int Get2ndVtx(int site, int type); /** Get first vertex of given segment */ int Get1stVtxSeg(int site); /** Get second vertex of given segment */ int Get2ndVtxSeg(int site); /** Get first vertex of given arc */ int Get1stVtxArc(int site); /** Get second vertex of given arc */ int Get2ndVtxArc(int site); /** Set first vertex of site of given type to pnt */ void Set1stVtx(int site, int type, int pnt); /** Set second vertex of site of given type to pnt */ void Set2ndVtx(int site, int type, int pnt); /** Set first vertex of given segment */ void Set1stVtxSeg(int site, int pnt); /** Set second vertex of given segment */ void Set2ndVtxSeg(int site, int pnt); /** Set first vertex of given arc */ void Set1stVtxArc(int site, int pnt); /** Set second vertex of given arc */ void Set2ndVtxArc(int site, int pnt); /** Check whether point has been visited */ vr_bool IsPntVisited(int site); /** Set whether point has been visited */ void SetPntVisited(int site, vr_bool vis); /** Check if pnt is start point of seg */ vr_bool IsSegStartPnt(int seg, int pnt); /** Check if pnt is send point of seg */ vr_bool IsSegEndPnt(int seg, int pnt); /** Get coordinates of input point */ coord GetPntCoords(int pnt); /** Set x-coordinate of point */ void SetXCoord(int pnt, double_arg x); /** Set y-coordinate of point */ void SetYCoord(int pnt, double_arg y); /** Get start point coordinates of seg */ coord GetSegStartCoord(int seg); /** Get end point coordinates of seg */ coord GetSegEndCoord(int seg); /** Get start point coordinates of arc */ coord GetArcStartCoord(int arc); /** Get end point coordinates of arc */ coord GetArcEndCoord(int arc); /** Get center point of arc a */ coord GetArcCenter(int a); /** Get radius of arc a */ double GetArcRadius(int a); /** Check whether p is start point of a */ vr_bool IsArcStartPnt(int a, int p); /** Check whether p is end point of a */ vr_bool IsArcEndPnt(int a, int p); /** Get original orientation of arc a * Attention: within VRONI all arcs are oriented CCW! */ vr_bool GetArcOrientation(int a); /** Set radius of arc a */ void SetArcRadius(int a, double_arg r); /** Set center of arc a */ void SetArcCenter(int a, coord p); /** Set orientation of arc a */ void SetArcOrientation(int a, vr_bool ccw); /** Set normal vector of start point of arc a */ void SetArcStartNormal(int a, coord ns); /** Set normal vector of end point of arc a */ void SetArcEndNormal(int a, coord ne); /** Get normal vector of start point of arc a */ coord GetArcStartNormal(int a); /** Get normal vector of end point of arc a */ coord GetArcEndNormal(int a); /** Set chord equation coefficients of arc s to a, b, d */ void SetChordEqnData(int s, double_arg a, double_arg b, double_arg d); /** Get chord equation coefficients of arc s */ void GetChordEqnData(int s, double* a, double* b, double* d); /** Set equation data of segment s */ void SetSegEqnData(int s, double_arg a, double_arg b, double_arg c); /** Get equation data of segment s */ void GetSegEqnData(int s, double* a, double* b, double* c); /** Get normal vector of seg s */ coord GetSegNormal(int s); /** Get unit vector from start point to end point of seg s */ coord GetSegDirection(int s); /** Get length of segment s*/ double GetSegLgth(int s); /** Set length of segment s */ void SetSegLgth(int s, double_arg l); /** Check whether point p has incident site */ vr_bool HasIncidentSite(int p); /** set incident site of point p */ void SetIncidentSite(int p, int status); /** Check whether point p is to be deleted */ vr_bool IsDeletedPnt(int p); /** Set whether point p is to be deleted */ void SetDeletedPnt(int p, vr_bool del); /** Get node of point p */ int GetPntNode(int p); /** Set node of point p */ void SetPntNode(int p, int n); /** Set vd-pointer of point p */ void SetPntVDPtr(int p, int e); /** Get vd-pointer of point p */ int GetPntVDPtr(int p); /** Reset vd-pointer of point p */ void ResetPntVDPtr(int p); /** Reset vd-pointer of segment s */ void ResetSegVDPtr(int s); /** Set vd-pointer of site s of type t to e */ void SetVDPtr(int s, int t, int e); /** Get vd-pointer of site s of type t */ int GetVDPtr(int s, int t); /** Set start node of edge e to n */ void SetStartNode(int e, int n); /** Set end node of edge e to n */ void SetEndNode(int e, int n); /** Get start node of edge e */ int GetStartNode(int e); /** Get end node of edge e */ int GetEndNode(int e); /** Is n the start node of edge e? */ vr_bool IsStartNode(int e, int n); /** Is n the end node of edge e? */ vr_bool IsEndNode(int e, int n); /** Is edge e incident to node n? */ vr_bool IsEdgeIncident(int e, int n); /** Get the opposite node to n at edge e */ int GetOtherNode(int e, int n); /** Get site and type left to edge e */ void GetLftSiteData(int e, int* s, t_site* t); /** Get site and type right to edge e */ void GetRgtSiteData(int e, int* s, t_site* t); /** Get type of site left to edge e */ t_site GetLftSiteType(int e); /** Get type of site right to edge e */ t_site GetRgtSiteType(int e); /** Get site left to edge e */ int GetLftSite(int e); /** Get site right to edge e */ int GetRgtSite(int e); /** Given an edge e and a defining site s1 of type t1. * Retrieve opposite site s2 and its type t2. */ void GetOtherSiteData(int e, int s1, t_site t1, int* s2, t_site* t2); /** Is node n a degree-2 node? */ vr_bool IsDeg2Node(int n); /** Set is-degree-2 flag of node n */ void SetNodeDegree(int n, vr_bool f); /** If site s of type t the left site of edge e? */ vr_bool IsLftSite(int e, int s, t_site t); /** If site s of type t the right site of edge e? */ vr_bool IsRgtSite(int e, int s, t_site t); /** Is site s of type t a left or right site of edge e? */ vr_bool IsLftRgtSite(int e, int s, t_site t); /** Is left site of edge e the point s? * Attention: We do not check for site type! */ vr_bool IsLftPnt(int e, int s); /** Is right site of edge e the point s? * Attention: We do not check for site type! */ vr_bool IsRgtPnt(int e, int s); /** Get CCW edge of edge e at node n */ int GetCCWEdge(int e, int n); /** Get CW edge of edge e at node n */ int GetCWEdge(int e, int n); /** Set CCW edge of edge e at node n to e1 */ void SetCCWEdge(int e, int n, int e1); /** Set CW edge of edge e at node n to e1 */ void SetCWEdge(int e, int n, int e1); /** Reset CW edge of edge e at node n to e1 */ void ResetCWEdge(int e, int n); /** Reset CCW edge of edge e at node n to e1 */ void ResetCCWEdge(int e, int n); /** Get status of node n */ n_status GetNodeStatus(int n); /** Set status of node n to s */ void SetNodeStatus(int n, n_status s); /** Mark node n as deleted */ void MarkNodeDeleted(int n); /** Mark node n as visited */ void MarkNodeVisited(int n); /** Mark node n as unchecked */ void MarkNodeUnchecked(int n); /** Mark node n as checked */ void MarkNodeChecked(int n); /** Mark node n as dummy */ void MarkNodeDummy(int n); /** Is node n marked as deleted? */ vr_bool IsNodeDeleted(int n); /** Is node n marked as visited? */ vr_bool IsNodeVisited(int n); /** Is node n marked as checked? */ vr_bool IsNodeChecked(int n); /** Is node n marked as unchecked? */ vr_bool IsNodeUnchecked(int n); /** Is node n marked as dummy? */ vr_bool IsNodeDummy(int n); /** Mark edge e as deleted */ void MarkEdgeDeleted(int e); /** Is edge e marked as deleted? */ vr_bool IsEdgeDeleted(int e); /** Is this edge not marked as deleted and has non-NIL left and right sites? */ vr_bool IsEdgeActive(int e); /** Is this edge e a genuine edge? That is, edge e is active (IsEdgeActive) and * if left or right sites are points, then the indices of the points are * greater (resp. less) than minidx (resp. maxidx) */ vr_bool IsEdgeGenuine(int e, int minidx, int maxidx); /** Get coordinates of node n */ coord GetNodeCoord(int n); /** Get parameter (clearance [squared]) of node n */ double GetNodeParam(int n); /** Get coordinate and parameter of node n */ void GetNodeData(int n, coord* p, double* r); /** Get parameter of start and end node of edge e */ void GetEdgeParam(int e, double* rs, double *re); /** Get an edge incident to node n */ int GetIncidentEdge(int n); /** Set the edge-pointer of node n to e */ void SetIncidentEdge(int n, int e); /** Get a site where node n belongs to */ int GetNodeSite(int n); /** Set site-pointer of node n to s */ void SetNodeSite(int n, int s); /** Update node n of edge e to node n0 */ void UpdateNodeEdgeData(int e, int n, int n0); /** Consider edges and nodes e1-n1-e0-n2-e2 in CW order. Set cw and ccw * pointers of e0 to e1, e2, GetCWEdge(e1,n1), GetCCWEdge(e2,n2) and vice * versa. */ void CloseVoronoiCell(int e1, int e0, int e2, int n1, int n2); /** Copy segment s1 to segment s */ void CopySegData(int s, int s1); /** Copy arc s1 to arc s */ void CopyArcData(int s, int s1); #ifdef WRITE_VD void SetVDEdge(int s, int t, int e); int GetVDEdge(int s, int t); void SetPntIndex(int i, int n); int GetPntIndex(int i); void SetNodeIndex(int i, int n); int GetNodeIndex(int i); #endif #ifdef ORDERED /** Set key of site s of type t to n */ void SetSiteNumber(int s, t_site t, int n); /** Get key of site s of type n */ int GetSiteNumber(int s, t_site t); #endif /* from basic.h */ inline double ScaleX(double xc) { return (scale_factor * (xc - shift.x)); } inline double ScaleY(double yc) { return (scale_factor * (yc - shift.y)); } inline double ScaleV(double value) { return (value * scale_factor); } inline double UnscaleX(double xc) { assert(scale_factor > 0.0); return (xc / scale_factor + shift.x); } inline double UnscaleY(double yc) { assert(scale_factor > 0.0); return (yc / scale_factor + shift.y); } inline double UnscaleV(double value) { assert(scale_factor > 0.0); return (value / scale_factor); } void SetRootTooLarge(double_arg t); #ifdef VRONI_INFO void InitRelaxationMemory(double_arg t); void UpdateRelaxationMemory(double_arg t); void ConfirmRelaxationMemory(); double ReportRelaxationMemory(); #endif // // BISECTOR COORDINATE EVALUATION // /* offset.cc */ void EvaluateBisectorData(int i, double_arg t, coord *w); protected: // // PROTECTED VARIABLES (i.e. accessible by derived classes) // /* io_debug.cc: */ #ifdef TRACE coord clip_min; coord clip_max; #endif /* driver.cc */ vr_bool save_data; vr_bool read_poly; vr_bool read_polygon; vr_bool read_sites; vr_bool read_xdr; vr_bool read_graphml; vr_bool read_polylines; vr_bool read_e00; vr_bool read_usgs; vr_bool read_dxf; vr_bool read_pnts; vr_bool read_file; vr_bool write_ipe; vr_bool write_vd_dt; vr_bool help; vr_bool time_it; vr_bool print_copy; vr_bool discard_dupl_s; vr_bool write_off; vr_bool auto_offset; vr_bool left_offset; vr_bool right_offset; vr_bool compute_wmat; vr_bool auto_wmat; vr_bool pnts_only; vr_bool compute_mic; vr_bool dxf_format; vr_bool write_ma; vr_bool clean_up; vr_bool new_input; vr_bool write_vd; vr_bool left_vd; vr_bool right_vd; vr_bool vr_incr; FILE *vr_file_handle; int driver_step_size; int p_step_size; int o_step_size; int a_step_size; int sample; int bound; int approx; int io_flag; int inputprec; int mpfr_prec; int vr_seed; double t_offset; double d_offset; double wmat_angle; double wmat_dist; double vd_apx_dist; char vd_file[256]; char input_file[256]; char output_file[256]; char off_file[256]; char vd_dt_file[256]; char ma_file[256]; char vr_file[256]; #if defined (OGL_GRAPHICS) vr_bool off_init; vr_bool data_read; vr_bool finished; vr_bool off_finished; vr_bool computed; vr_bool wmat_computed; vr_bool mic_computed; vr_bool vd_output; vr_bool first_input; int first_pnt; int last_pnt; int new_pnts; #ifdef TRACE double xc2, yc2; #endif #ifdef API_PARABOLIC int count_pnts; coord p1, p2; double t1, t2; #endif #endif /* redraw.cc */ #ifdef GRAPHICS typedef struct { int index; /* index of a pnt, seg, arc or node of the VD */ int color; /* color information; see defs.h */ } buffer; /* generic buffer type for drawing objects. */ /* the index is the array index of the object */ /* referenced; see data.cc (for pnt, seg, arc) */ /* and vd.cc (for vdn). */ buffer *pnt_buf; buffer *seg_buf; buffer *arc_buf; buffer *vdn_buf; int num_pnt_buf, max_num_pnt_buf; int num_seg_buf, max_num_seg_buf; int num_arc_buf, max_num_arc_buf; int num_vdn_buf, max_num_vdn_buf; struct vde_buffer { coord p1; /* (x,y) coords of start point of a line seg */ coord p2; /* (x,y) coords of end point of a line seg */ int color; /* color information; see defs.h */ //Ensure construction doesn't implicitly initialize elements - done explicitly later anyway inline vde_buffer() {} }; /* buffer for drawing edges of the VD */ vronivector vde_buf; int num_vde_buf, max_num_vde_buf; struct off_buffer { coord p1; /* (x,y) coords of start point */ coord p2; /* (x,y) coords of end point */ coord p3; /* (x,y) coords of center (for an arc) */ double r; /* radius (for an arc) */ vr_bool ccw; /* orientation (for an arc) */ int color; /* color information; see defs.h */ //Ensure construction doesn't implicitly initialize elements - done explicitly later anyway inline off_buffer() {} }; /* buffer for drawing offset arcs and segs */ vronivector off_buf; int num_off_buf, max_num_off_buf; typedef struct { int index; /* index of an object (pnt, seg, ... ) */ t_site type; /* type of the object; see defs.h */ int color; /* color information; see defs.h */ } cur_buffer; /* buffer for drawing "current" objects; used */ /* if the code is in "step mode" */ cur_buffer *cur_buf = (cur_buffer*)NULL; int num_cur_buf, max_num_cur_buf; struct cir_buffer { coord cntr; /* center of a circle */ double radius; /* radius of a circle */ //Ensure construction doesn't implicitly initialize elements - done explicitly later anyway inline cir_buffer() {} }; vronivector cir_buf; int num_cir_buf, max_num_cir_buf; #endif /* api_functions.cc */ #ifdef GRAPHICS vr_bool graphics; vr_bool draw_pnts; vr_bool draw_segs; vr_bool draw_off; vr_bool draw_arcs; vr_bool draw_vde; vr_bool draw_vdn; vr_bool draw_dte; vr_bool draw_mat; vr_bool draw_mic; #endif /* data_off.cc */ STACK_TYPE *stack; STACK_TYPE num_stack; STACK_TYPE max_num_stack; vronivector edge_data; int num_edge_data; int max_num_edge_data; e_flag *edge_flags; int num_edge_flags; int max_num_edge_flags; int *active_edges; int num_active_edges; int max_num_active_edges; int min_pnt_ind; int max_pnt_ind; vr_bool e_data_init; int data_off_VD_ID; /* mic.cc */ vr_bool MIC_computed; /* offset.cc */ vronivector offset_list; int num_offset_list; int max_num_offset_list; vronivector offset_data; int num_offset_data; int max_num_offset_data; int cur_offset_list; double max_t_offset; #ifdef VISUAL_TEST_OFFSETS vr_bool small_increment; #endif vr_bool unscaleXYZ; double t; double d_off; vr_bool data_written; int offset_VD_ID; /* wmat.cc */ vr_bool WMAT_computed; // // PROTECTED FUNCTIONS (i.e. accessible by derived classes) // void VD_Dbg_Warning(const char* VD_Warning_String) { #ifdef VRONI_DBG_WARN fflush(stdout); fprintf(stdout, "\nwarning in %s\n", VD_Warning_String); fflush(stdout); #endif ExtApplFuncVD_Dbg_Warning; } void VD_IO_Warning(const char* VD_Warning_String) { io_troubles = true; #ifdef VRONI_IO_WARN if (verbose) { fflush(stdout); fprintf(stdout, "\nI/O warning in %s\n", VD_Warning_String); fflush(stdout); } #endif ExtApplFuncVD_IO_Warning; } void VD_Warning(const char* VD_Warning_String) { #ifdef VRONI_WARN if (!quiet) { fflush(stdout); fprintf(stdout, "\nwarning in %s\n", VD_Warning_String); fflush(stdout); } #endif ExtApplFuncVD_Warning; } void VD_Info(const char* VD_Info_String) { #ifdef VRONI_INFO if (verbose && !quiet) { fflush(stdout); fprintf(stdout, "%s", VD_Info_String); fflush(stdout); } #endif ExtApplFuncVD_Info; } /* compute.cc: */ void ComputeVD(vr_bool save_data, vr_bool new_input, int step_size, vr_bool time, int bound, int sample, int approx, char output_file[], vr_bool discard_duplicate_sites, int p_step_size, vr_bool *finished, int a_step_size, vr_bool pnts_only, vr_bool write_vd, char vd_dt_file[], vr_bool left_vd, vr_bool right_vd, vr_bool clean_up); /* memory.cc: */ void *ReallocateArray(void *old_ptr, int number, size_t size, char const *var_name); void FreeMemory(void **ptr, char const *var_name); #ifdef DEBUG_MEMORY vr_bool IndexOutOfBounds(void *array_ptr, char const *var_name, size_t size, int index); #endif unsigned long ReportMaxNumberBytes(void); unsigned long ReportCurrNumberBytes(void); vr_bool AllMemoryFreed(); /* data.cc: */ void ExtendPnts(int number); vr_bool GetSupportVtxFlag(void); void SetSupportVtxFlag(vr_bool flag); void CheckIsolatedPnts(void); void PrintSiteData(int s, t_site t, const char *string); void FindClosestSeg(double_arg xl, double_arg yl); void FindClosestPnt(double_arg xl, double_arg yl); void InitSiteOrder(t_site type); int GetNextSite(void); void RemoveSegment(int i); void RemoveArc(int i); void SplitSegmentIntoHalves(int i1); int SplitSeg(int i1, int i2); int SplitArc(int i1, int i2); void MergePoints(int i1, int i2); void ResetFlags(void); void MarkDrawSite(int i, t_site type); void ResetDrawSite(int i, t_site type); void ResetInputData(void); void FreeInputData(); #ifdef EXT_APPL_PNTS void InitPntSite(pnt *pointer, double_arg x, double_arg y, eap_type ext_appl); #else void InitPntSite(pnt *pointer, double_arg x, double_arg y); #endif #ifdef EXT_APPL_PNTS int StorePnt(double_arg x, double_arg y, eap_type ext_appl); #else int StorePnt(double_arg x, double_arg y); #endif #ifdef EXT_APPL_SITES int StoreSeg(int i1, int i2, eas_type ext_appl); int StoreArc(int i1, int i2, double_arg xc, double_arg yc, vr_bool ccw, eas_type ext_appl); #else int StoreSeg(int i1, int i2); int StoreArc(int i1, int i2, double_arg xc, double_arg yc, vr_bool ccw); #endif void InitPnts(int number); void InitSegs(int number); void InitArcs(int number); void SetBoundingBox(void); void CheckBoundingBox(void); void AddDummyCorners(int bound); vr_bool InPntsList(int index); vr_bool InSegsList(int index); vr_bool InArcsList(int index); void InitStoragePnts(int number); void InitStorageSegs(int number); void InitStorageArcs(int number); void ScaleData(void); void ResizePnts(int number); void DXFStartPoly(); void DXFClosePoly(double bulge); void DXFAddPolyVertex(double_arg xc1, double_arg yc1, double bulge); /* redraw.cc: */ #ifdef GRAPHICS void AddNodeToBuffer(int index, int color); void AddPntToBuffer(int index, int color); void AddSegToBuffer(int index, int color); void AddArcToBuffer(int index, int color1); void AddToCurBuffer(int index, t_site type, int color); void FreeDrawingBuffer(void); void ResetBufferData(void); void ResetOffsetBuffer(void); void ResetCurBuffer(void); void ResetVDBuffer(void); void UpdateBuffer(void); void AddEdgeToBuffer(double_arg x1, double_arg y1, double_arg x2, double_arg y2, int color); void AddCirToBuffer(coord cntr, double_arg radius); void WriteIpeOutput(char *filename); void AddOffToBuffer(double_arg x1, double_arg y1, double_arg x2, double_arg y2, double_arg x3, double_arg y3, double_arg r, vr_bool ccw, int color); #ifdef OGL_GRAPHICS void BuffToDrawArc(int j, int color); void BuffToDrawSeg(int j, int color); void Redraw(void); #endif // OGL_GRAPHICS #endif /* graphics_ogl.cc */ #ifdef GRAPHICS #ifdef OGL_GRAPHICS void ResetGraphicsData(void); void UpdateScaleData(void); void DrawSeg(coord pnt1, coord pnt2, int color); void DrawPnt(coord pnt, int color, vr_bool large_radius); void DrawArc(coord pnt1, coord pnt2, coord pnt3, double radius, int color); void DrawText(coord pos, int color, const char* fmt, ...); void DrawCircle(coord pnt3, double radius, int color); void ResetRubberLine(void); void FlushDisplay(void); #endif // OGL_GRAPHICS #endif /* driver.cc: */ void HandleWriteVDOutput(void); void ParseCommandLineArgs(int argc, char *argv[], vr_bool *graphics, vr_bool *color_graphics, vr_bool *full_screen); void GetInputData(vr_bool *input_received); void ProceedWithoutGraphics(vr_bool input_received); void HandleComputeVD(void); void ClosePolygon(void); void StartNewPolygon(void); void AddPolygonVertex(double_arg xc1, double_arg yc1); void ResetOnlineGraphicsData(void); void ResetDriverData(void); /* io_basic.cc: */ void ReadBDM(char input_file[], vr_bool *new_input); void ReadPolylines(char input_file[], vr_bool *new_input); void ReadSites(char input_file[], vr_bool *new_input); void ReadContour(FILE *input); void ReadPolygon(char input_file[], vr_bool *new_input); void ReadPoly(char input_file[], vr_bool *new_input); void ReadPoints(char input_file[], vr_bool *new_input); FILE *OpenFileVD(const char *file_name, const char *access); /* io_debug.cc: */ void WriteSites(const char *output_file); #ifdef TRACE void WriteSiteData(int j, t_site type, const char* qual_string); void WriteProcessedSites(const char *output_file); void ClipWriteSiteData(int j, t_site type, const char *output_file); void ExportClipWindow(double_arg x1, double_arg y1, double_arg x2, double_arg y2); void WriteDisplayedSites(double_arg xmin, double_arg ymin, double_arg xmax, double_arg ymax, const char *output_file); #endif /* io_dxf.cc: */ void ReadDXFFile(char input_file[], vr_bool *new_input); void WriteDXFLWPoly_Vertex(FILE *dxf_file, double_arg xc1, double_arg yc1, double_arg bulge); void WriteDXFLWPoly_Start(FILE *dxf_file, vr_bool closed, int color); void WriteDXFPoly_Vertex(FILE *dxf_file, double_arg xc1, double_arg yc1, double_arg bulge); void WriteDXFPoly_Start(FILE *dxf_file, vr_bool closed, int color); void WriteDXFArc(FILE *dxf_file, double_arg xc1, double_arg yc1, double_arg xc2, double_arg yc2, double_arg xc3, double_arg yc3, vr_bool ccw_flag, int color); void WriteDXFCircle(FILE *dxf_file, double_arg xc1, double_arg yc1, double_arg radius, int color); void WriteDXFPoint(FILE *dxf_file, double_arg xc1, double_arg yc1, int color); void WriteDXFLine(FILE *dxf_file, double_arg xc1, double_arg yc1, double_arg xc2, double_arg yc2, int color); void WriteDXFEntity(FILE *dxf_file, int color); void StartDXFFile(FILE *dxf_file); void FinishDXFFile(FILE *dxf_file); void WriteDXFPoly_End(FILE *dxf_file); /* io_help.cc: */ void Copyright(void); void Help(void); void PrintVarValue(FILE *output, void *v, char const *var_name, my_types t); /* io_misc.cc: */ void SkipText(FILE *in_file, char ch); char ParseText(FILE *in_file, char ch1, char ch2); vr_bool FindText(FILE *in_file, char ch); void HandleBlock(FILE *in_file); void ReadXDRFile(char input_file[], vr_bool *new_input); vr_bool ReadGraphMLNode(FILE *input); vr_bool ReadGraphMLEdge(FILE *input); void ReadGraphML(char input_file[], vr_bool *new_input); void ReadE00File(char input_file[], vr_bool *new_input); void ReadUSGS(char input_file[], vr_bool *new_input); void AddXMLseg(int *i1, double_arg xt, double_arg yt, double_arg xc, double_arg yc, double_arg r, char type, int i0); vr_bool ReadIpePath(FILE *input); vr_bool ReadIpeMark(FILE *input); void ReadXML(char input_file[], vr_bool *new_input); /* io_other.cc: */ void WriteCgalSites(char output_file[]); /* io_vddt.cc: */ void WriteVoronoiRegion(int i, FILE *output); void WriteVDDT(char output_file[]); /* io_parse.cc: */ vr_bool ReadOptionalNumber(FILE *input, int *data); vr_bool ReadOptionalCoord(FILE *input, double *xy); vr_bool ReadNumber(FILE *input, int *data); #ifdef EXT_APPL_PNTS vr_bool ReadPntData(FILE *input, double *xc, double *yc, eap_type *eap_data); #else vr_bool ReadPntData(FILE *input, double *xc, double *yc); #endif #ifdef EXT_APPL_SITES vr_bool ReadSiteData(FILE *input, double *xc, double *yc, eas_type *eas_data); #else vr_bool ReadSiteData(FILE *input, double *xc, double *yc); #endif vr_bool ReadVectorData(FILE *input, double *xc, double *yc); #ifdef EXT_APPL_PNTS void WritePntData(FILE *output, double_arg xc, double_arg yc, eap_type *eap_data); #else void WritePntData(FILE *output, double_arg xc, double_arg yc); #endif short fSeeks(FILE *input, const char *strings[], short nbr); /* arg_eval.cc: */ vr_bool ArgEval(int argc, char *argv[], vr_bool *color_graphics, vr_bool *graphics, vr_bool *save_data, char *output_file, vr_bool *read_input, char *input_file, vr_bool *read_poly, int *step_size, vr_bool *verbose, vr_bool *write_ipe, vr_bool *help, vr_bool *time, vr_bool *statistics, vr_bool *copy, vr_bool *quiet, int *bound, int *sample, vr_bool *scale, int *approx, vr_bool *read_sites, vr_bool *read_xdr, vr_bool *read_graphml, vr_bool *discard_dupl_s, int *p_step_size, vr_bool *read_e00, vr_bool *read_dxf, vr_bool *read_polylines, double *t_offset, double *d_offset, vr_bool *write_off, char *off_file, int *o_step_size, vr_bool *auto_offset, vr_bool *full_screen, vr_bool *read_usgs, vr_bool *left_offset, vr_bool *right_offset, vr_bool *compute_wmat, double *wmat_angle, double *wmat_dist, vr_bool *auto_wmat, vr_bool *pnts_only, vr_bool *compute_mic, int *a_step_size, vr_bool *check_data, vr_bool *write_vd_dt, char *vd_dt_file, vr_bool *read_pnts, vr_bool *dxf_format, vr_bool *read_file, vr_bool *write_ma, char *ma_file, vr_bool *clean_up, vr_bool *write_vd, char *vd_file, double *vd_apx_dist, vr_bool *left_vd, vr_bool *right_vd, vr_bool *vr_incr, char *vr_file, int *inputprec, int *mpfr_prec, int *vr_seed); void EvalError(void); /* clean_data.cc: */ void CleanData(int *removed, int *removed_segs, int *removed_arcs, vr_bool discard_duplicate_sites); void RepairPntLinks(int i_del, int i_old, vr_bool repair_now); void FreeReverseIndex(void); vr_bool GetDataSorted(void); void ResetCleanStatus(void); /* prepro.cc: */ void AddSupportVertices(void); void RemoveSupportVertices(void); void SetPreprocessingThreshold(double_arg threshold); void ExtendBoundingBox(void); void PreprocessSegments(int *num_critical_segs); void PreprocessArcs(int *num_critical_arcs); void AdjustArcs(int *num_critical_arcs); void HandleBulge(const coord & p1, const coord & p2, double *bulge, coord *center, double *radius, int *attr); void ComputeBulge(const coord & p1, const coord & p2, double *bulge, const coord & center, double_arg radius, int attr); void ReplaceArc(int i); void ReplaceSeg(int i); /* approx.cc: */ void ApproxArcsHeuristic(int approx); void ApproxArcsBounded(double arc_absolute, double arc_relative); void SampleData(int sample); /* numerics.cc: */ double PntSiteConeClassificator(int i, t_site ti, coord q1, coord q2, const coord & q, double eps); #ifdef WITH_MPFRBACKEND void set_mpfrbackend_prec(mpfr_prec_t mpfr_prec, vr_bool verbose); #endif double ComputeSiteDistance(int i, t_site ti, const coord & p); vr_bool IntersectRayOffsetSeg(const coord & p, const coord & v, double_arg a, double_arg b, double_arg c, int k1, int k2, coord *centers, double *radii, int *num_solutions); vr_bool SegSegBisector(int i, int j, double_arg ai, double_arg bi, double_arg aj, double_arg bj, double_arg cj, coord *P, coord *V); vr_bool IterativeIntersection(t_site type1, t_site type2, /* object types */ double_arg a, double_arg b, double_arg c, /* line 1 */ const coord & c1, double_arg r1, /* circle 1 */ const coord & p2, /* start point or center of obj 2 */ double t_s, double t_e, /* parameters of obj 2 */ const coord & v2, /* direction vector of seg 2 */ double_arg r2, /* radius of arc 2 */ double *t_q, coord *q); /* vd_basic.cc: */ int ClassifySolutions(int i, int j, int k, int e, t_site i_type, t_site j_type, t_site k_type, vr_bool i_orig, vr_bool j_orig, vr_bool k_orig, coord *centers, double *radii, int *num_sol, double eps, vr_bool *problematic); vr_bool IntersectRayBisector(int i1, const coord & v, int e, coord *w, double *r2); void SetDeg2Flag(void); vr_bool GetDeg2Flag(void); void SetNodesSqdFlag(); vr_bool GetNodesSqdFlag(void); #ifdef GRAPHICS void FindClosestNode(double_arg xl, double_arg yl); #endif int GetVDIdentifier(void); void SetVDStatusTrue(void); void ResetVDStatus(void); void TakeSquareOfNodes(void); void InsertDummyNode(int e, int n, vr_bool store); void DeleteDummyNodes(void); void DeleteNode(int n); void DeleteEdge(int e); vr_bool CheckVD(vr_bool arcs_recovered); vr_bool InEdgesList(int index); vr_bool InNodesList(int index); int StoreNode(double_arg x, double_arg y, double_arg r2); void InitNodes(int number); int StoreEdge(int n1, int n2, int lft, int rgt, t_site ltype, t_site rtype); void InitEdges(int number); void FreeVDData(); void ResetVDData(void); void ComputeInitialVD(void); #ifdef GRAPHICS void AddVDEdgeToBuffer(int i); void AddVDToBuffer(vr_bool left_vd, vr_bool right_vd); void AddDelToBuffer(void); vr_bool CheckVDCell(int i, int e0, t_site t, vr_bool arcs_recovered); #endif void PrintNodeData(int n, const char *string); void PrintEdgeData(int e, const char *string); void PrintVDData(const char *string); /* vd_arc.cc: */ vr_bool IsSameSide(int i, t_site t, int j, int i1, coord p_node); void FindMostViolatedRecursiveArc(int e, int k0, int i1, int j, int k, int *n, double *dist); int FindMostViolatedNodeArc(int i1, int i2, int j, vr_bool *node_shared); void GetPntSiteNormal(int i, t_site site, coord p, coord* v, double* dist); void ProjectPntOnSite(int i, t_site site, coord p, coord* w); vr_bool PreserveVoronoiCellArc(int i, t_site t, int i0); vr_bool BreakLoopArc(int i0); void MarkNonRecursiveArc(int e, int n, int i, std::stack& e_stack, std::stack& n_stack, std::stack& i_stack); void MarkRecursiveArc(int e, int n, int i); void InsertArcIntoVD(int i); /* vd_data.cc: */ #ifdef TRACE unsigned long GetThresholdCounter(void); #endif void SetDebugFlagVD(vr_bool dbg_flag); void ResetLoopStackSize(int size); void ResetLoopStackMin(int size); void ResetLoopStack(); void GetLoopStackSize(int& size); void GetLoopStackMin(int& size); int GetLoopStackSizeFunc(void); int GetLoopStackMinFunc(void); int GetLoopStackElementFunc(int I); void FreeVDConstructionData(void); void ResetVDConstructionData(void); void UpdateRecursive(int i, t_site t, int n, int e, int *el, int *er, int *nl, int *nr); void ResetTreeDeleteStatus(int e, int n); void InsertApexDegreeTwoNodeSeg(int e, int i, int i1, t_site t1); void InsertApexDegreeTwoNodeArc(int e, int i, int i1, t_site t1); void ResetNodeStatus(int e, int n); void PurifyLoop(int n1, int n3); vr_bool LoopExists(int e, int n, int *m); vr_bool ComputeCenter(int e, int i3, t_site t3, coord *w, double *r2, vr_bool *problematic, int *site); /* vd_pnt.cc: */ int FindMostViolatedNodePnt(int i, coord p); void UpdateRecursivePnt(int i, int n, int e, int *el, int *er, int *nl, int *nr); void InsertPntIntoVD(int i); /* vd_seg.cc: */ void FindMostViolatedRecursiveSeg(int e, /* current VD edge */ int k0, /* start node of recursive scan */ int i1, /* pnt that coincides with k0 */ int j,/* segment to be inserted into VD */ int k, /* current node */ int *n, /* closest node found by scan */ double *dist); /* distance of node n */ int FindMostViolatedNodeSeg(int i1, /* start point of seg */ int i2, /* end point of seg */ int j, /* segment to be inserted into VD */ vr_bool *node_shared, double *diff); vr_bool PreserveVoronoiCellSeg(int i, t_site t, int i0); vr_bool BreakLoopSeg(int i0); void MarkNonRecursiveSeg(int e, int n, int i, std::stack& e_stack, std::stack& n_stack, std::stack& i_stack); void MarkRecursiveSeg(int e, int n, int i); void InsertSegIntoVD(int i); /* tree.cc: */ void FreeTree(void); int InitTree(int number, int *first_N_points, int N_Initial, double *min_dist); int InsertPntIntoTree(int ind, double *dist_min, vr_bool no_distance); vr_bool InTree(int idx); #ifdef GRAPHICS void DrawTree(void); #endif /* grid.cc: */ void DeletePntFromGrid(int index); void FreeGrid(void); void SetUpGrid(int number); void BuildGrid(void); void InitGrid(void); vr_bool InGrid(int cell); void InitRaster(void); void InitPntList(int number); #ifdef GRAPHICS void DrawCell(int i, int j); void DrawGrid(void); #endif int InsertPntIntoGrid(int index, double *min_dist); int FindNearestNeighborGrid(int index, int i_min, double *min_dist); /* pnt_pnt_pnt.cc: */ vr_bool PntPntPntCntr(int i, int j, int k, coord *ctr, double *radius); vr_bool NumericalPntPntPntCntr(const coord & A, const coord & B, const coord & C, coord *cntr, double *r2); /* seg_pnt_pnt.cc: */ vr_bool SegPntPntCntr(int i, int j, int k, int e, coord *cntr, double *r2, vr_bool *problematic); vr_bool SegPntCntr(int i, coord p, coord *cntr, double *r2); /* seg_seg_pnt.cc: */ vr_bool SegSegPntCntr(int i, int j, int k, int e, coord *cntr, double *r2, vr_bool *problematic, int *site); /* seg_seg_seg.cc: */ vr_bool SegSegSegCntr(int i, int j, int k, int e, coord *cntr, double *r2, vr_bool *problematic, int *site); /* arc_arc_arc.cc: */ vr_bool ArcArcArcCntr(int i, int j, int k, int e, coord *cntr, double *r2, vr_bool *problematic, int* site); /* arc_arc_pnt.cc: */ vr_bool ArcArcPntCntr(int i, int j, int k, int e, coord *cntr, double *r2, vr_bool *problematic, int* site); /* arc_pnt_pnt.cc: */ vr_bool ArcPntPntCntr(int i, int j, int k, int e, coord *cntr, double *r2, vr_bool *problematic); /* arc_arc_seg.cc: */ vr_bool ArcArcSegCntr(int i, int j, int k, int e, coord *cntr, double *r2, vr_bool *problematic, int* site); /* arc_seg_pnt.cc: */ vr_bool ArcSegPntCntr(int i, int j, int k, int e, coord *cntr, double *r2, vr_bool *problematic, int* site); /* arc_seg_seg.cc: */ vr_bool ArcSegSegCntr(int i, int j, int k, int e, coord *cntr, double *r2, vr_bool *problematic, int* site); /* arc_common.cc: */ int ArcRoots2abc(double a, double b, double c, double* roots); /* misc.cc: */ void ResetIntersectionData(void); #ifndef API_PARABOLIC void AddParabolaToBuffer(int i, double t1, double t2, coord u, coord v, int color); #endif #ifdef GENUINE_ARCS void AddHyperbolaEllipseToBuffer(int i, double t1, double t2, coord u, coord v, int color); #endif double NodeRadiiClassificator(int e, coord p); double NodeSegClassificator(int i, coord p); double NodeSidednessClassificator(int i, t_site ti, /* old site */ const coord & q, /* old node */ const coord & p); /* new node */ double NodeEdgeClassificator(int e, const coord & p, double eps); void SplitAtIntersection(int i1, int i2, t_site t1, t_site t2, coord w); vr_bool IsPntOnPnt(int i1, int i2, double eps); vr_bool IsPntOnSeg(int i1, int i2, double eps); #ifdef GENUINE_ARCS vr_bool IsPntOnArc(int i1, int i2, double eps); #endif vr_bool IsSegSegIntersection(int i1, int i2, double eps); #ifdef GENUINE_ARCS vr_bool IsSegArcIntersection(int i1, int i2, double eps); vr_bool IsArcArcIntersection(int i1, int i2, double eps); #endif void SetStepSize(double_arg delta); void InsertDegreeTwoNodes(void); vr_bool IsInvalidData(vr_bool critical); void CheckDataPnt(int *int_found); void CheckDataSeg(int *int_found); void CheckDataArc(int *int_found); void SubdivideLongEdges(void); void SetInvalidSites(int i1, t_site t1, int i2, t_site t2, double eps); double ClassifySolPnt(int i, const coord & p, double_arg clear); double ClassifySolSeg(int i, const coord & p, double_arg clear); double ClassifySolArc(int i, const coord & p, double_arg clear); /* api_parabolic.cc */ #ifdef API_PARABOLIC void ApproxParabolicVDEdge(int i, double t, double apx_eps, int *num_apx_pnts, coord **apx_pnts); void AddParabolaToBuffer(int i, double t1, double t2, coord u, coord v, int color); void SegCircleIntersection(coord p_start, coord p_end, double t_start, double t_end, coord center, double radius, int *num_pnts, coord *p1, coord *p2, double *t1, double *t2); void ParCircleIntersection(int i, coord center, double radius, int *num_pnts, coord *p1, coord *p2, double *t1, double *t2); void VDEdgeCircleIntersection(int i, coord center, double radius, int *num_pnts, coord *p1, coord *p2, double *t1, double *t2); void DoCircleIntersections(int number); void API_ParabolicStatistics(); #endif /* desperate.cc: */ vr_bool DesperatePntPntPntCntr(const coord & A, const coord & B, const coord & C, coord *cntr, double *r2); void DesperateSampleEdge(int e, int i, t_site t, coord *w, double *r2); void DesperateComputeCenter(int e, int i, t_site t, coord *w, double *r2); int DesperateFindMostViolatedNodeSeg(int i1, int j); void DesperatePreserveVoronoiCellSeg(int i, t_site t, int i0); void DesperateBreakLoopSeg(int i0); int DesperateFindMostViolatedNodeArc(int i1, int j); void DesperatePreserveVoronoiCellArc(int i, t_site t, int i0); void DesperateBreakLoopArc(int i0); /* data_off.cc: */ void RecApxVDEdge(int e, double delta, coord3D **active_pnts, int *num_active_pnts, int *max_num_active_pnts, coord p1, coord p2, double t1, double t2); void ScanVDCell(int e, int i, t_site type, FILE *fp); void ApproximateVDEdge(int e, double delta, coord3D **active_pnts, int *num_active_pnts, int *max_num_active_pnts); void StoreActivePnt(coord3D **active_pnts, int *num_active_pnts, int *max_num_active_pnts, int i, vr_bool isPnt); void StoreActiveEdge(int e); vr_bool InEdgeDataList(int i); vr_bool InEdgeFlagList(int i); vr_bool InActiveEdgeList(int i); vr_bool IsCorrectSide(int i, int type, int n, vr_bool left_offset); void ScanVDEdges(int e, int n, vr_bool offset_side, vr_bool compute_mic, int *max_edge, double *max_rad); void InitializeEdgeData(vr_bool unrestricted, vr_bool left_offset, vr_bool compute_mic, int *mic_edge); void FreeEdgeData(void); vr_bool ComputeParabolaData(int i, e_formula *coeff); void CreateParabolaData(int i); vr_bool ComputeHyperbolaData(int i, e_formula *coeff); void CreateHyperbolaData(int i); void EvaluateDegenerateHyperEll(int i, double t, coord *w); vr_bool ComputeHyperbolaEllipseData(int i, e_formula *coeff); void CreateHyperbolaEllipseData(int i); vr_bool ComputeLineData(int i, e_formula *coeff); void CreateLineData(int i); void EvaluateDegenerateEdge(int i, double_arg t, coord *w); void EvaluateParabolaData(int i, int i1, double_arg t, coord *w); void EvaluateHyperbolaData(int i, double t, coord *w); void EvaluateLineData(int i, double t, coord *w); void EvaluateHyperbolaEllipseData(int i, double_arg t, coord *w); void ResetEdgeData(void); void OutputMAEdges(FILE *output, int e, int n); void OutputMA(char output_file[]); void OutputVD(char output_file[], double vd_apx_dist, vr_bool left_vd, vr_bool right_vd); /* offset.cc */ void SetMaxOffset(double_arg t); vr_bool InOffsetData(int I); vr_bool InOffsetList(int I); void ResetOffsetData(void); vr_bool ScrutinizeArc(coord start, coord end, coord center, vr_bool *ori, double eps, vr_bool not_isolated); void ComputeOff(int step_size, vr_bool time, char off_file[], vr_bool write_off, vr_bool dxf_format, double_arg t_offset, double_arg d_offset, vr_bool *finished, vr_bool left_offset, vr_bool right_offset); void FreeOffsetData(void); void WriteOffsets(char off_file[]); void WriteOffsetsDXF(char off_file[]); #ifdef EXT_APPL_OFF eao_type GetExtApplOffsetFunc(int O); void SetExtApplOffsetFunc(int O, eao_type ext_appl); #endif #ifdef GRAPHICS void AddOffsetsToBuffer(void); #endif off_list* GetOffsetList(int i); off_data* GetOffsetData(int i); void ComputeIsolatedOffsets(double_arg t0, double_arg d_off); void ComputeOffset(int i, double_arg t); void StartOffsets(void *output, int num_offset_loops); void StartOffsetLoop(void *output, int num_offset_elements); void WriteOffsetSeg(void *output, #ifdef EXT_APPL_OFF eao_type ext_appl_off, #endif double_arg x1, double_arg y1, double_arg x2, double_arg y2); void WriteOffsetArc(void *output, #ifdef EXT_APPL_OFF eao_type ext_appl_off, #endif double_arg x1, double_arg y1, double_arg, double_arg, double_arg xc, double_arg yc, vr_bool ccw); void EndOffsetLoop(void *, int, int, double_arg, double_arg); void EndOffsets(void *, int, int, int); void StartOffsetsDXF(void *output, int); void StartOffsetLoopDXF(void *output, int); void WriteOffsetSegDXF(void *output, #ifdef EXT_APPL_OFF eao_type, #endif double_arg x1, double_arg y1, double_arg, double_arg); void WriteOffsetArcDXF(void *output, #ifdef EXT_APPL_OFF eao_type, #endif double_arg x1, double_arg y1, double_arg x2, double_arg y2, double_arg xc, double_arg yc, vr_bool ccw); void EndOffsetLoopDXF(void *output, int, int, double_arg, double_arg); void EndOffsetsDXF(void *output, int, int, int); #ifdef GRAPHICS void StartOffsetsBuf(void*, int); void StartOffsetLoopBuf(void*, int); void WriteOffsetSegBuf(void*, #ifdef EXT_APPL_OFF eao_type ext_appl_off, #endif double_arg x1, double_arg y1, double_arg x2, double_arg y2); void WriteOffsetArcBuf(void*, #ifdef EXT_APPL_OFF eao_type ext_appl_off, #endif double_arg x1, double_arg y1, double_arg x2, double_arg y2, double_arg xc, double_arg yc, vr_bool ccw); void EndOffsetLoopBuf(void*, int, int, double_arg, double_arg); void EndOffsetsBuf(void*, int, int, int); #endif /* wmat.cc */ void CheckWMAT(double wmat_dist, double wmat_angle); vr_bool GetWMATStatus(void); void ResetWMATStatus(void); void ComputeWMAT(double wmat_angle, double wmat_dist, vr_bool time, vr_bool left_wmat, vr_bool right_wmat); #ifdef EXT_APPL_WMAT eam_type GetExtApplWMAT(int E); void SetExtApplWMAT(int E, eam_type ext_appl); #endif #ifdef GRAPHICS void AddWMATToBuffer(void); #endif /* mic.cc */ vr_bool GetMICStatus(void); void ResetMICStatus(void); void ComputeMIC(vr_bool time, vr_bool left_mic, vr_bool right_mic, coord *center, double *radius); /* intersections.cc */ grid* InitialiseGrid(int num_elements, coord bb_min, coord bb_max); void AddPointToGrid(grid* g, int i1, double_arg eps); void AddSegToGrid(grid* g, int i1, double_arg eps); vr_bool CheckSegIntersectsGridVerSeg(int seg, double_arg x, double_arg y1, double_arg y2, double_arg eps); vr_bool CheckSegIntersectsGridHorSeg(int seg, double_arg x1, double_arg x2, double_arg y, double_arg eps); vr_bool AddSegIntersection(seg_entry* seg, coord intersection); #ifdef GENUINE_ARCS void AddArcToGrid(grid* g, int i1, double_arg eps); vr_bool AddArcIntersection(arc_entry* arc, coord intersection); vr_bool CheckArcIntersectsGridVerSeg(int arc, double_arg x, double_arg y1, double_arg y2, double_arg eps); vr_bool CheckArcIntersectsGridHorSeg(int arc, double_arg x1, double_arg x2, double_arg y, double_arg eps); #endif void SplitAtIntersections(grid* grid, double_arg eps); void FillGrid(grid* g, double_arg eps); double GetIntersectionThreshold(void); vr_bool ComputeAllIntersections(double_arg eps); vr_bool CheckIntersections(void); vr_bool IsCheckComplete(void); void ResetIntersectionStatus(void); vr_bool ThresholdReached(void); vr_bool GetSegSegIntersection(int i1, int i2, coord* result, double_arg eps, vr_bool *ident); int GetSegArcIntersection(int seg, int arc, coord* res1, coord* res2, double_arg eps); int GetArcArcIntersection(int i1, int i2, coord* res1, coord* res2, double_arg eps, vr_bool *ident_arcs); vr_bool CheckPntPnt(int i1, int i2, double_arg eps); vr_bool CheckPntOnSeg(int seg, int pnt, double_arg eps); vr_bool CheckPntOnArc(int arc, int pnt, double_arg eps); void DeleteGrid(grid* grid); int FindCellX(grid* g, double_arg x); int FindCellY(grid* g, double_arg y); vr_bool CheckIntersectionsLocally(int i1, t_site t1, int i2, t_site t2, int i3, t_site t3); /* elapsed.cc */ double elapsed(); // // FRIENDS (allow specific API functions to access/call protected members) // /* in api_functions.cc */ friend void API_ParseCommandLineArgs(int argc, char *argv[], vr_bool *graphics, vr_bool *color_graphics, vr_bool *full_screen); friend void API_OutputMA(char vdma_file[]); friend void API_GetInputData(vr_bool *input_received); friend void API_ProceedWithoutGraphics(vr_bool new_input); /* in graphics_ogl.cc */ #ifdef GRAPHICS #ifdef OGL_GRAPHICS friend void UpdateScaleData(void); friend void QuickDisplay(); friend void ResetGraphicsData(void); friend void UnZoom(void); friend void HandleMouseButton(int button, int state, GLint pix_i2, GLint pix_j2); friend void HandleKeyPress(unsigned char key, GLint pix_i1, GLint pix_j1); friend void HandleSpecialKeys(int key, GLint pix_i1, GLint pix_j1); friend void HandleViewMenu(int item); friend void InitializeGraphics(int argc, char *argv[], vr_bool color_graphics, vr_bool full_screen); friend void ProcessGraphicsEvents(void); #endif // OGL_GRAPHICS #endif private: // // PRIVATE VARIABLES // vr_bool troubles; vr_bool io_troubles; // I/O trouble count used by VD_IO_Warning /* api_functions.cc */ coord bb_min; coord bb_max; vr_bool verbose; vr_bool quiet; vr_bool statistics; vr_bool numerical; vr_bool scale_data; vr_bool check_data; double LARGE; in_pnts *pntd; in_segs *segd; in_arcs *arcd; /* compute.cc */ vr_bool incremental; vr_bool restart; vr_bool restart_due_to_intersection; vr_bool pnts_deleted; vr_bool desperate; double cpu_time_pre; double cpu_time_pnt; double cpu_time_seg; double cpu_time_arc; double cpu_time_off; double cpu_time_wmat; double cpu_time_mic; double cpu_time_cln; int removed_pnts; int removed_segs; int removed_arcs; int max_n_pnts; int n_pnts; int n_segs; int restart_counter; int num_critical_segs; int num_critical_arcs; int intersection_counter; int restart_without_intersection; vr_bool done_pnts; vr_bool done_segs; vr_bool done_arcs; vr_bool initialized; vr_bool written; vr_bool first_pnts; vr_bool first_segs; #ifdef GENUINE_ARCS int n_arcs; vr_bool first_arcs; #endif #ifdef INIT_FORCED FILE *fcd_output; #endif /* data.cc */ vr_bool data_scaled; double scale_factor; coord shift; int max_num_pnts; int max_num_segs; int max_num_arcs; vr_bool bbox_initialized; vr_bool bbox_added; vr_bool support_vtx_added; int num_pnts_added; int num_pnts_deleted; int num_segs_deleted; int num_arcs_deleted; #ifdef RANDOM vronivector m_rnd_sites; int m_num_rnd_sites; int m_max_num_rnd_sites; int m_cur_rnd_sites; #endif #ifdef FORCED vronivector fcd_sites; int num_fcd_sites; int max_num_fcd_sites; int cur_fcd_sites; #endif #ifdef SORTED vronivector srt_sites; int num_srt_sites; int max_num_srt_sites; #endif vr_bool dxf_poly_started; vr_bool dxf_vertex_added; int dxf_vertex_index; int dxf_vertex_first; #ifdef ORDERED int site_counter; vronivector ord_sites; int num_ord_sites; int max_num_ord_sites; #endif #ifndef ORDERED #ifndef SORTED #ifndef RANDOM #ifndef FORCED int nosr; #endif #endif #endif #endif /* io_basic.cc */ vr_bool isolated_pnts; /* io_dxf.cc */ int dxf_handle; /* vd_basic.cc */ #ifdef VRONI_INFO double max_relaxation; double curr_relaxation; #endif double too_large; int num_nodes; int max_num_nodes; int num_edges; int max_num_edges; vronivector free_nodes; vronivector free_edges; int num_free_nodes; int max_num_free_nodes; int num_free_edges; int max_num_free_edges; typedef struct { int e1; int e2; int n; } dummy_node; dummy_node *dummies; int num_dummies; int max_num_dummies; vr_bool VD_computed; vr_bool deg2_nodes_inserted; vr_bool VD_nodes_squared; int VD_identifier; /* prepro.cc */ double preProZero; /* vd_data.cc */ vr_bool debug_flag_VD; typedef struct { int ind; t_site type; } s_visited; s_visited *sites_visited; int num_visited; int max_num_visited; int *pnt_visited; int num_pnt_visited; int max_num_pnt_visited; int *nodes_checked; int num_checked; int max_num_checked; double zero; typedef struct { int site; t_site type; } preserve_buffer; preserve_buffer *preserve; int num_preserve; int max_num_preserve; int *loop_stack; int num_loop_stack; int min_loop_stack; int max_num_loop_stack; #ifdef TRACE unsigned long threshold_counter; vr_bool dbg_center; #endif /* misc.cc */ #ifdef GENUINE_ARCS double misc_step_size; #else double misc_step_size; #endif int invalid_i1; int invalid_i2; t_site invalid_t1; t_site invalid_t2; double invalid_eps; /* intersections.cc */ vr_bool check_completed; double eps_int; double comp_eps; /* vd_pnt.cc */ vr_bool grid_used; /* clean_data.cc */ typedef enum { ISO_PNT, SEG_START, SEG_END, ARC_START, ARC_END } index_type; struct reverse_index { int site; index_type type; int next; //Ensure construction doesn't implicitly initialize elements - done explicitly later anyway inline reverse_index() {} }; vronivector reverse_ind; int max_num_reverse_ind; int num_reverse_ind; vr_bool reverse_index_exists; vr_bool data_sorted; vr_bool clean_initialized; /* arg_eval.cc */ #ifdef TRACE vr_bool center; vr_bool write_debug; vr_bool proto; int max_cntr; #endif #ifdef OTHER vr_bool cgal; #endif /* voronoi.cc */ #ifdef TRACE int stack_size; int max_stack_size; #endif /* moved from vddata.h */ vronivector pnts; vronivector segs; vronivector arcs; int num_pnts; int num_segs; int num_arcs; vronivector nodes; vronivector edges; /* grid.cc */ int N_Initial; typedef struct { int pnt; int next; } pnt_node; int *the_grid; int max_num_grid; int N; int N_x; int N_y; double grid_x; double grid_y; double grid_a; double grid_b; double grid_min_x; double grid_min_y; double grid_max_x; double grid_max_y; vronivector raster_x; vronivector raster_y; int max_num_raster_x; int max_num_raster_y; pnt_node *pnt_list; int num_pnt_list; int max_num_pnt_list; double grid_delta_x; double grid_delta_y; int *first_N_pnts; int first_counter; /* heap.cc */ struct heap_node { double key; int ref; //Ensure construction doesn't implicitly initialize elements - done explicitly later anyway heap_node() {} }; vronivector heap; int num_heap; int max_num_heap; vr_bool deleted; vr_bool not_updated; /* tree.cc */ typedef struct tnode { int splitter; /* pnts[splitter] defines the splitting point */ int ch1; /* below and to the left of the splitter */ int ch2; /* above and to the left of the splitter */ int ch3; /* below and to the right of the splitter */ int ch4; /* above and to the right of the splitter */ } tree_node; double tree_min_x; double tree_min_y; double tree_max_x; double tree_max_y; double tree_delta_x; double tree_delta_y; tree_node *tree; int num_tree; int max_num_tree; int root_of_tree; /* memory.cc */ #ifdef DEBUG_MEMORY typedef struct { void *array_ptr; size_t size; unsigned int high; } memory_dbg; #define MAX_MEMORY_CURSOR 32768 unsigned long curr_memory; unsigned long max_memory; memory_dbg memory_history[MAX_MEMORY_CURSOR]; int memory_dbg_cursor; typedef enum { mem_freed, mem_allocated, mem_reallocated } memory_status; void UpdateMemoryStatus(void *ptr, memory_status status, size_t size, unsigned int high); int SearchMemoryHistory(void *ptr); #endif /* local.h */ double martin_h_local; double basic_h_local; double basic_h_local_delta; double basic_h_local_quot; long basic_i_local; coord numerics_h_p; coord numerics_h_q; coord numerics_h_r; double numerics_h_det; double numerics_h_x; double numerics_h_y; double numerics_h_local; /* elapsed.cc */ #ifndef NO_CPUTIME #ifdef CPUTIME_BY_CHRONO std::chrono::high_resolution_clock::time_point start; vr_bool elapsed_initialized; #else #ifdef CPUTIME_IN_MILLISECONDS unsigned long total_secs; unsigned long total_usecs; #else /* ifndef CPUTIME_IN_MILLISECONDS */ #ifdef CPUTIME_VIA_CLOCK clock_t total_cpu_time; vr_bool elapsed_initialized; #else /* ifndef CPUTIME_IN_MILLISECONDS || CPUTIME_VIA_CLOCK */ long total; int HZ; #endif #endif #endif #endif // // PRIVATE FUNCTIONS // /* geom.h | geom.cc */ /** Compute squared distance between two points */ double PntPntDistSq(coord pi, coord pj); /** Compute distance between two points */ double PntPntDist(coord pi, coord pj); /** Compute mid point on the line (pi,pj) */ coord MidPoint(coord pi, coord pj); /** Compute centroid point of the triangle (pi,pj,pk) */ coord Centroid(coord pi, coord pj, coord pk); /** Build linar combination of vectors p and r by parameter t */ coord LinearComb(const coord & p, const coord & r, double_arg t); /** Get the point q = p + t*v */ coord RayPnt(const coord & p, const coord & v, double_arg t); /** Compute point on circle with center c and radius r * at angle phi in mathematical sense.*/ coord CirclePnt(const coord & c, double_arg r, double_arg phi); /** Compute (signed) distance of point p to circle (c,r). Positive * values indicate that p is outside the circle (c,r). */ double PntCircleDist(const coord & c, double_arg r, const coord & p); /** Compute absolute distance of point p tor circle (c,r) */ double AbsPntCircleDist(const coord & c, double_arg r, const coord & p); /** Test if point p is on circle (c,r) */ int IsPntOnCircle(const coord & c, double_arg r, const coord & p); /** Compute the signed distance of the point p to the line given by * the equation a*x + b*y + c = 0. A positive result means that * p lies in the positive half-plane defined by the line. */ double PntLineDist(double_arg a, double_arg b, double_arg c, const coord & p); /** Compute the absolute distance of the point p to the line given by * the equation a*x + b*y + c = 0 */ double AbsPntLineDist(double_arg a, double_arg b, double_arg c, const coord & p); /** Compute a uniform distributed random point */ coord UniformRandomPoint(); vr_bool IsBetweenVoronoiNodes(int e, const coord & p, double eps); /* arc_common.h | arc_common.cc */ /* Given three circles with centers c1, c2, and c3 and radii r1, r2, and r3 this function calculates all points p which are equidistant to the given circles and saves them in centers. The corresponding distances are saved in radii. The number of points found is returned. */ int CircCircCircCenters(const coord & c1, const coord & c2, const coord & c3, double_arg r1, double_arg r2, double_arg r3, coord* centers, double* radii, double eps); /* Given a circle with center c1 and two points c2 and c3, this function calculates all points p which are equidistant to the given circle and points and saves them in centers. The corresponding distances are saved in radii. The number of points found is returned. */ int CircPntPntCenters(const coord & c1, const coord & c2, const coord & c3, double_arg r1, double_arg l, coord* centers, double* radii); /* Given two circles with centers c1, c2 and radii r1, r2 and a segment in Hessian normal form s1a.x + s1b.y = s1c this function calculates all points p which are equidistant to the given sites and saves them in centers. The corresponding distances are saved in radii. The number of points found is returned. */ int CircCircSegCenters(const coord & c1, const coord & c2, double_arg r1, double_arg r2, double_arg s1a, double_arg s1b, double_arg s1c, coord* centers, double* radii, double eps); /* Given a circle with center c1 and radius r1 and two segments in Hessian normal form s1a.x + s1b.y = s1c, s2a.x + s2b.y = s2c this function calculates all points p which are equidistant to the given sites and saves them in centers. The corresponding distances are saved in radii. The number of points found is returned. */ int CircSegSegCenters(const coord & c1, double_arg r1, double_arg s1a, double_arg s1b, double_arg s1c, double_arg s2a, double_arg s2b, double_arg s2c, coord* centers, double* radii, double eps); /* Determine the set of all points which are equidistant to two arcs which are centered at c1 and share a common endpoint ep and a circle which is centered at c2 and has a radius r2. The centers and radii found are saved in centers and radii, respectively. This function returns the number of found points. */ int ConcentricArcsCircleCenter(coord c1, coord ep, coord c2, double r2, coord* centers, double* radii); /* Determine the set of all points which are equidistant to two arcs which are centered at c1 and share a common endpoint ep and a segment which has Hessian normal form a2.x + b2.y = c2. The centers and radii found are saved in centers and radii, respectively. This function returns the number of found points. */ int ConcentricArcsSegCenter(coord c1, coord ep, double a2, double b2, double c2, coord* centers, double* radii); /** Test whether pnt is in arc-cone. */ vr_bool IsPntInArcConeEps(int arc, const coord & pnt, double_arg eps); /** Test whether pnt is in arc-cone. */ vr_bool IsPntInArcCone(int arc, coord pnt); /** Test whether pnt is in arc-cone. */ vr_bool IsPntInArcConeStrict(int arc, coord pnt); /** Intersect two Circles */ int IntersectTwoCircles(const coord & c1, const coord & c2, double_arg r1, double_arg r2, coord* left, coord* right); /** Intersect Circle with segment*/ int IntersectCircleSeg(const coord & c, double_arg r, double_arg a, double_arg b, double_arg d, coord* left, coord* right); /** Do arc and pnt intersect in inner of arc? (Higher eps --> less likely an intersection) */ vr_bool DoArcPntIntersect(int arc, const coord & pnt, double_arg eps); /** * The circle centered at c1 with radius r1 and the circle c2 with the radius r2 are placed * side-by-side and a hyperbola is defined as bisector. This bisector has two asymptotes which * are determined. The directions of those are saved in dir1 and dir2. The start points of * these rays are at (a,b) resp. (a,-b) modulo rotation and offset from the crossing point. * These is useful to get an approximation to min. distance to both circles. */ void GetAsymptotes(const coord & c1, double_arg r1, const coord & c2, double_arg r2, coord *start1, coord *dir1, coord* start2, coord *dir2); /* * We shoot a ray starting at p in direction v and intersect this ray with * the offset circles of the point c. Hence, the intersection lies on the ray * and is equidistant to p and to c. Effectively, this means intersecting * the bisector between p and c with the ray. * * returns the number of solutions * */ int IntersectRayPoint(const coord & p, coord v, const coord & c, coord* centers, double* radii, double eps); /* * We shoot a ray starting at p in direction v and intersect this ray with the * offset-circles of the circle centered at c and with radius r. So the * intersection lies on the ray and is equidistant to p and to the circle (c,r) * * returns the number of solutions * */ int IntersectRayCircle(const coord & p, coord v, const coord & c, double_arg r, coord* centers, double* radii, double eps); /** We shoot a ray starting at p in direction v and intersect this ray with the offset-segments * of the segment with normal vector (a,b) and hesse form a.x+b.y=c. So the intersection lies on the * ray and is equidistant to p and to the segment. * * returns the number of solutions * */ int IntersectRaySegment(const coord & p, coord v, double_arg a, double_arg b, double_arg c, coord* centers, double* radii, double eps); /* wmat.cc */ #ifdef WMAT void ComputeWMATParabola(int i, int i1, int i2, double_arg wmat_cosine, double_arg wmat_dist_sq); void ComputeWMATHyperbola(int i, int i1, int i2, double_arg wmat_cosine, double_arg wmat_dist_sq); void ComputeWMATLine(int i, int i1, int i2, double wmat_cosine, double wmat_dist_sq); void ComputeWMATEdge(int e, double_arg wmat_cosine, double_arg wmat_dist_sq); #else void ComputeWMATParabola(int i, int i1, int i2); void ComputeWMATHyperbola(int i); void ComputeWMATLine(int i); void ComputeWMATEdge(int e); #endif /* clean_data.cc: */ vr_bool InReverseIndList(int i); void InsertReverseIndex(const int ipnt, const int isite, const index_type tsite); void SetUpReverseIndex(int number_of_segs, int number_of_arcs, vr_bool set_idx); /* heap.cc */ void StoreHeapData(int idx, double s_key, int s_ref); void GetHeapData(int idx, double *s_key, int *s_ref); void FreeHeap(void); vr_bool InHeap(int idx); vr_bool InHeapInsert(int idx); void DumpOnHeap(double_arg key, int ref); void UpdateHeap(double_arg key, int ref); void ExtendHeap(double_arg key, int ref); void InsertIntoHeap(double_arg key, int ref); vr_bool DeleteFromHeap(double *key, int *ref); void InitHeap(void); void ResetHeap(void); /* tree.cc */ void RecursiveInitTree(double x_min, double y_min, double x_max, double y_max, int *first_N_points, int *m, int level); #ifdef GRAPHICS void RecursiveDrawTree(double x_min, double y_min, double_arg x_max, double_arg y_max, int root); #endif /****************************************************************************/ /* funioni aggiunte per integrazione con nostre librerie */ /****************************************************************************/ public : void GetPointFromCoord( coord ptCoord, double p[3]) ; // offset int GetOffsetCount() { return num_offset_list ; } ; int GetOffsetCurveCount( int i) ; vr_bool GetOffsetCurve( int nOffs, int nCrv, int& nType, double ptS[3], double ptE[3], double ptC[3], int& nOrigLoop, int& nOrigCrv, int& nOrigPnt) ; // voronoi void ResetVoronoiDiagram(void) ; void GetVDBisectorPoints( int i, double ptS[3], double ptE[3]) ; void GetVDBisectorParams( int i, double& dParS, double& dParE) ; BisectorType GetVDBisectorType( int i) ; void GetVDBisectorPointAtParam( int nEdge, double dPar, double pt[3]) ; // media axis vr_bool IsWMATEdge( int nEdge) ; // debug void MyWriteVoronoiRegion( FILE *output) ; }; /* inline function includes */ #include "geom.h" #ifdef GENUINE_ARCS #include "arc_common.h" #endif #include "vd_data.h" #include "numerics.h" #endif