QGIS API Documentation  2.11.0-Master
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 #include <stddef.h>
31 #include <geos_c.h>
32 
33 #include <sstream>
34 
35 #include <iostream>
36 #include <cfloat>
37 //#include <cfloat>
38 #include <cstdarg>
39 #include <ctime>
40 
41 #include "layer.h"
42 #include "internalexception.h"
43 #include "util.h"
44 #include "labelposition.h"
45 #include "feature.h"
46 #include "geomfunction.h"
47 
48 #ifndef M_PI
49 #define M_PI 3.14159265358979323846
50 #endif
51 
52 #ifndef M_PI_2
53 #define M_PI_2 1.57079632679489661923
54 #endif
55 
56 #ifndef M_SQRT_2
57 #define M_SQRT_2 0.707106781186547524401
58 #endif
59 
60 #ifndef M_SQRT2
61 #define M_SQRT2 1.41421356237309504880
62 #endif
63 
64 namespace pal
65 {
66 
67  void sort( double* heap, int* x, int* y, int N )
68  {
69  unsigned int n = N, i = n / 2, parent, child;
70  double t;
71  int tx;
72  int ty;
73  for ( ;; )
74  {
75  if ( i > 0 )
76  {
77  i--;
78  t = heap[i];
79  tx = x[i];
80  ty = y[i];
81  }
82  else
83  {
84  n--;
85  if ( n == 0 ) return;
86  t = heap[n];
87  tx = x[n];
88  ty = y[n];
89  heap[n] = heap[0];
90  x[n] = x[0];
91  y[n] = y[0];
92  }
93  parent = i;
94  child = i * 2 + 1;
95  while ( child < n )
96  {
97  if ( child + 1 < n && heap[child + 1] > heap[child] )
98  {
99  child++;
100  }
101  if ( heap[child] > t )
102  {
103  heap[parent] = heap[child];
104  x[parent] = x[child];
105  y[parent] = y[child];
106  parent = child;
107  child = parent * 2 + 1;
108  }
109  else
110  {
111  break;
112  }
113  }
114  heap[parent] = t;
115  x[parent] = tx;
116  y[parent] = ty;
117  }
118  }
119 
120  void tabcpy( int n, const int* const x, const int* const y,
121  const double* const prob, int *cx, int *cy, double *p )
122  {
123  int i;
124 
125  for ( i = 0; i < n; i++ )
126  {
127  cx[i] = x[i];
128  cy[i] = y[i];
129  p[i] = prob[i];
130  }
131  }
132 
133 
134  void sort( void** items, int N, bool ( *greater )( void *l, void *r ) )
135  {
136 
137  if ( N <= 0 )
138  return;
139 
140  unsigned int n = ( unsigned int ) N, i = n / 2, parent, child;
141 
142  void *t = NULL;
143 
144  for ( ;; )
145  {
146  if ( i > 0 )
147  {
148  i--;
149  t = items[i];
150  }
151  else
152  {
153  n--;
154  if ( n == 0 ) return;
155  t = items[n];
156  items[n] = items[0];
157  }
158  parent = i;
159  child = i * 2 + 1;
160  while ( child < n )
161  {
162  if ( child + 1 < n && greater( items[child + 1], items[child] ) )
163  {
164  child++;
165  }
166  if ( greater( items[child], t ) )
167  {
168  items[parent] = items[child];
169  parent = child;
170  child = parent * 2 + 1;
171  }
172  else
173  {
174  break;
175  }
176  }
177  items[parent] = t;
178  }
179  }
180 
181  inline bool ptrGeomEq( const GEOSGeometry *l, const GEOSGeometry *r )
182  {
183  return l == r;
184  }
185 
186  LinkedList<const GEOSGeometry*> * unmulti( const GEOSGeometry *the_geom )
187  {
190 
191  const GEOSGeometry *geom;
192 
193  queue->push_back( the_geom );
194  int nGeom;
195  int i;
196 
197  while ( queue->size() > 0 )
198  {
199  geom = queue->pop_front();
200  GEOSContextHandle_t geosctxt = geosContext();
201  switch ( GEOSGeomTypeId_r( geosctxt, geom ) )
202  {
203  case GEOS_MULTIPOINT:
204  case GEOS_MULTILINESTRING:
205  case GEOS_MULTIPOLYGON:
206  nGeom = GEOSGetNumGeometries_r( geosctxt, geom );
207  for ( i = 0; i < nGeom; i++ )
208  {
209  queue->push_back( GEOSGetGeometryN_r( geosctxt, geom, i ) );
210  }
211  break;
212  case GEOS_POINT:
213  case GEOS_LINESTRING:
214  case GEOS_POLYGON:
215  final_queue->push_back( geom );
216  break;
217  default:
218  delete final_queue;
219  delete queue;
220  return NULL;
221  }
222  }
223  delete queue;
224 
225  return final_queue;
226  }
227 
228 
229 } // namespace
230 
231 
232 
LinkedList< const GEOSGeometry * > * unmulti(const GEOSGeometry *the_geom)
Definition: util.cpp:186
bool ptrGeomEq(const GEOSGeometry *l, const GEOSGeometry *r)
Definition: util.cpp:181
GEOSContextHandle_t geosContext()
Get GEOS context handle to be used in all GEOS library calls with reentrant API.
Definition: pal.cpp:79
void tabcpy(int n, const int *const x, const int *const y, const double *const prob, int *cx, int *cy, double *p)
Definition: util.cpp:120
void sort(double *heap, int *x, int *y, int N)
Definition: util.cpp:67