← Back to branch summary

~ubuntu-branches/ubuntu/raring/python-scipy/raring-proposed

« back to all changes in this revision

Viewing changes to Lib/sandbox/delaunay/VoronoiDiagramGenerator.h

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2007-01-07 14:12:12 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20070107141212-mm0ebkh5b37hcpzn
http://bugs.debian.org/402783
* Remove build dependency on python-numpy-dev.
* python-scipy: Depend on python-numpy instead of python-numpy-dev.
* Package builds on other archs than i386. Closes: #402783.

Show diffs side-by-side

added added

removed removed

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