nominatim/voronoi/VoronoiDiagramGenerator.h

   1 /*\r
   2 * The author of this software is Steven Fortune.  Copyright (c) 1994 by AT&T\r
   3 * Bell Laboratories.\r
   4 * Permission to use, copy, modify, and distribute this software for any\r
   5 * purpose without fee is hereby granted, provided that this entire notice\r
   6 * is included in all copies of any software which is or includes a copy\r
   7 * or modification of this software and in all copies of the supporting\r
   8 * documentation for such software.\r
   9 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED\r
  10 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY\r
  11 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY\r
  12 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.\r
  13 */\r
  14 \r
  15 /* \r
  16 * This code was originally written by Stephan Fortune in C code.  I, Shane O'Sullivan, \r
  17 * have since modified it, encapsulating it in a C++ class and, fixing memory leaks and \r
  18 * adding accessors to the Voronoi Edges.\r
  19 * Permission to use, copy, modify, and distribute this software for any\r
  20 * purpose without fee is hereby granted, provided that this entire notice\r
  21 * is included in all copies of any software which is or includes a copy\r
  22 * or modification of this software and in all copies of the supporting\r
  23 * documentation for such software.\r
  24 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED\r
  25 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY\r
  26 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY\r
  27 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.\r
  28 */\r
  29 \r
  30 #ifndef VORONOI_DIAGRAM_GENERATOR\r
  31 #define VORONOI_DIAGRAM_GENERATOR\r
  32 \r
  33 #include <math.h>\r
  34 #include <stdlib.h>\r
  35 #include <string.h>\r
  36 \r
  37 \r
  38 #ifndef NULL\r
  39 #define NULL 0\r
  40 #endif\r
  41 #define DELETED -2\r
  42 \r
  43 #define le 0\r
  44 #define re 1\r
  45 \r
  46 struct SourcePoint\r
  47 {\r
  48         int id;\r
  49         double weight;\r
  50         double x;\r
  51         double y;\r
  52 };\r
  53 \r
  54 struct  Freenode        \r
  55 {\r
  56         struct  Freenode *nextfree;\r
  57 };\r
  58 \r
  59 struct FreeNodeArrayList\r
  60 {\r
  61         struct  Freenode* memory;\r
  62         struct  FreeNodeArrayList* next;\r
  63 \r
  64 };\r
  65 \r
  66 struct  Freelist        \r
  67 {\r
  68         struct  Freenode        *head;\r
  69         int             nodesize;\r
  70 };\r
  71 \r
  72 struct Point    \r
  73 {\r
  74         float x,y;\r
  75 };\r
  76 \r
  77 struct PolygonPoint\r
  78 {\r
  79         struct  Point   coord;\r
  80         double          angle;\r
  81         int     boundary;\r
  82 };\r
  83 \r
  84 struct Polygon\r
  85 {\r
  86         int             sitenbr;\r
  87         struct  Point   coord;\r
  88         int             numpoints;\r
  89         struct PolygonPoint * pointlist;\r
  90         int             boundary;\r
  91 };\r
  92 \r
  93 \r
  94 // structure used both for sites and for vertices \r
  95 struct Site     \r
  96 {\r
  97         struct  Point   coord;\r
  98         struct  Point   coordout;\r
  99         double          weight;\r
 100         int             sitenbr;\r
 101         int             refcnt;\r
 102 };\r
 103 \r
 104 \r
 105 \r
 106 struct Edge     \r
 107 {\r
 108         float   a,b,c;\r
 109         struct  Site    *ep[2];\r
 110         struct  Site    *reg[2];\r
 111         int             edgenbr;\r
 112 \r
 113 };\r
 114 \r
 115 struct GraphEdge\r
 116 {\r
 117         float x1,y1,x2,y2;\r
 118         struct GraphEdge* next;\r
 119 };\r
 120 \r
 121 \r
 122 \r
 123 \r
 124 struct Halfedge \r
 125 {\r
 126         struct  Halfedge        *ELleft, *ELright;\r
 127         struct  Edge    *ELedge;\r
 128         int             ELrefcnt;\r
 129         char    ELpm;\r
 130         struct  Site    *vertex;\r
 131         float   ystar;\r
 132         struct  Halfedge *PQnext;\r
 133 };\r
 134 \r
 135 \r
 136 \r
 137 \r
 138 class VoronoiDiagramGenerator\r
 139 {\r
 140 public:\r
 141         VoronoiDiagramGenerator();\r
 142         ~VoronoiDiagramGenerator();\r
 143 \r
 144         bool generateVoronoi(struct SourcePoint* srcPoints, int numPoints, float minX, float maxX, float minY, float maxY, float minDist=0);\r
 145         void getSitePoints(int sitenbr, int* numpoints, PolygonPoint** pS);\r
 146 \r
 147         void resetIterator()\r
 148         {\r
 149                 iteratorEdges = allEdges;\r
 150         }\r
 151 \r
 152         bool getNext(float& x1, float& y1, float& x2, float& y2)\r
 153         {\r
 154                 if(iteratorEdges == 0)\r
 155                         return false;\r
 156                 \r
 157                 x1 = iteratorEdges->x1;\r
 158                 x2 = iteratorEdges->x2;\r
 159                 y1 = iteratorEdges->y1;\r
 160                 y2 = iteratorEdges->y2;\r
 161 \r
 162                 iteratorEdges = iteratorEdges->next;\r
 163 \r
 164                 return true;\r
 165         }\r
 166 \r
 167 \r
 168 private:\r
 169         void cleanup();\r
 170         void cleanupEdges();\r
 171         char *getfree(struct Freelist *fl);     \r
 172         struct Halfedge *PQfind();\r
 173         int PQempty();\r
 174 \r
 175 \r
 176         \r
 177         struct  Halfedge **ELhash;\r
 178         struct  Halfedge *HEcreate(), *ELleft(), *ELright(), *ELleftbnd();\r
 179         struct  Halfedge *HEcreate(struct Edge *e,int pm);\r
 180 \r
 181 \r
 182         struct Point PQ_min();\r
 183         struct Halfedge *PQextractmin();        \r
 184         void freeinit(struct Freelist *fl,int size);\r
 185         void makefree(struct Freenode *curr,struct Freelist *fl);\r
 186         void geominit();\r
 187         void plotinit();\r
 188         bool voronoi(int triangulate);\r
 189         void ref(struct Site *v);\r
 190         void deref(struct Site *v);\r
 191         void endpoint(struct Edge *e,int lr,struct Site * s);\r
 192         void endpoint(struct Edge *e1,int lr,struct Site * s, struct Edge *e2, struct Edge *e3);\r
 193 \r
 194         void ELdelete(struct Halfedge *he);\r
 195         struct Halfedge *ELleftbnd(struct Point *p);\r
 196         struct Halfedge *ELright(struct Halfedge *he);\r
 197         void makevertex(struct Site *v);\r
 198         void out_triple(struct Site *s1, struct Site *s2,struct Site * s3);\r
 199 \r
 200         void PQinsert(struct Halfedge *he,struct Site * v, float offset);\r
 201         void PQdelete(struct Halfedge *he);\r
 202         bool ELinitialize();\r
 203         void ELinsert(struct    Halfedge *lb, struct Halfedge *newHe);\r
 204         struct Halfedge * ELgethash(int b);\r
 205         struct Halfedge *ELleft(struct Halfedge *he);\r
 206         struct Site *leftreg(struct Halfedge *he);\r
 207         void out_site(struct Site *s);\r
 208         bool PQinitialize();\r
 209         int PQbucket(struct Halfedge *he);\r
 210         void pushpoint(int sitenbr, double x, double y, int boundary);\r
 211         int ccw( Point p0, Point p1, Point p2 );\r
 212         void clip_line(struct Edge *e);\r
 213         char *myalloc(unsigned n);\r
 214         int right_of(struct Halfedge *el,struct Point *p);\r
 215 \r
 216         struct Site *rightreg(struct Halfedge *he);\r
 217         struct Edge *bisect(struct      Site *s1,struct Site *s2);\r
 218         float dist(struct Site *s,struct Site *t);\r
 219         struct Site *intersect(struct Halfedge *el1, struct Halfedge *el2, struct Point *p=0);\r
 220 \r
 221         void out_bisector(struct Edge *e);\r
 222         void out_ep(struct Edge *e);\r
 223         void out_vertex(struct Site *v);\r
 224         struct Site *nextone();\r
 225 \r
 226         void pushGraphEdge(float x1, float y1, float x2, float y2);\r
 227 \r
 228         void openpl();\r
 229         void line(float x1, float y1, float x2, float y2);\r
 230         void circle(float x, float y, float radius);\r
 231         void range(float minX, float minY, float maxX, float maxY);\r
 232 \r
 233 \r
 234         struct  Freelist        hfl;\r
 235         struct  Halfedge *ELleftend, *ELrightend;\r
 236         int     ELhashsize;\r
 237 \r
 238         int             triangulate, sorted, plot, debug;\r
 239         float   xmin, xmax, ymin, ymax, deltax, deltay;\r
 240 \r
 241         struct  Site    *sites;\r
 242         struct Polygon *polygons;\r
 243         struct Point    corners[4];\r
 244         int             nsites;\r
 245         int             siteidx;\r
 246         int             sqrt_nsites;\r
 247         int             nvertices;\r
 248         struct  Freelist sfl;\r
 249         struct  Site    *bottomsite;\r
 250 \r
 251         int             nedges;\r
 252         struct  Freelist efl;\r
 253         int             PQhashsize;\r
 254         struct  Halfedge *PQhash;\r
 255         int             PQcount;\r
 256         int             PQmin;\r
 257 \r
 258         int             ntry, totalsearch;\r
 259         float   pxmin, pxmax, pymin, pymax, cradius;\r
 260         int             total_alloc;\r
 261 \r
 262         float borderMinX, borderMaxX, borderMinY, borderMaxY;\r
 263 \r
 264         FreeNodeArrayList* allMemoryList;\r
 265         FreeNodeArrayList* currentMemoryBlock;\r
 266 \r
 267         GraphEdge* allEdges;\r
 268         GraphEdge* iteratorEdges;\r
 269 \r
 270         float minDistanceBetweenSites;\r
 271         \r
 272 };\r
 273 \r
 274 int scomp(const void *p1,const void *p2);\r
 275 int spcomp(const void *p1,const void *p2);\r
 276 int anglecomp(const void * p1, const void * p2);\r
 277 \r
 278 \r
 279 #endif\r
 280 \r
 281 \r