FastJet 3.0.0
|
00001 #ifndef __FASTJET__VORONOI_H__ 00002 #define __FASTJET__VORONOI_H__ 00003 00004 //STARTHEADER 00005 // $Id: Voronoi.hh 2548 2011-08-16 16:04:14Z salam $ 00006 // 00007 // Copyright (c) 1994 by AT&T Bell Laboratories (see below) 00008 // 00009 // 00010 //---------------------------------------------------------------------- 00011 // This file is included as part of FastJet but was mostly written by 00012 // S. Fortune in C, put into C++ with memory management by S 00013 // O'Sullivan, and with further interface and memeory management 00014 // modifications by Gregory Soyez. 00015 // 00016 // Permission to use, copy, modify, and distribute this software for 00017 // any purpose without fee is hereby granted, provided that this 00018 // entire notice is included in all copies of any software which is or 00019 // includes a copy or modification of this software and in all copies 00020 // of the supporting documentation for such software. THIS SOFTWARE IS 00021 // BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED WARRANTY. 00022 // IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY REPRESENTATION 00023 // OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS 00024 // SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. 00025 // 00026 //---------------------------------------------------------------------- 00027 //ENDHEADER 00028 00029 00030 /* 00031 * The author of this software is Steven Fortune. 00032 * Copyright (c) 1994 by AT&T Bell Laboratories. 00033 * Permission to use, copy, modify, and distribute this software for any 00034 * purpose without fee is hereby granted, provided that this entire notice 00035 * is included in all copies of any software which is or includes a copy 00036 * or modification of this software and in all copies of the supporting 00037 * documentation for such software. 00038 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED 00039 * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY 00040 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY 00041 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. 00042 */ 00043 00044 /* 00045 * This code was originally written by Stephan Fortune in C code. I, 00046 * Shane O'Sullivan, have since modified it, encapsulating it in a C++ 00047 * class and, fixing memory leaks and adding accessors to the Voronoi 00048 * Edges. Permission to use, copy, modify, and distribute this 00049 * software for any purpose without fee is hereby granted, provided 00050 * that this entire notice is included in all copies of any software 00051 * which is or includes a copy or modification of this software and in 00052 * all copies of the supporting documentation for such software. THIS 00053 * SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED 00054 * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY 00055 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE 00056 * MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR 00057 * PURPOSE. 00058 */ 00059 00060 #include "fastjet/LimitedWarning.hh" 00061 #include <vector> 00062 #include <math.h> 00063 #include <stdlib.h> 00064 #include <string.h> 00065 00066 #define DELETED -2 00067 #define le 0 00068 #define re 1 00069 00070 FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh 00071 00072 /** 00073 * \if internal_doc 00074 * @ingroup internal 00075 * \class VPoint 00076 * class to handle a 2d point 00077 * \endif 00078 */ 00079 class VPoint{ 00080 public: 00081 /// defailt ctor 00082 VPoint() : x(0.0), y(0.0) {} 00083 00084 /// ctor with initialisation 00085 VPoint(double _x, double _y) : x(_x), y(_y) {} 00086 00087 /// addition 00088 inline VPoint operator + (const VPoint &p) const{ 00089 return VPoint(x+p.x, y+p.y); 00090 } 00091 00092 /// subtraction 00093 inline VPoint operator - (const VPoint &p) const{ 00094 return VPoint(x-p.x, y-p.y); 00095 } 00096 00097 /// scalar multiplication 00098 inline VPoint operator * (const double t) const{ 00099 return VPoint(x*t, y*t); 00100 } 00101 00102 /// vector coordinates 00103 double x,y; 00104 }; 00105 00106 00107 /// norm of a vector 00108 inline double norm(const VPoint p){ 00109 return p.x*p.x+p.y*p.y; 00110 } 00111 00112 00113 /// 2D vector product 00114 inline double vector_product(const VPoint &p1, const VPoint &p2){ 00115 return p1.x*p2.y-p1.y*p2.x; 00116 } 00117 00118 00119 /// scalar product 00120 inline double scalar_product(const VPoint &p1, const VPoint &p2){ 00121 return p1.x*p2.x+p1.y*p2.y; 00122 } 00123 00124 00125 /** 00126 * \if internal_doc 00127 * @ingroup internal 00128 * \class GraphEdge 00129 * handle an edge of the Voronoi Diagram. 00130 * \endif 00131 */ 00132 class GraphEdge{ 00133 public: 00134 /// coordinates of the extreme points 00135 double x1,y1,x2,y2; 00136 00137 /// indices of the parent sites that define the edge 00138 int point1, point2; 00139 00140 /// pointer to the next edge 00141 GraphEdge* next; 00142 }; 00143 00144 00145 /** 00146 * \if internal_doc 00147 * @ingroup internal 00148 * \class Site 00149 * structure used both for particle sites and for vertices. 00150 * \endif 00151 */ 00152 class Site{ 00153 public: 00154 VPoint coord; 00155 int sitenbr; 00156 int refcnt; 00157 }; 00158 00159 00160 00161 class Freenode{ 00162 public: 00163 Freenode *nextfree; 00164 }; 00165 00166 00167 class FreeNodeArrayList{ 00168 public: 00169 Freenode* memory; 00170 FreeNodeArrayList* next; 00171 }; 00172 00173 00174 class Freelist{ 00175 public: 00176 Freenode *head; 00177 int nodesize; 00178 }; 00179 00180 class Edge{ 00181 public: 00182 double a,b,c; 00183 Site *ep[2]; 00184 Site *reg[2]; 00185 int edgenbr; 00186 }; 00187 00188 00189 class Halfedge{ 00190 public: 00191 Halfedge *ELleft, *ELright; 00192 Edge *ELedge; 00193 int ELrefcnt; 00194 char ELpm; 00195 Site *vertex; 00196 volatile double ystar; 00197 Halfedge *PQnext; 00198 }; 00199 00200 /** 00201 * \if internal_doc 00202 * @ingroup internal 00203 * \class VoronoiDiagramGenerator 00204 * Shane O'Sullivan C++ version of Stephan Fortune Voronoi diagram 00205 * generator 00206 * \endif 00207 */ 00208 class VoronoiDiagramGenerator{ 00209 public: 00210 VoronoiDiagramGenerator(); 00211 ~VoronoiDiagramGenerator(); 00212 00213 bool generateVoronoi(std::vector<VPoint> *_parent_sites, 00214 double minX, double maxX, double minY, double maxY, 00215 double minDist=0); 00216 00217 inline void resetIterator(){ 00218 iteratorEdges = allEdges; 00219 } 00220 00221 bool getNext(GraphEdge **e){ 00222 if(iteratorEdges == 0) 00223 return false; 00224 00225 *e = iteratorEdges; 00226 iteratorEdges = iteratorEdges->next; 00227 return true; 00228 } 00229 00230 std::vector<VPoint> *parent_sites; 00231 int n_parent_sites; 00232 00233 private: 00234 void cleanup(); 00235 void cleanupEdges(); 00236 char *getfree(Freelist *fl); 00237 Halfedge *PQfind(); 00238 int PQempty(); 00239 00240 Halfedge **ELhash; 00241 Halfedge *HEcreate(), *ELleft(), *ELright(), *ELleftbnd(); 00242 Halfedge *HEcreate(Edge *e,int pm); 00243 00244 VPoint PQ_min(); 00245 Halfedge *PQextractmin(); 00246 void freeinit(Freelist *fl,int size); 00247 void makefree(Freenode *curr,Freelist *fl); 00248 void geominit(); 00249 void plotinit(); 00250 bool voronoi(int triangulate); 00251 void ref(Site *v); 00252 void deref(Site *v); 00253 void endpoint(Edge *e,int lr,Site * s); 00254 00255 void ELdelete(Halfedge *he); 00256 Halfedge *ELleftbnd(VPoint *p); 00257 Halfedge *ELright(Halfedge *he); 00258 void makevertex(Site *v); 00259 void out_triple(Site *s1, Site *s2,Site * s3); 00260 00261 void PQinsert(Halfedge *he,Site * v, double offset); 00262 void PQdelete(Halfedge *he); 00263 bool ELinitialize(); 00264 void ELinsert(Halfedge *lb, Halfedge *newHe); 00265 Halfedge * ELgethash(int b); 00266 Halfedge *ELleft(Halfedge *he); 00267 Site *leftreg(Halfedge *he); 00268 void out_site(Site *s); 00269 bool PQinitialize(); 00270 int PQbucket(Halfedge *he); 00271 void clip_line(Edge *e); 00272 char *myalloc(unsigned n); 00273 int right_of(Halfedge *el,VPoint *p); 00274 00275 Site *rightreg(Halfedge *he); 00276 Edge *bisect(Site *s1, Site *s2); 00277 double dist(Site *s,Site *t); 00278 Site *intersect(Halfedge *el1, Halfedge *el2, VPoint *p=0); 00279 00280 void out_bisector(Edge *e); 00281 void out_ep(Edge *e); 00282 void out_vertex(Site *v); 00283 Site *nextone(); 00284 00285 void pushGraphEdge(double x1, double y1, double x2, double y2, 00286 Site *s1, Site *s2); 00287 00288 void openpl(); 00289 void circle(double x, double y, double radius); 00290 void range(double minX, double minY, double maxX, double maxY); 00291 00292 Freelist hfl; 00293 Halfedge *ELleftend, *ELrightend; 00294 int ELhashsize; 00295 00296 int triangulate, sorted, plot, debug; 00297 double xmin, xmax, ymin, ymax, deltax, deltay; 00298 00299 Site *sites; 00300 int nsites; 00301 int siteidx; 00302 int sqrt_nsites; 00303 int nvertices; 00304 Freelist sfl; 00305 Site *bottomsite; 00306 00307 int nedges; 00308 Freelist efl; 00309 int PQhashsize; 00310 Halfedge *PQhash; 00311 int PQcount; 00312 int PQmin; 00313 00314 int ntry, totalsearch; 00315 double pxmin, pxmax, pymin, pymax, cradius; 00316 int total_alloc; 00317 00318 double borderMinX, borderMaxX, borderMinY, borderMaxY; 00319 00320 FreeNodeArrayList* allMemoryList; 00321 FreeNodeArrayList* currentMemoryBlock; 00322 00323 GraphEdge* allEdges; 00324 GraphEdge* iteratorEdges; 00325 00326 double minDistanceBetweenSites; 00327 00328 static LimitedWarning _warning_degeneracy; 00329 }; 00330 00331 int scomp(const void *p1,const void *p2); 00332 00333 00334 FASTJET_END_NAMESPACE 00335 00336 #endif