1 /*****************************************************************************
4 Author: Christian Mayer
6 Called by: main program
8 ---------- Copyright (C) 1999 Christian Mayer (vader@t-online.de) ----------
10 This program is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free Software
12 Foundation; either version 2 of the License, or (at your option) any later
15 This program is distributed in the hope that it will be useful, but WITHOUT
16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
20 You should have received a copy of the GNU General Public License along with
21 this program; if not, write to the Free Software Foundation, Inc., 59 Temple
22 Place - Suite 330, Boston, MA 02111-1307, USA.
24 Further information about the GNU General Public License can also be found on
25 the world wide web at http://www.gnu.org.
27 FUNCTIONAL DESCRIPTION
28 ------------------------------------------------------------------------------
29 library for Voronoi Diagram calculation based on Steven Fortune 'Sweep2'
30 FGVoronoi is the wraper to feed the voronoi calulation with a vetor of points
31 and any class you want, as it uses templates
32 NOTE: Sweep2 didn't free *any* memory. So I'm doing what I can, but that's not
36 ------------------------------------------------------------------------------
37 30.05.99 Christian Mayer Created
38 16.06.99 Durk Talsma Portability for Linux
39 *****************************************************************************/
41 /****************************************************************************/
43 /****************************************************************************/
44 #include "FGVoronoi.h"
45 #include <Voronoi/voronoi.h>
46 #include <Voronoi/my_memory.h>
49 #include <Voronoi/defs.h>
52 void voronoi(int triangulate, struct Site *(*nextsite)());
54 void freeinit(struct Freelist *fl, int size);
55 struct Site *nextone(void);
56 bool readsites(PointList input);
59 /****************************************************************************/
60 /********************************** CODE ************************************/
61 /****************************************************************************/
62 FGVoronoiOutputList Voronoiate(const FGVoronoiInputList& input)
64 FGVoronoiOutputList ret_list;
68 FGVoronoiInputList::iterator it1;
71 for (it1 = (FGVoronoiInputList::iterator)input.begin(); it1 != input.end(); it1++)
73 p2ds.push_back(VoronoiPoint(it1->position.x(), it1->position.y()));
76 cl.clear(); //make sure that it's empty
78 if (readsites(p2ds) == false)
81 freeinit(&sfl, sizeof *sites);
84 voronoi(triangulate, nextone);
87 /*free(sites); //to prevent a *big* memory leak...
88 free(ELhash); //Sweep2 didn't free *any* memory...
91 for (cellList::iterator it2 = cl.begin(); it2 != cl.end(); it2++)
96 //uncomment for debugging
102 PointList::iterator it3 = it2->boundary.begin();
104 if (it3->infinity == false)
105 boundary.push_back( *it3 );
108 Point2D direction_vector = *it3;
110 boundary.push_back( (*it3) + direction_vector);
113 for (; it3 != it2->boundary.end(); it3++)
115 boundary.push_back( *it3 );
120 if (it3->infinity == true)
122 Point2D direction_vector = *it3;
124 Point2D value = *it3;
126 boundary.push_back(value + direction_vector);
129 ret_list.push_back(FGVoronoiOutput(boundary, input[it2->ID].value));
140 /* return a single in-storage site */
141 struct Site *nextone(void)
151 return( (struct Site *)NULL);
155 /* sort sites on y, then x, coord */
156 //int scomp(const struct Point *s1, const struct Point *s2)
157 int scomp(const void *s1, const void *s2)
159 if(((Point*)s1) -> y < ((Point*)s2) -> y) return(-1);
160 if(((Point*)s1) -> y > ((Point*)s2) -> y) return(1);
161 if(((Point*)s1) -> x < ((Point*)s2) -> x) return(-1);
162 if(((Point*)s1) -> x > ((Point*)s2) -> x) return(1);
168 /* read all sites, sort, and compute xmin, xmax, ymin, ymax */
169 bool readsites(PointList input)
173 if (input.size() == 0)
174 return false; //empty array
176 PointList::iterator It = input.begin();
179 sites = (struct Site *) myalloc(4000*sizeof(*sites));
181 while(It != input.end())
183 sites[nsites].coord.x = It->x();
184 sites[nsites].coord.y = It->y();
186 sites[nsites].sitenbr = nsites;
187 sites[nsites].refcnt = 0;
191 if (nsites % 4000 == 0)
192 sites = (struct Site *) my_realloc(sites,(nsites+4000)*sizeof(*sites));
195 qsort(sites, nsites, sizeof (*sites), scomp);
196 xmin=sites[0].coord.x;
197 xmax=sites[0].coord.x;
199 for(i=1; i<nsites; i+=1)
201 if(sites[i].coord.x < xmin)
202 xmin = sites[i].coord.x;
203 if(sites[i].coord.x > xmax)
204 xmax = sites[i].coord.x;
207 ymin = sites[0].coord.y;
208 ymax = sites[nsites-1].coord.y;