Voronoi.hh

Go to the documentation of this file.
00001 #ifndef __FASTJET__VORONOI_H__
00002 #define __FASTJET__VORONOI_H__
00003 
00004 //STARTHEADER
00005 // $Id: Voronoi.hh 621 2007-05-09 10:34:30Z 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/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      // defined in fastjet/internal/base.hh
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

Generated on Tue Dec 18 17:05:02 2007 for fastjet by  doxygen 1.5.2