00001 #ifndef __FASTJET__VORONOI_H__
00002 #define __FASTJET__VORONOI_H__
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060 #include "fastjet/ClusterSequenceWithArea.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 using namespace std;
00071
00072 FASTJET_BEGIN_NAMESPACE
00073
00078 class Point{
00079 public:
00081 Point() : x(0.0), y(0.0) {}
00082
00084 Point(double _x, double _y) : x(_x), y(_y) {}
00085
00087 inline Point operator + (const Point &p) const{
00088 return Point(x+p.x, y+p.y);
00089 }
00090
00092 inline Point operator - (const Point &p) const{
00093 return Point(x-p.x, y-p.y);
00094 }
00095
00097 inline Point operator * (const double t) const{
00098 return Point(x*t, y*t);
00099 }
00100
00102 double x,y;
00103 };
00104
00105
00107 inline double norm(const Point p){
00108 return p.x*p.x+p.y*p.y;
00109 }
00110
00111
00113 inline double vector_product(const Point &p1, const Point &p2){
00114 return p1.x*p2.y-p1.y*p2.x;
00115 }
00116
00117
00119 inline double scalar_product(const Point &p1, const Point &p2){
00120 return p1.x*p2.x+p1.y*p2.y;
00121 }
00122
00123
00128 class GraphEdge{
00129 public:
00131 double x1,y1,x2,y2;
00132
00134 int point1, point2;
00135
00137 GraphEdge* next;
00138 };
00139
00140
00145 class Site{
00146 public:
00147 Point coord;
00148 int sitenbr;
00149 int refcnt;
00150 };
00151
00152
00153
00154 class Freenode{
00155 public:
00156 Freenode *nextfree;
00157 };
00158
00159
00160 class FreeNodeArrayList{
00161 public:
00162 Freenode* memory;
00163 FreeNodeArrayList* next;
00164 };
00165
00166
00167 class Freelist{
00168 public:
00169 Freenode *head;
00170 int nodesize;
00171 };
00172
00173 class Edge{
00174 public:
00175 double a,b,c;
00176 Site *ep[2];
00177 Site *reg[2];
00178 int edgenbr;
00179 };
00180
00181
00182 class Halfedge{
00183 public:
00184 Halfedge *ELleft, *ELright;
00185 Edge *ELedge;
00186 int ELrefcnt;
00187 char ELpm;
00188 Site *vertex;
00189 double ystar;
00190 Halfedge *PQnext;
00191 };
00192
00193
00194 class VoronoiDiagramGenerator{
00195 public:
00196 VoronoiDiagramGenerator();
00197 ~VoronoiDiagramGenerator();
00198
00199 bool generateVoronoi(vector<Point> *_parent_sites,
00200 double minX, double maxX, double minY, double maxY,
00201 double minDist=0);
00202
00203 inline void resetIterator(){
00204 iteratorEdges = allEdges;
00205 }
00206
00207 bool getNext(GraphEdge **e){
00208 if(iteratorEdges == 0)
00209 return false;
00210
00211 *e = iteratorEdges;
00212 iteratorEdges = iteratorEdges->next;
00213 return true;
00214 }
00215
00216 vector<Point> *parent_sites;
00217 int n_parent_sites;
00218
00219 private:
00220 void cleanup();
00221 void cleanupEdges();
00222 char *getfree(Freelist *fl);
00223 Halfedge *PQfind();
00224 int PQempty();
00225
00226 Halfedge **ELhash;
00227 Halfedge *HEcreate(), *ELleft(), *ELright(), *ELleftbnd();
00228 Halfedge *HEcreate(Edge *e,int pm);
00229
00230 Point PQ_min();
00231 Halfedge *PQextractmin();
00232 void freeinit(Freelist *fl,int size);
00233 void makefree(Freenode *curr,Freelist *fl);
00234 void geominit();
00235 void plotinit();
00236 bool voronoi(int triangulate);
00237 void ref(Site *v);
00238 void deref(Site *v);
00239 void endpoint(Edge *e,int lr,Site * s);
00240
00241 void ELdelete(Halfedge *he);
00242 Halfedge *ELleftbnd(Point *p);
00243 Halfedge *ELright(Halfedge *he);
00244 void makevertex(Site *v);
00245 void out_triple(Site *s1, Site *s2,Site * s3);
00246
00247 void PQinsert(Halfedge *he,Site * v, double offset);
00248 void PQdelete(Halfedge *he);
00249 bool ELinitialize();
00250 void ELinsert(Halfedge *lb, Halfedge *newHe);
00251 Halfedge * ELgethash(int b);
00252 Halfedge *ELleft(Halfedge *he);
00253 Site *leftreg(Halfedge *he);
00254 void out_site(Site *s);
00255 bool PQinitialize();
00256 int PQbucket(Halfedge *he);
00257 void clip_line(Edge *e);
00258 char *myalloc(unsigned n);
00259 int right_of(Halfedge *el,Point *p);
00260
00261 Site *rightreg(Halfedge *he);
00262 Edge *bisect(Site *s1, Site *s2);
00263 double dist(Site *s,Site *t);
00264 Site *intersect(Halfedge *el1, Halfedge *el2, Point *p=0);
00265
00266 void out_bisector(Edge *e);
00267 void out_ep(Edge *e);
00268 void out_vertex(Site *v);
00269 Site *nextone();
00270
00271 void pushGraphEdge(double x1, double y1, double x2, double y2,
00272 Site *s1, Site *s2);
00273
00274 void openpl();
00275 void circle(double x, double y, double radius);
00276 void range(double minX, double minY, double maxX, double maxY);
00277
00278 Freelist hfl;
00279 Halfedge *ELleftend, *ELrightend;
00280 int ELhashsize;
00281
00282 int triangulate, sorted, plot, debug;
00283 double xmin, xmax, ymin, ymax, deltax, deltay;
00284
00285 Site *sites;
00286 int nsites;
00287 int siteidx;
00288 int sqrt_nsites;
00289 int nvertices;
00290 Freelist sfl;
00291 Site *bottomsite;
00292
00293 int nedges;
00294 Freelist efl;
00295 int PQhashsize;
00296 Halfedge *PQhash;
00297 int PQcount;
00298 int PQmin;
00299
00300 int ntry, totalsearch;
00301 double pxmin, pxmax, pymin, pymax, cradius;
00302 int total_alloc;
00303
00304 double borderMinX, borderMaxX, borderMinY, borderMaxY;
00305
00306 FreeNodeArrayList* allMemoryList;
00307 FreeNodeArrayList* currentMemoryBlock;
00308
00309 GraphEdge* allEdges;
00310 GraphEdge* iteratorEdges;
00311
00312 double minDistanceBetweenSites;
00313 };
00314
00315 int scomp(const void *p1,const void *p2);
00316
00317
00318 FASTJET_END_NAMESPACE
00319
00320 #endif