1 /*****************************************************************************
4 Author: Christian Mayer
7 -------- Copyright (C) 1999 Christian Mayer (fgfs@christianmayer.de) --------
9 This program is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free Software
11 Foundation; either version 2 of the License, or (at your option) any later
14 This program is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
16 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
19 You should have received a copy of the GNU General Public License along with
20 this program; if not, write to the Free Software Foundation, Inc., 59 Temple
21 Place - Suite 330, Boston, MA 02111-1307, USA.
23 Further information about the GNU General Public License can also be found on
24 the world wide web at http://www.gnu.org.
26 FUNCTIONAL DESCRIPTION
27 ------------------------------------------------------------------------------
28 library for Voronoi Diagram calculation based on Steven Fortune 'Sweep2'
29 FGVoronoi is the wraper to feed the voronoi calulation with a vetor of points
30 and any class you want, as it uses templates
31 NOTE: Sweep2 didn't free *any* memory. So I'm doing what I can, but that's not
35 ------------------------------------------------------------------------------
36 30.05.99 Christian Mayer Created
37 16.06.99 Durk Talsma Portability for Linux
38 11.10.1999 Christian Mayer changed set<> to map<> on Bernie Bright's
40 19.10.1999 Christian Mayer change to use PLIB's sg instead of Point[2/3]D
41 and lots of wee code cleaning
42 *****************************************************************************/
44 /****************************************************************************/
46 /****************************************************************************/
47 #include "FGVoronoi.h"
48 #include <Voronoi/voronoi.h>
49 #include <Voronoi/my_memory.h>
51 #include <Voronoi/defs.h>
55 void voronoi(int triangulate, struct Site *(*nextsite)());
57 void freeinit(struct Freelist *fl, int size);
58 struct Site *nextone();
59 bool readsites(PointList input);
62 /****************************************************************************/
63 /********************************** CODE ************************************/
64 /****************************************************************************/
65 FGVoronoiOutputList Voronoiate(const FGVoronoiInputList& input)
67 FGVoronoiOutputList ret_list;
71 FGVoronoiInputList::const_iterator it1;
74 for (it1 = input.begin(); it1 != input.end(); it1++)
76 p2ds.push_back(VoronoiPoint(it1->position[0], it1->position[1]));
79 cl.clear(); //make sure that it's empty
81 if (readsites(p2ds) == false)
84 freeinit(&sfl, sizeof *sites);
87 voronoi(triangulate, nextone);
90 /*free(sites); //to prevent a *big* memory leak...
91 free(ELhash); //Sweep2 didn't free *any* memory...
94 for (cellList::iterator it2 = cl.begin(); it2 != cl.end(); it2++)
99 //uncomment for debugging
102 Point2DList boundary;
105 PointList::iterator it3 = it2->boundary.begin();
107 if (it3->infinity == false)
108 boundary.push_back( sgVec2Wrap(it3->p) );
111 sgVec2 direction_vector;
112 sgCopyVec2(direction_vector, it3->p);
115 sgAddVec2(direction_vector, it3->p);
117 boundary.push_back( direction_vector );
120 for (; it3 != it2->boundary.end(); it3++)
122 boundary.push_back( sgVec2Wrap(it3->p) );
127 if (it3->infinity == true)
129 sgVec2 direction_vector;
130 sgCopyVec2(direction_vector, it3->p);
133 sgAddVec2(direction_vector, it3->p);
136 boundary.push_back(direction_vector);
139 ret_list.push_back(FGVoronoiOutput(boundary, input[it2->ID].value));
150 /* return a single in-storage site */
151 struct Site *nextone(void)
161 return( (struct Site *)NULL);
165 /* sort sites on y, then x, coord */
166 //int scomp(const struct Point *s1, const struct Point *s2)
167 int scomp(const void *s1, const void *s2)
169 if(((Point*)s1) -> y < ((Point*)s2) -> y) return(-1);
170 if(((Point*)s1) -> y > ((Point*)s2) -> y) return(1);
171 if(((Point*)s1) -> x < ((Point*)s2) -> x) return(-1);
172 if(((Point*)s1) -> x > ((Point*)s2) -> x) return(1);
178 /* read all sites, sort, and compute xmin, xmax, ymin, ymax */
179 bool readsites(PointList input)
183 if (input.size() == 0)
184 return false; //empty array
186 PointList::iterator It = input.begin();
189 sites = (struct Site *) myalloc(4000*sizeof(*sites));
191 while(It != input.end())
193 sites[nsites].coord.x = It->p[0];
194 sites[nsites].coord.y = It->p[1];
196 sites[nsites].sitenbr = nsites;
197 sites[nsites].refcnt = 0;
201 if (nsites % 4000 == 0)
202 sites = (struct Site *) my_realloc(sites,(nsites+4000)*sizeof(*sites));
205 qsort(sites, nsites, sizeof (*sites), scomp);
206 xmin=sites[0].coord.x;
207 xmax=sites[0].coord.x;
209 for(i=1; i<nsites; i+=1)
211 if(sites[i].coord.x < xmin)
212 xmin = sites[i].coord.x;
213 if(sites[i].coord.x > xmax)
214 xmax = sites[i].coord.x;
217 ymin = sites[0].coord.y;
218 ymax = sites[nsites-1].coord.y;