1 #ifndef __FASTJET__VORONOI_H__
2 #define __FASTJET__VORONOI_H__
102 #include "fastjet/LimitedWarning.hh"
112 FASTJET_BEGIN_NAMESPACE
124 VPoint() : x(0.0), y(0.0) {}
127 VPoint(
double _x,
double _y) : x(_x), y(_y) {}
130 inline VPoint operator + (
const VPoint &p)
const{
131 return VPoint(x+p.x, y+p.y);
135 inline VPoint operator - (
const VPoint &p)
const{
136 return VPoint(x-p.x, y-p.y);
140 inline VPoint
operator * (
const double t)
const{
141 return VPoint(x*t, y*t);
150 inline double norm(
const VPoint p){
151 return p.x*p.x+p.y*p.y;
157 return p1.x*p2.y-p1.y*p2.x;
163 return p1.x*p2.x+p1.y*p2.y;
209 class FreeNodeArrayList{
212 FreeNodeArrayList* next;
233 Halfedge *ELleft, *ELright;
238 volatile double ystar;
250 class VoronoiDiagramGenerator{
252 VoronoiDiagramGenerator();
253 ~VoronoiDiagramGenerator();
255 bool generateVoronoi(std::vector<VPoint> *_parent_sites,
256 double minX,
double maxX,
double minY,
double maxY,
259 inline void resetIterator(){
260 iteratorEdges = allEdges;
263 bool getNext(GraphEdge **e){
264 if(iteratorEdges == 0)
268 iteratorEdges = iteratorEdges->next;
272 std::vector<VPoint> *parent_sites;
278 char *getfree(Freelist *fl);
283 Halfedge *HEcreate(), *ELleft(), *ELright(), *ELleftbnd();
284 Halfedge *HEcreate(Edge *e,
int pm);
287 Halfedge *PQextractmin();
288 void freeinit(Freelist *fl,
int size);
289 void makefree(Freenode *curr,Freelist *fl);
297 void endpoint(Edge *e,
int lr,Site * s);
299 void ELdelete(Halfedge *he);
300 Halfedge *ELleftbnd(VPoint *p);
301 Halfedge *ELright(Halfedge *he);
302 void makevertex(Site *v);
304 void PQinsert(Halfedge *he,Site * v,
double offset);
305 void PQdelete(Halfedge *he);
307 void ELinsert(Halfedge *lb, Halfedge *newHe);
308 Halfedge * ELgethash(
int b);
309 Halfedge *ELleft(Halfedge *he);
310 Site *leftreg(Halfedge *he);
312 int PQbucket(Halfedge *he);
313 void clip_line(Edge *e);
314 char *myalloc(
unsigned n);
315 int right_of(Halfedge *el,VPoint *p);
317 Site *rightreg(Halfedge *he);
318 Edge *bisect(Site *s1, Site *s2);
319 double dist(Site *s,Site *t);
323 Site *intersect(Halfedge *el1, Halfedge *el2 );
327 void pushGraphEdge(
double x1,
double y1,
double x2,
double y2,
343 Halfedge *ELleftend, *ELrightend;
347 double xmin, xmax, ymin, ymax, deltax, deltay;
364 int ntry, totalsearch;
365 double pxmin, pxmax, pymin, pymax, cradius;
368 double borderMinX, borderMaxX, borderMinY, borderMaxY;
370 FreeNodeArrayList* allMemoryList;
371 FreeNodeArrayList* currentMemoryBlock;
374 GraphEdge* iteratorEdges;
376 double minDistanceBetweenSites;
378 static LimitedWarning _warning_degeneracy;
381 int scomp(
const void *p1,
const void *p2);
384 FASTJET_END_NAMESPACE
double norm(const VPoint p)
norm of a vector
Selector operator*(const Selector &s1, const Selector &s2)
successive application of 2 selectors
double scalar_product(const VPoint &p1, const VPoint &p2)
scalar product
double vector_product(const VPoint &p1, const VPoint &p2)
2D vector product