[11] | 1 | #ifndef __FASTJET__VORONOI_H__
|
---|
| 2 | #define __FASTJET__VORONOI_H__
|
---|
| 3 |
|
---|
| 4 | //STARTHEADER
|
---|
| 5 | // $Id: Voronoi.hh,v 1.1 2008-11-06 14:32:09 ovyn Exp $
|
---|
| 6 | //
|
---|
| 7 | // Copyright (c) 1994 by AT&T Bell Laboratories (see below)
|
---|
| 8 | //
|
---|
| 9 | //
|
---|
| 10 | //----------------------------------------------------------------------
|
---|
| 11 | // This file is included as part of FastJet but was mostly written by
|
---|
| 12 | // S. Fortune in C, put into C++ with memory management by S
|
---|
| 13 | // O'Sullivan, and with further interface and memeory management
|
---|
| 14 | // modifications by Gregory Soyez.
|
---|
| 15 | //
|
---|
| 16 | // Permission to use, copy, modify, and distribute this software for
|
---|
| 17 | // any purpose without fee is hereby granted, provided that this
|
---|
| 18 | // entire notice is included in all copies of any software which is or
|
---|
| 19 | // includes a copy or modification of this software and in all copies
|
---|
| 20 | // of the supporting documentation for such software. THIS SOFTWARE IS
|
---|
| 21 | // BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED WARRANTY.
|
---|
| 22 | // IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY REPRESENTATION
|
---|
| 23 | // OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS
|
---|
| 24 | // SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
|
---|
| 25 | //
|
---|
| 26 | //----------------------------------------------------------------------
|
---|
| 27 | //ENDHEADER
|
---|
| 28 |
|
---|
| 29 |
|
---|
| 30 | /*
|
---|
| 31 | * The author of this software is Steven Fortune.
|
---|
| 32 | * Copyright (c) 1994 by AT&T Bell Laboratories.
|
---|
| 33 | * Permission to use, copy, modify, and distribute this software for any
|
---|
| 34 | * purpose without fee is hereby granted, provided that this entire notice
|
---|
| 35 | * is included in all copies of any software which is or includes a copy
|
---|
| 36 | * or modification of this software and in all copies of the supporting
|
---|
| 37 | * documentation for such software.
|
---|
| 38 | * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
|
---|
| 39 | * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
|
---|
| 40 | * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
|
---|
| 41 | * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
|
---|
| 42 | */
|
---|
| 43 |
|
---|
| 44 | /*
|
---|
| 45 | * This code was originally written by Stephan Fortune in C code. I,
|
---|
| 46 | * Shane O'Sullivan, have since modified it, encapsulating it in a C++
|
---|
| 47 | * class and, fixing memory leaks and adding accessors to the Voronoi
|
---|
| 48 | * Edges. Permission to use, copy, modify, and distribute this
|
---|
| 49 | * software for any purpose without fee is hereby granted, provided
|
---|
| 50 | * that this entire notice is included in all copies of any software
|
---|
| 51 | * which is or includes a copy or modification of this software and in
|
---|
| 52 | * all copies of the supporting documentation for such software. THIS
|
---|
| 53 | * SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
|
---|
| 54 | * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
|
---|
| 55 | * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE
|
---|
| 56 | * MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR
|
---|
| 57 | * PURPOSE.
|
---|
| 58 | */
|
---|
| 59 |
|
---|
| 60 | #include "Utilities/Fastjet/include/fastjet/ClusterSequenceWithArea.hh"
|
---|
| 61 | #include <vector>
|
---|
| 62 | #include <math.h>
|
---|
| 63 | #include <stdlib.h>
|
---|
| 64 | #include <string.h>
|
---|
| 65 |
|
---|
| 66 | #define DELETED -2
|
---|
| 67 | #define le 0
|
---|
| 68 | #define re 1
|
---|
| 69 |
|
---|
| 70 | //using namespace std;
|
---|
| 71 |
|
---|
| 72 | FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh
|
---|
| 73 |
|
---|
| 74 | /**
|
---|
| 75 | * \class Point
|
---|
| 76 | * class to handle a 2d point
|
---|
| 77 | */
|
---|
| 78 | class Point{
|
---|
| 79 | public:
|
---|
| 80 | /// defailt ctor
|
---|
| 81 | Point() : x(0.0), y(0.0) {}
|
---|
| 82 |
|
---|
| 83 | /// ctor with initialisation
|
---|
| 84 | Point(double _x, double _y) : x(_x), y(_y) {}
|
---|
| 85 |
|
---|
| 86 | /// addition
|
---|
| 87 | inline Point operator + (const Point &p) const{
|
---|
| 88 | return Point(x+p.x, y+p.y);
|
---|
| 89 | }
|
---|
| 90 |
|
---|
| 91 | /// subtraction
|
---|
| 92 | inline Point operator - (const Point &p) const{
|
---|
| 93 | return Point(x-p.x, y-p.y);
|
---|
| 94 | }
|
---|
| 95 |
|
---|
| 96 | /// scalar multiplication
|
---|
| 97 | inline Point operator * (const double t) const{
|
---|
| 98 | return Point(x*t, y*t);
|
---|
| 99 | }
|
---|
| 100 |
|
---|
| 101 | /// vector coordinates
|
---|
| 102 | double x,y;
|
---|
| 103 | };
|
---|
| 104 |
|
---|
| 105 |
|
---|
| 106 | /// norm of a vector
|
---|
| 107 | inline double norm(const Point p){
|
---|
| 108 | return p.x*p.x+p.y*p.y;
|
---|
| 109 | }
|
---|
| 110 |
|
---|
| 111 |
|
---|
| 112 | /// 2D vector product
|
---|
| 113 | inline double vector_product(const Point &p1, const Point &p2){
|
---|
| 114 | return p1.x*p2.y-p1.y*p2.x;
|
---|
| 115 | }
|
---|
| 116 |
|
---|
| 117 |
|
---|
| 118 | /// scalar product
|
---|
| 119 | inline double scalar_product(const Point &p1, const Point &p2){
|
---|
| 120 | return p1.x*p2.x+p1.y*p2.y;
|
---|
| 121 | }
|
---|
| 122 |
|
---|
| 123 |
|
---|
| 124 | /**
|
---|
| 125 | * \class GraphEdge
|
---|
| 126 | * handle an edge of the Voronoi Diagram.
|
---|
| 127 | */
|
---|
| 128 | class GraphEdge{
|
---|
| 129 | public:
|
---|
| 130 | /// coordinates of the extreme points
|
---|
| 131 | double x1,y1,x2,y2;
|
---|
| 132 |
|
---|
| 133 | /// indices of the parent sites that define the edge
|
---|
| 134 | int point1, point2;
|
---|
| 135 |
|
---|
| 136 | /// pointer to the next edge
|
---|
| 137 | GraphEdge* next;
|
---|
| 138 | };
|
---|
| 139 |
|
---|
| 140 |
|
---|
| 141 | /**
|
---|
| 142 | * \class Site
|
---|
| 143 | * structure used both for particle sites and for vertices.
|
---|
| 144 | */
|
---|
| 145 | class Site{
|
---|
| 146 | public:
|
---|
| 147 | Point coord;
|
---|
| 148 | int sitenbr;
|
---|
| 149 | int refcnt;
|
---|
| 150 | };
|
---|
| 151 |
|
---|
| 152 |
|
---|
| 153 |
|
---|
| 154 | class Freenode{
|
---|
| 155 | public:
|
---|
| 156 | Freenode *nextfree;
|
---|
| 157 | };
|
---|
| 158 |
|
---|
| 159 |
|
---|
| 160 | class FreeNodeArrayList{
|
---|
| 161 | public:
|
---|
| 162 | Freenode* memory;
|
---|
| 163 | FreeNodeArrayList* next;
|
---|
| 164 | };
|
---|
| 165 |
|
---|
| 166 |
|
---|
| 167 | class Freelist{
|
---|
| 168 | public:
|
---|
| 169 | Freenode *head;
|
---|
| 170 | int nodesize;
|
---|
| 171 | };
|
---|
| 172 |
|
---|
| 173 | class Edge{
|
---|
| 174 | public:
|
---|
| 175 | double a,b,c;
|
---|
| 176 | Site *ep[2];
|
---|
| 177 | Site *reg[2];
|
---|
| 178 | int edgenbr;
|
---|
| 179 | };
|
---|
| 180 |
|
---|
| 181 |
|
---|
| 182 | class Halfedge{
|
---|
| 183 | public:
|
---|
| 184 | Halfedge *ELleft, *ELright;
|
---|
| 185 | Edge *ELedge;
|
---|
| 186 | int ELrefcnt;
|
---|
| 187 | char ELpm;
|
---|
| 188 | Site *vertex;
|
---|
| 189 | volatile double ystar;
|
---|
| 190 | Halfedge *PQnext;
|
---|
| 191 | };
|
---|
| 192 |
|
---|
| 193 |
|
---|
| 194 | class VoronoiDiagramGenerator{
|
---|
| 195 | public:
|
---|
| 196 | VoronoiDiagramGenerator();
|
---|
| 197 | ~VoronoiDiagramGenerator();
|
---|
| 198 |
|
---|
| 199 | bool generateVoronoi(std::vector<Point> *_parent_sites,
|
---|
| 200 | double minX, double maxX, double minY, double maxY,
|
---|
| 201 | double minDist=0);
|
---|
| 202 |
|
---|
| 203 | inline void resetIterator(){
|
---|
| 204 | iteratorEdges = allEdges;
|
---|
| 205 | }
|
---|
| 206 |
|
---|
| 207 | bool getNext(GraphEdge **e){
|
---|
| 208 | if(iteratorEdges == 0)
|
---|
| 209 | return false;
|
---|
| 210 |
|
---|
| 211 | *e = iteratorEdges;
|
---|
| 212 | iteratorEdges = iteratorEdges->next;
|
---|
| 213 | return true;
|
---|
| 214 | }
|
---|
| 215 |
|
---|
| 216 | std::vector<Point> *parent_sites;
|
---|
| 217 | int n_parent_sites;
|
---|
| 218 |
|
---|
| 219 | private:
|
---|
| 220 | void cleanup();
|
---|
| 221 | void cleanupEdges();
|
---|
| 222 | char *getfree(Freelist *fl);
|
---|
| 223 | Halfedge *PQfind();
|
---|
| 224 | int PQempty();
|
---|
| 225 |
|
---|
| 226 | Halfedge **ELhash;
|
---|
| 227 | Halfedge *HEcreate(), *ELleft(), *ELright(), *ELleftbnd();
|
---|
| 228 | Halfedge *HEcreate(Edge *e,int pm);
|
---|
| 229 |
|
---|
| 230 | Point PQ_min();
|
---|
| 231 | Halfedge *PQextractmin();
|
---|
| 232 | void freeinit(Freelist *fl,int size);
|
---|
| 233 | void makefree(Freenode *curr,Freelist *fl);
|
---|
| 234 | void geominit();
|
---|
| 235 | void plotinit();
|
---|
| 236 | bool voronoi(int triangulate);
|
---|
| 237 | void ref(Site *v);
|
---|
| 238 | void deref(Site *v);
|
---|
| 239 | void endpoint(Edge *e,int lr,Site * s);
|
---|
| 240 |
|
---|
| 241 | void ELdelete(Halfedge *he);
|
---|
| 242 | Halfedge *ELleftbnd(Point *p);
|
---|
| 243 | Halfedge *ELright(Halfedge *he);
|
---|
| 244 | void makevertex(Site *v);
|
---|
| 245 | void out_triple(Site *s1, Site *s2,Site * s3);
|
---|
| 246 |
|
---|
| 247 | void PQinsert(Halfedge *he,Site * v, double offset);
|
---|
| 248 | void PQdelete(Halfedge *he);
|
---|
| 249 | bool ELinitialize();
|
---|
| 250 | void ELinsert(Halfedge *lb, Halfedge *newHe);
|
---|
| 251 | Halfedge * ELgethash(int b);
|
---|
| 252 | Halfedge *ELleft(Halfedge *he);
|
---|
| 253 | Site *leftreg(Halfedge *he);
|
---|
| 254 | void out_site(Site *s);
|
---|
| 255 | bool PQinitialize();
|
---|
| 256 | int PQbucket(Halfedge *he);
|
---|
| 257 | void clip_line(Edge *e);
|
---|
| 258 | char *myalloc(unsigned n);
|
---|
| 259 | int right_of(Halfedge *el,Point *p);
|
---|
| 260 |
|
---|
| 261 | Site *rightreg(Halfedge *he);
|
---|
| 262 | Edge *bisect(Site *s1, Site *s2);
|
---|
| 263 | double dist(Site *s,Site *t);
|
---|
| 264 | Site *intersect(Halfedge *el1, Halfedge *el2, Point *p=0);
|
---|
| 265 |
|
---|
| 266 | void out_bisector(Edge *e);
|
---|
| 267 | void out_ep(Edge *e);
|
---|
| 268 | void out_vertex(Site *v);
|
---|
| 269 | Site *nextone();
|
---|
| 270 |
|
---|
| 271 | void pushGraphEdge(double x1, double y1, double x2, double y2,
|
---|
| 272 | Site *s1, Site *s2);
|
---|
| 273 |
|
---|
| 274 | void openpl();
|
---|
| 275 | void circle(double x, double y, double radius);
|
---|
| 276 | void range(double minX, double minY, double maxX, double maxY);
|
---|
| 277 |
|
---|
| 278 | Freelist hfl;
|
---|
| 279 | Halfedge *ELleftend, *ELrightend;
|
---|
| 280 | int ELhashsize;
|
---|
| 281 |
|
---|
| 282 | int triangulate, sorted, plot, debug;
|
---|
| 283 | double xmin, xmax, ymin, ymax, deltax, deltay;
|
---|
| 284 |
|
---|
| 285 | Site *sites;
|
---|
| 286 | int nsites;
|
---|
| 287 | int siteidx;
|
---|
| 288 | int sqrt_nsites;
|
---|
| 289 | int nvertices;
|
---|
| 290 | Freelist sfl;
|
---|
| 291 | Site *bottomsite;
|
---|
| 292 |
|
---|
| 293 | int nedges;
|
---|
| 294 | Freelist efl;
|
---|
| 295 | int PQhashsize;
|
---|
| 296 | Halfedge *PQhash;
|
---|
| 297 | int PQcount;
|
---|
| 298 | int PQmin;
|
---|
| 299 |
|
---|
| 300 | int ntry, totalsearch;
|
---|
| 301 | double pxmin, pxmax, pymin, pymax, cradius;
|
---|
| 302 | int total_alloc;
|
---|
| 303 |
|
---|
| 304 | double borderMinX, borderMaxX, borderMinY, borderMaxY;
|
---|
| 305 |
|
---|
| 306 | FreeNodeArrayList* allMemoryList;
|
---|
| 307 | FreeNodeArrayList* currentMemoryBlock;
|
---|
| 308 |
|
---|
| 309 | GraphEdge* allEdges;
|
---|
| 310 | GraphEdge* iteratorEdges;
|
---|
| 311 |
|
---|
| 312 | double minDistanceBetweenSites;
|
---|
| 313 | };
|
---|
| 314 |
|
---|
| 315 | int scomp(const void *p1,const void *p2);
|
---|
| 316 |
|
---|
| 317 |
|
---|
| 318 | FASTJET_END_NAMESPACE
|
---|
| 319 |
|
---|
| 320 | #endif
|
---|