QGIS API Documentation  2.8.2-Wien
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
util.cpp
Go to the documentation of this file.
1 /*
2  * libpal - Automated Placement of Labels Library
3  *
4  * Copyright (C) 2008 Maxence Laurent, MIS-TIC, HEIG-VD
5  * University of Applied Sciences, Western Switzerland
6  * http://www.hes-so.ch
7  *
8  * Contact:
9  * maxence.laurent <at> heig-vd <dot> ch
10  * or
11  * eric.taillard <at> heig-vd <dot> ch
12  *
13  * This file is part of libpal.
14  *
15  * libpal is free software: you can redistribute it and/or modify
16  * it under the terms of the GNU General Public License as published by
17  * the Free Software Foundation, either version 3 of the License, or
18  * (at your option) any later version.
19  *
20  * libpal is distributed in the hope that it will be useful,
21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23  * GNU General Public License for more details.
24  *
25  * You should have received a copy of the GNU General Public License
26  * along with libpal. If not, see <http://www.gnu.org/licenses/>.
27  *
28  */
29 
30 #ifdef HAVE_CONFIG_H
31 #include <config.h>
32 #endif
33 
34 #include <stddef.h>
35 #include <geos_c.h>
36 
37 #include <sstream>
38 
39 #include <iostream>
40 #include <cfloat>
41 //#include <cfloat>
42 #include <cstdarg>
43 #include <ctime>
44 
45 #include <pal/layer.h>
46 
47 #include "internalexception.h"
48 #include "util.h"
49 #include "labelposition.h"
50 #include "feature.h"
51 #include "geomfunction.h"
52 
53 #ifndef M_PI
54 #define M_PI 3.14159265358979323846
55 #endif
56 
57 #ifndef M_PI_2
58 #define M_PI_2 1.57079632679489661923
59 #endif
60 
61 #ifndef M_SQRT_2
62 #define M_SQRT_2 0.707106781186547524401
63 #endif
64 
65 #ifndef M_SQRT2
66 #define M_SQRT2 1.41421356237309504880
67 #endif
68 
69 namespace pal
70 {
71 
72  void sort( double* heap, int* x, int* y, int N )
73  {
74  unsigned int n = N, i = n / 2, parent, child;
75  double t;
76  int tx;
77  int ty;
78  for ( ;; )
79  {
80  if ( i > 0 )
81  {
82  i--;
83  t = heap[i];
84  tx = x[i];
85  ty = y[i];
86  }
87  else
88  {
89  n--;
90  if ( n == 0 ) return;
91  t = heap[n];
92  tx = x[n];
93  ty = y[n];
94  heap[n] = heap[0];
95  x[n] = x[0];
96  y[n] = y[0];
97  }
98  parent = i;
99  child = i * 2 + 1;
100  while ( child < n )
101  {
102  if ( child + 1 < n && heap[child + 1] > heap[child] )
103  {
104  child++;
105  }
106  if ( heap[child] > t )
107  {
108  heap[parent] = heap[child];
109  x[parent] = x[child];
110  y[parent] = y[child];
111  parent = child;
112  child = parent * 2 + 1;
113  }
114  else
115  {
116  break;
117  }
118  }
119  heap[parent] = t;
120  x[parent] = tx;
121  y[parent] = ty;
122  }
123  }
124 
125  void tabcpy( int n, const int* const x, const int* const y,
126  const double* const prob, int *cx, int *cy, double *p )
127  {
128  int i;
129 
130  for ( i = 0; i < n; i++ )
131  {
132  cx[i] = x[i];
133  cy[i] = y[i];
134  p[i] = prob[i];
135  }
136  }
137 
138 
139  void sort( void** items, int N, bool ( *greater )( void *l, void *r ) )
140  {
141 
142  if ( N <= 0 )
143  return;
144 
145  unsigned int n = ( unsigned int ) N, i = n / 2, parent, child;
146 
147  void *t = NULL;
148 
149  for ( ;; )
150  {
151  if ( i > 0 )
152  {
153  i--;
154  t = items[i];
155  }
156  else
157  {
158  n--;
159  if ( n == 0 ) return;
160  t = items[n];
161  items[n] = items[0];
162  }
163  parent = i;
164  child = i * 2 + 1;
165  while ( child < n )
166  {
167  if ( child + 1 < n && greater( items[child + 1], items[child] ) )
168  {
169  child++;
170  }
171  if ( greater( items[child], t ) )
172  {
173  items[parent] = items[child];
174  parent = child;
175  child = parent * 2 + 1;
176  }
177  else
178  {
179  break;
180  }
181  }
182  items[parent] = t;
183  }
184  }
185 
186  inline bool ptrGeomEq( const GEOSGeometry *l, const GEOSGeometry *r )
187  {
188  return l == r;
189  }
190 
191  LinkedList<const GEOSGeometry*> * unmulti( const GEOSGeometry *the_geom )
192  {
193  LinkedList<const GEOSGeometry*> *queue = new LinkedList<const GEOSGeometry*> ( ptrGeomEq );
194  LinkedList<const GEOSGeometry*> *final_queue = new LinkedList<const GEOSGeometry*> ( ptrGeomEq );
195 
196  const GEOSGeometry *geom;
197 
198  queue->push_back( the_geom );
199  int nGeom;
200  int i;
201 
202  while ( queue->size() > 0 )
203  {
204  geom = queue->pop_front();
205  GEOSContextHandle_t geosctxt = geosContext();
206  switch ( GEOSGeomTypeId_r( geosctxt, geom ) )
207  {
208  case GEOS_MULTIPOINT:
209  case GEOS_MULTILINESTRING:
210  case GEOS_MULTIPOLYGON:
211  nGeom = GEOSGetNumGeometries_r( geosctxt, geom );
212  for ( i = 0; i < nGeom; i++ )
213  {
214  queue->push_back( GEOSGetGeometryN_r( geosctxt, geom, i ) );
215  }
216  break;
217  case GEOS_POINT:
218  case GEOS_LINESTRING:
219  case GEOS_POLYGON:
220  final_queue->push_back( geom );
221  break;
222  default:
223  delete final_queue;
224  delete queue;
225  return NULL;
226  }
227  }
228  delete queue;
229 
230  return final_queue;
231  }
232 
233 
234 } // namespace
235 
236 
237