PostGIS  2.5.7dev-r@@SVN_REVISION@@
lwstroke.c
Go to the documentation of this file.
1 /**********************************************************************
2  *
3  * PostGIS - Spatial Types for PostgreSQL
4  * http://postgis.net
5  *
6  * PostGIS is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation, either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * PostGIS is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with PostGIS. If not, see <http://www.gnu.org/licenses/>.
18  *
19  **********************************************************************
20  *
21  * Copyright (C) 2001-2006 Refractions Research Inc.
22  * Copyright (C) 2017 Sandro Santilli <strk@kbt.io>
23  *
24  **********************************************************************/
25 
26 
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <stdarg.h>
30 #include <string.h>
31 
32 #include "../postgis_config.h"
33 
34 /*#define POSTGIS_DEBUG_LEVEL 3*/
35 
36 #include "lwgeom_log.h"
37 
38 #include "liblwgeom_internal.h"
39 
40 
41 LWGEOM* pta_unstroke(const POINTARRAY *points, int srid);
42 LWGEOM* lwline_unstroke(const LWLINE *line);
43 LWGEOM* lwpolygon_unstroke(const LWPOLY *poly);
44 LWGEOM* lwmline_unstroke(const LWMLINE *mline);
45 LWGEOM* lwmpolygon_unstroke(const LWMPOLY *mpoly);
47 LWGEOM* lwgeom_unstroke(const LWGEOM *geom);
48 
49 
50 /*
51  * Determines (recursively in the case of collections) whether the geometry
52  * contains at least on arc geometry or segment.
53  */
54 int
55 lwgeom_has_arc(const LWGEOM *geom)
56 {
57  LWCOLLECTION *col;
58  uint32_t i;
59 
60  LWDEBUG(2, "lwgeom_has_arc called.");
61 
62  switch (geom->type)
63  {
64  case POINTTYPE:
65  case LINETYPE:
66  case POLYGONTYPE:
67  case TRIANGLETYPE:
68  case MULTIPOINTTYPE:
69  case MULTILINETYPE:
70  case MULTIPOLYGONTYPE:
72  case TINTYPE:
73  return LW_FALSE;
74  case CIRCSTRINGTYPE:
75  case CURVEPOLYTYPE:
76  case COMPOUNDTYPE:
77  return LW_TRUE;
78  /* It's a collection that MAY contain an arc */
79  default:
80  col = (LWCOLLECTION *)geom;
81  for (i=0; i<col->ngeoms; i++)
82  {
83  if (lwgeom_has_arc(col->geoms[i]) == LW_TRUE)
84  return LW_TRUE;
85  }
86  return LW_FALSE;
87  }
88 }
89 
90 
91 
92 /*******************************************************************************
93  * Begin curve segmentize functions
94  ******************************************************************************/
95 
96 static double interpolate_arc(double angle, double a1, double a2, double a3, double zm1, double zm2, double zm3)
97 {
98  LWDEBUGF(4,"angle %.05g a1 %.05g a2 %.05g a3 %.05g zm1 %.05g zm2 %.05g zm3 %.05g",angle,a1,a2,a3,zm1,zm2,zm3);
99  /* Counter-clockwise sweep */
100  if ( a1 < a2 )
101  {
102  if ( angle <= a2 )
103  return zm1 + (zm2-zm1) * (angle-a1) / (a2-a1);
104  else
105  return zm2 + (zm3-zm2) * (angle-a2) / (a3-a2);
106  }
107  /* Clockwise sweep */
108  else
109  {
110  if ( angle >= a2 )
111  return zm1 + (zm2-zm1) * (a1-angle) / (a1-a2);
112  else
113  return zm2 + (zm3-zm2) * (a2-angle) / (a2-a3);
114  }
115 }
116 
134 static int
136  const POINT4D *p1, const POINT4D *p2, const POINT4D *p3,
137  double tol, LW_LINEARIZE_TOLERANCE_TYPE tolerance_type,
138  int flags)
139 {
140  POINT2D center;
141  POINT2D *t1 = (POINT2D*)p1;
142  POINT2D *t2 = (POINT2D*)p2;
143  POINT2D *t3 = (POINT2D*)p3;
144  POINT4D pt;
145  int p2_side = 0;
146  int clockwise = LW_TRUE;
147  double radius; /* Arc radius */
148  double increment; /* Angle per segment */
149  double angle_shift = 0;
150  double a1, a2, a3, angle;
151  POINTARRAY *pa = to;
152  int is_circle = LW_FALSE;
153  int points_added = 0;
154  int reverse = 0;
155 
156  LWDEBUG(2, "lwarc_linearize called.");
157 
158  LWDEBUGF(2, " curve is CIRCULARSTRING(%.15g %.15f, %.15f %.15f, %.15f %15f)",
159  t1->x, t1->y, t2->x, t2->y, t3->x, t3->y);
160 
161  p2_side = lw_segment_side(t1, t3, t2);
162 
163  LWDEBUGF(2, " p2 side is %d", p2_side);
164 
165  /* Force counterclockwise scan if SYMMETRIC operation is requsested */
166  if ( p2_side == -1 && flags & LW_LINEARIZE_FLAG_SYMMETRIC )
167  {
168  /* swap p1-p3 */
169  t1 = (POINT2D*)p3;
170  t3 = (POINT2D*)p1;
171  p1 = (POINT4D*)t1;
172  p3 = (POINT4D*)t3;
173  p2_side = 1;
174  reverse = 1;
175  }
176 
177  radius = lw_arc_center(t1, t2, t3, &center);
178  LWDEBUGF(2, " center is POINT(%.15g %.15g) - radius:%g", center.x, center.y, radius);
179 
180  /* Matched start/end points imply circle */
181  if ( p1->x == p3->x && p1->y == p3->y )
182  is_circle = LW_TRUE;
183 
184  /* Negative radius signals straight line, p1/p2/p3 are colinear */
185  if ( (radius < 0.0 || p2_side == 0) && ! is_circle )
186  return 0;
187 
188  /* The side of the p1/p3 line that p2 falls on dictates the sweep
189  direction from p1 to p3. */
190  if ( p2_side == -1 )
191  clockwise = LW_TRUE;
192  else
193  clockwise = LW_FALSE;
194 
195  if ( tolerance_type == LW_LINEARIZE_TOLERANCE_TYPE_SEGS_PER_QUAD )
196  {{
197  int perQuad = rint(tol);
198  // error out if tol != perQuad ? (not-round)
199  if ( perQuad != tol )
200  {
201  lwerror("lwarc_linearize: segments per quadrant must be an integer value, got %.15g", tol, perQuad);
202  return -1;
203  }
204  if ( perQuad < 1 )
205  {
206  lwerror("lwarc_linearize: segments per quadrant must be at least 1, got %d", perQuad);
207  return -1;
208  }
209  increment = fabs(M_PI_2 / perQuad);
210  LWDEBUGF(2, "lwarc_linearize: perQuad:%d, increment:%g (%g degrees)", perQuad, increment, increment*180/M_PI);
211 
212  }}
213  else if ( tolerance_type == LW_LINEARIZE_TOLERANCE_TYPE_MAX_DEVIATION )
214  {{
215  double halfAngle, maxErr;
216  if ( tol <= 0 )
217  {
218  lwerror("lwarc_linearize: max deviation must be bigger than 0, got %.15g", tol);
219  return -1;
220  }
221 
222  /*
223  * Ref: https://en.wikipedia.org/wiki/Sagitta_(geometry)
224  *
225  * An arc "sagitta" (distance between middle point of arc and
226  * middle point of corresponding chord) is defined as:
227  *
228  * sagitta = radius * ( 1 - cos( angle ) );
229  *
230  * We want our sagitta to be at most "tolerance" long,
231  * and we want to find out angle, so we use the inverse
232  * formula:
233  *
234  * tol = radius * ( 1 - cos( angle ) );
235  * 1 - cos( angle ) = tol/radius
236  * - cos( angle ) = tol/radius - 1
237  * cos( angle ) = - tol/radius + 1
238  * angle = acos( 1 - tol/radius )
239  *
240  * Constraints: 1.0 - tol/radius must be between -1 and 1
241  * which means tol must be between 0 and 2 times
242  * the radius, which makes sense as you cannot have a
243  * sagitta bigger than twice the radius!
244  *
245  */
246  maxErr = tol;
247  if ( maxErr > radius * 2 )
248  {
249  maxErr = radius * 2;
250  LWDEBUGF(2, "lwarc_linearize: tolerance %g is too big, "
251  "using arc-max 2 * radius == %g", tol, maxErr);
252  }
253  do {
254  halfAngle = acos( 1.0 - maxErr / radius );
255  /* TODO: avoid a loop here, going rather straight to
256  * a minimum angle value */
257  if ( halfAngle != 0 ) break;
258  LWDEBUGF(2, "lwarc_linearize: tolerance %g is too small for this arc"
259  " to compute approximation angle, doubling it", maxErr);
260  maxErr *= 2;
261  } while(1);
262  increment = 2 * halfAngle;
263  LWDEBUGF(2, "lwarc_linearize: maxDiff:%g, radius:%g, halfAngle:%g, increment:%g (%g degrees)", tol, radius, halfAngle, increment, increment*180/M_PI);
264  }}
265  else if ( tolerance_type == LW_LINEARIZE_TOLERANCE_TYPE_MAX_ANGLE )
266  {
267  increment = tol;
268  if ( increment <= 0 )
269  {
270  lwerror("lwarc_linearize: max angle must be bigger than 0, got %.15g", tol);
271  return -1;
272  }
273  }
274  else
275  {
276  lwerror("lwarc_linearize: unsupported tolerance type %d", tolerance_type);
277  return LW_FALSE;
278  }
279 
280  /* Angles of each point that defines the arc section */
281  a1 = atan2(p1->y - center.y, p1->x - center.x);
282  a2 = atan2(p2->y - center.y, p2->x - center.x);
283  a3 = atan2(p3->y - center.y, p3->x - center.x);
284 
285  LWDEBUGF(2, "lwarc_linearize A1:%g (%g) A2:%g (%g) A3:%g (%g)",
286  a1, a1*180/M_PI, a2, a2*180/M_PI, a3, a3*180/M_PI);
287 
288  if ( flags & LW_LINEARIZE_FLAG_SYMMETRIC )
289  {{
290  /* Calculate total arc angle, in radians */
291  double angle = clockwise ? a1 - a3 : a3 - a1;
292  if ( angle < 0 ) angle += M_PI * 2;
293  LWDEBUGF(2, "lwarc_linearize SYMMETRIC requested - total angle %g deg",
294  angle * 180 / M_PI);
295  if ( flags & LW_LINEARIZE_FLAG_RETAIN_ANGLE )
296  {{
297  /* Number of steps */
298  int steps = trunc(angle / increment);
299  /* Angle reminder */
300  double angle_reminder = angle - ( increment * steps );
301  angle_shift = angle_reminder / 2.0;
302 
303  LWDEBUGF(2, "lwarc_linearize RETAIN_ANGLE operation requested - "
304  "total angle %g, steps %d, increment %g, reminder %g",
305  angle * 180 / M_PI, steps, increment * 180 / M_PI,
306  angle_reminder * 180 / M_PI);
307  }}
308  else
309  {{
310  /* Number of segments in output */
311  int segs = ceil(angle / increment);
312  /* Tweak increment to be regular for all the arc */
313  increment = angle/segs;
314 
315  LWDEBUGF(2, "lwarc_linearize SYMMETRIC operation requested - "
316  "total angle %g degrees - LINESTRING(%g %g,%g %g,%g %g) - S:%d - I:%g",
317  angle*180/M_PI, p1->x, p1->y, center.x, center.y, p3->x, p3->y,
318  segs, increment*180/M_PI);
319  }}
320  }}
321 
322  /* p2 on left side => clockwise sweep */
323  if ( clockwise )
324  {
325  LWDEBUG(2, " Clockwise sweep");
326  increment *= -1;
327  angle_shift *= -1;
328  /* Adjust a3 down so we can decrement from a1 to a3 cleanly */
329  if ( a3 > a1 )
330  a3 -= 2.0 * M_PI;
331  if ( a2 > a1 )
332  a2 -= 2.0 * M_PI;
333  }
334  /* p2 on right side => counter-clockwise sweep */
335  else
336  {
337  LWDEBUG(2, " Counterclockwise sweep");
338  /* Adjust a3 up so we can increment from a1 to a3 cleanly */
339  if ( a3 < a1 )
340  a3 += 2.0 * M_PI;
341  if ( a2 < a1 )
342  a2 += 2.0 * M_PI;
343  }
344 
345  /* Override angles for circle case */
346  if( is_circle )
347  {
348  increment = fabs(increment);
349  a3 = a1 + 2.0 * M_PI;
350  a2 = a1 + M_PI;
351  clockwise = LW_FALSE;
352  }
353 
354  LWDEBUGF(2, "lwarc_linearize angle_shift:%g, increment:%g",
355  angle_shift * 180/M_PI, increment * 180/M_PI);
356 
357  if ( reverse ) {{
358  const int capacity = 8; /* TODO: compute exactly ? */
359  pa = ptarray_construct_empty(ptarray_has_z(to), ptarray_has_m(to), capacity);
360  }}
361 
362  /* Sweep from a1 to a3 */
363  if ( ! reverse )
364  {
366  }
367  ++points_added;
368  if ( angle_shift ) angle_shift -= increment;
369  LWDEBUGF(2, "a1:%g (%g deg), a3:%g (%g deg), inc:%g, shi:%g, cw:%d",
370  a1, a1 * 180 / M_PI, a3, a3 * 180 / M_PI, increment, angle_shift, clockwise);
371  for ( angle = a1 + increment + angle_shift; clockwise ? angle > a3 : angle < a3; angle += increment )
372  {
373  LWDEBUGF(2, " SA: %g ( %g deg )", angle, angle*180/M_PI);
374  pt.x = center.x + radius * cos(angle);
375  pt.y = center.y + radius * sin(angle);
376  pt.z = interpolate_arc(angle, a1, a2, a3, p1->z, p2->z, p3->z);
377  pt.m = interpolate_arc(angle, a1, a2, a3, p1->m, p2->m, p3->m);
378  ptarray_append_point(pa, &pt, LW_FALSE);
379  ++points_added;
380  angle_shift = 0;
381  }
382 
383  /* Ensure the final point is EXACTLY the same as the first for the circular case */
384  if ( is_circle )
385  {
386  ptarray_remove_point(pa, pa->npoints - 1);
388  }
389 
390  if ( reverse )
391  {
392  int i;
394  for ( i=pa->npoints; i>0; i-- ) {
395  getPoint4d_p(pa, i-1, &pt);
396  ptarray_append_point(to, &pt, LW_FALSE);
397  }
398  ptarray_free(pa);
399  }
400 
401  return points_added;
402 }
403 
404 /*
405  * @param icurve input curve
406  * @param tol tolerance, semantic driven by tolerance_type
407  * @param tolerance_type see LW_LINEARIZE_TOLERANCE_TYPE
408  * @param flags see flags in lwarc_linearize
409  *
410  * @return a newly allocated LWLINE
411  */
412 static LWLINE *
413 lwcircstring_linearize(const LWCIRCSTRING *icurve, double tol,
414  LW_LINEARIZE_TOLERANCE_TYPE tolerance_type,
415  int flags)
416 {
417  LWLINE *oline;
418  POINTARRAY *ptarray;
419  uint32_t i, j;
420  POINT4D p1, p2, p3, p4;
421  int ret;
422 
423  LWDEBUGF(2, "lwcircstring_linearize called., dim = %d", icurve->points->flags);
424 
425  ptarray = ptarray_construct_empty(FLAGS_GET_Z(icurve->points->flags), FLAGS_GET_M(icurve->points->flags), 64);
426 
427  for (i = 2; i < icurve->points->npoints; i+=2)
428  {
429  LWDEBUGF(3, "lwcircstring_linearize: arc ending at point %d", i);
430 
431  getPoint4d_p(icurve->points, i - 2, &p1);
432  getPoint4d_p(icurve->points, i - 1, &p2);
433  getPoint4d_p(icurve->points, i, &p3);
434 
435  ret = lwarc_linearize(ptarray, &p1, &p2, &p3, tol, tolerance_type, flags);
436  if ( ret > 0 )
437  {
438  LWDEBUGF(3, "lwcircstring_linearize: generated %d points", ptarray->npoints);
439  }
440  else if ( ret == 0 )
441  {
442  LWDEBUG(3, "lwcircstring_linearize: points are colinear, returning curve points as line");
443 
444  for (j = i - 2 ; j < i ; j++)
445  {
446  getPoint4d_p(icurve->points, j, &p4);
447  ptarray_append_point(ptarray, &p4, LW_TRUE);
448  }
449  }
450  else
451  {
452  /* An error occurred, lwerror should have been called by now */
453  ptarray_free(ptarray);
454  return NULL;
455  }
456  }
457  getPoint4d_p(icurve->points, icurve->points->npoints-1, &p1);
458  ptarray_append_point(ptarray, &p1, LW_FALSE);
459 
460  oline = lwline_construct(icurve->srid, NULL, ptarray);
461  return oline;
462 }
463 
464 /*
465  * @param icompound input compound curve
466  * @param tol tolerance, semantic driven by tolerance_type
467  * @param tolerance_type see LW_LINEARIZE_TOLERANCE_TYPE
468  * @param flags see flags in lwarc_linearize
469  *
470  * @return a newly allocated LWLINE
471  */
472 static LWLINE *
473 lwcompound_linearize(const LWCOMPOUND *icompound, double tol,
474  LW_LINEARIZE_TOLERANCE_TYPE tolerance_type,
475  int flags)
476 {
477  LWGEOM *geom;
478  POINTARRAY *ptarray = NULL, *ptarray_out = NULL;
479  LWLINE *tmp = NULL;
480  uint32_t i, j;
481  POINT4D p;
482 
483  LWDEBUG(2, "lwcompound_stroke called.");
484 
485  ptarray = ptarray_construct_empty(FLAGS_GET_Z(icompound->flags), FLAGS_GET_M(icompound->flags), 64);
486 
487  for (i = 0; i < icompound->ngeoms; i++)
488  {
489  geom = icompound->geoms[i];
490  if (geom->type == CIRCSTRINGTYPE)
491  {
492  tmp = lwcircstring_linearize((LWCIRCSTRING *)geom, tol, tolerance_type, flags);
493  for (j = 0; j < tmp->points->npoints; j++)
494  {
495  getPoint4d_p(tmp->points, j, &p);
496  ptarray_append_point(ptarray, &p, LW_TRUE);
497  }
498  lwline_free(tmp);
499  }
500  else if (geom->type == LINETYPE)
501  {
502  tmp = (LWLINE *)geom;
503  for (j = 0; j < tmp->points->npoints; j++)
504  {
505  getPoint4d_p(tmp->points, j, &p);
506  ptarray_append_point(ptarray, &p, LW_TRUE);
507  }
508  }
509  else
510  {
511  lwerror("Unsupported geometry type %d found.",
512  geom->type, lwtype_name(geom->type));
513  return NULL;
514  }
515  }
516  ptarray_out = ptarray_remove_repeated_points(ptarray, 0.0);
517  ptarray_free(ptarray);
518  return lwline_construct(icompound->srid, NULL, ptarray_out);
519 }
520 
521 /* Kept for backward compatibility - TODO: drop */
522 LWLINE *
523 lwcompound_stroke(const LWCOMPOUND *icompound, uint32_t perQuad)
524 {
526 }
527 
528 
529 /*
530  * @param icompound input curve polygon
531  * @param tol tolerance, semantic driven by tolerance_type
532  * @param tolerance_type see LW_LINEARIZE_TOLERANCE_TYPE
533  * @param flags see flags in lwarc_linearize
534  *
535  * @return a newly allocated LWPOLY
536  */
537 static LWPOLY *
538 lwcurvepoly_linearize(const LWCURVEPOLY *curvepoly, double tol,
539  LW_LINEARIZE_TOLERANCE_TYPE tolerance_type,
540  int flags)
541 {
542  LWPOLY *ogeom;
543  LWGEOM *tmp;
544  LWLINE *line;
545  POINTARRAY **ptarray;
546  uint32_t i;
547 
548  LWDEBUG(2, "lwcurvepoly_linearize called.");
549 
550  ptarray = lwalloc(sizeof(POINTARRAY *)*curvepoly->nrings);
551 
552  for (i = 0; i < curvepoly->nrings; i++)
553  {
554  tmp = curvepoly->rings[i];
555  if (tmp->type == CIRCSTRINGTYPE)
556  {
557  line = lwcircstring_linearize((LWCIRCSTRING *)tmp, tol, tolerance_type, flags);
558  ptarray[i] = ptarray_clone_deep(line->points);
559  lwline_free(line);
560  }
561  else if (tmp->type == LINETYPE)
562  {
563  line = (LWLINE *)tmp;
564  ptarray[i] = ptarray_clone_deep(line->points);
565  }
566  else if (tmp->type == COMPOUNDTYPE)
567  {
568  line = lwcompound_linearize((LWCOMPOUND *)tmp, tol, tolerance_type, flags);
569  ptarray[i] = ptarray_clone_deep(line->points);
570  lwline_free(line);
571  }
572  else
573  {
574  lwerror("Invalid ring type found in CurvePoly.");
575  return NULL;
576  }
577  }
578 
579  ogeom = lwpoly_construct(curvepoly->srid, NULL, curvepoly->nrings, ptarray);
580  return ogeom;
581 }
582 
583 /* Kept for backward compatibility - TODO: drop */
584 LWPOLY *
585 lwcurvepoly_stroke(const LWCURVEPOLY *curvepoly, uint32_t perQuad)
586 {
588 }
589 
590 
599 static LWMLINE *
600 lwmcurve_linearize(const LWMCURVE *mcurve, double tol,
602  int flags)
603 {
604  LWMLINE *ogeom;
605  LWGEOM **lines;
606  uint32_t i;
607 
608  LWDEBUGF(2, "lwmcurve_linearize called, geoms=%d, dim=%d.", mcurve->ngeoms, FLAGS_NDIMS(mcurve->flags));
609 
610  lines = lwalloc(sizeof(LWGEOM *)*mcurve->ngeoms);
611 
612  for (i = 0; i < mcurve->ngeoms; i++)
613  {
614  const LWGEOM *tmp = mcurve->geoms[i];
615  if (tmp->type == CIRCSTRINGTYPE)
616  {
617  lines[i] = (LWGEOM *)lwcircstring_linearize((LWCIRCSTRING *)tmp, tol, type, flags);
618  }
619  else if (tmp->type == LINETYPE)
620  {
621  lines[i] = (LWGEOM *)lwline_construct(mcurve->srid, NULL, ptarray_clone_deep(((LWLINE *)tmp)->points));
622  }
623  else if (tmp->type == COMPOUNDTYPE)
624  {
625  lines[i] = (LWGEOM *)lwcompound_linearize((LWCOMPOUND *)tmp, tol, type, flags);
626  }
627  else
628  {
629  lwerror("Unsupported geometry found in MultiCurve.");
630  return NULL;
631  }
632  }
633 
634  ogeom = (LWMLINE *)lwcollection_construct(MULTILINETYPE, mcurve->srid, NULL, mcurve->ngeoms, lines);
635  return ogeom;
636 }
637 
646 static LWMPOLY *
647 lwmsurface_linearize(const LWMSURFACE *msurface, double tol,
649  int flags)
650 {
651  LWMPOLY *ogeom;
652  LWGEOM *tmp;
653  LWPOLY *poly;
654  LWGEOM **polys;
655  POINTARRAY **ptarray;
656  uint32_t i, j;
657 
658  LWDEBUG(2, "lwmsurface_linearize called.");
659 
660  polys = lwalloc(sizeof(LWGEOM *)*msurface->ngeoms);
661 
662  for (i = 0; i < msurface->ngeoms; i++)
663  {
664  tmp = msurface->geoms[i];
665  if (tmp->type == CURVEPOLYTYPE)
666  {
667  polys[i] = (LWGEOM *)lwcurvepoly_linearize((LWCURVEPOLY *)tmp, tol, type, flags);
668  }
669  else if (tmp->type == POLYGONTYPE)
670  {
671  poly = (LWPOLY *)tmp;
672  ptarray = lwalloc(sizeof(POINTARRAY *)*poly->nrings);
673  for (j = 0; j < poly->nrings; j++)
674  {
675  ptarray[j] = ptarray_clone_deep(poly->rings[j]);
676  }
677  polys[i] = (LWGEOM *)lwpoly_construct(msurface->srid, NULL, poly->nrings, ptarray);
678  }
679  }
680  ogeom = (LWMPOLY *)lwcollection_construct(MULTIPOLYGONTYPE, msurface->srid, NULL, msurface->ngeoms, polys);
681  return ogeom;
682 }
683 
692 static LWCOLLECTION *
693 lwcollection_linearize(const LWCOLLECTION *collection, double tol,
695  int flags)
696 {
697  LWCOLLECTION *ocol;
698  LWGEOM *tmp;
699  LWGEOM **geoms;
700  uint32_t i;
701 
702  LWDEBUG(2, "lwcollection_linearize called.");
703 
704  geoms = lwalloc(sizeof(LWGEOM *)*collection->ngeoms);
705 
706  for (i=0; i<collection->ngeoms; i++)
707  {
708  tmp = collection->geoms[i];
709  switch (tmp->type)
710  {
711  case CIRCSTRINGTYPE:
712  geoms[i] = (LWGEOM *)lwcircstring_linearize((LWCIRCSTRING *)tmp, tol, type, flags);
713  break;
714  case COMPOUNDTYPE:
715  geoms[i] = (LWGEOM *)lwcompound_linearize((LWCOMPOUND *)tmp, tol, type, flags);
716  break;
717  case CURVEPOLYTYPE:
718  geoms[i] = (LWGEOM *)lwcurvepoly_linearize((LWCURVEPOLY *)tmp, tol, type, flags);
719  break;
720  case MULTICURVETYPE:
721  case MULTISURFACETYPE:
722  case COLLECTIONTYPE:
723  geoms[i] = (LWGEOM *)lwcollection_linearize((LWCOLLECTION *)tmp, tol, type, flags);
724  break;
725  default:
726  geoms[i] = lwgeom_clone_deep(tmp);
727  break;
728  }
729  }
730  ocol = lwcollection_construct(COLLECTIONTYPE, collection->srid, NULL, collection->ngeoms, geoms);
731  return ocol;
732 }
733 
734 LWGEOM *
735 lwcurve_linearize(const LWGEOM *geom, double tol,
737  int flags)
738 {
739  LWGEOM * ogeom = NULL;
740  switch (geom->type)
741  {
742  case CIRCSTRINGTYPE:
743  ogeom = (LWGEOM *)lwcircstring_linearize((LWCIRCSTRING *)geom, tol, type, flags);
744  break;
745  case COMPOUNDTYPE:
746  ogeom = (LWGEOM *)lwcompound_linearize((LWCOMPOUND *)geom, tol, type, flags);
747  break;
748  case CURVEPOLYTYPE:
749  ogeom = (LWGEOM *)lwcurvepoly_linearize((LWCURVEPOLY *)geom, tol, type, flags);
750  break;
751  case MULTICURVETYPE:
752  ogeom = (LWGEOM *)lwmcurve_linearize((LWMCURVE *)geom, tol, type, flags);
753  break;
754  case MULTISURFACETYPE:
755  ogeom = (LWGEOM *)lwmsurface_linearize((LWMSURFACE *)geom, tol, type, flags);
756  break;
757  case COLLECTIONTYPE:
758  ogeom = (LWGEOM *)lwcollection_linearize((LWCOLLECTION *)geom, tol, type, flags);
759  break;
760  default:
761  ogeom = lwgeom_clone_deep(geom);
762  }
763  return ogeom;
764 }
765 
766 /* Kept for backward compatibility - TODO: drop */
767 LWGEOM *
768 lwgeom_stroke(const LWGEOM *geom, uint32_t perQuad)
769 {
771 }
772 
777 static double
778 lw_arc_angle(const POINT2D *a, const POINT2D *b, const POINT2D *c)
779 {
780  POINT2D ab, cb;
781 
782  ab.x = b->x - a->x;
783  ab.y = b->y - a->y;
784 
785  cb.x = b->x - c->x;
786  cb.y = b->y - c->y;
787 
788  double dot = (ab.x * cb.x + ab.y * cb.y); /* dot product */
789  double cross = (ab.x * cb.y - ab.y * cb.x); /* cross product */
790 
791  double alpha = atan2(cross, dot);
792 
793  return alpha;
794 }
795 
800 static int pt_continues_arc(const POINT4D *a1, const POINT4D *a2, const POINT4D *a3, const POINT4D *b)
801 {
802  POINT2D center;
803  POINT2D *t1 = (POINT2D*)a1;
804  POINT2D *t2 = (POINT2D*)a2;
805  POINT2D *t3 = (POINT2D*)a3;
806  POINT2D *tb = (POINT2D*)b;
807  double radius = lw_arc_center(t1, t2, t3, &center);
808  double b_distance, diff;
809 
810  /* Co-linear a1/a2/a3 */
811  if ( radius < 0.0 )
812  return LW_FALSE;
813 
814  b_distance = distance2d_pt_pt(tb, &center);
815  diff = fabs(radius - b_distance);
816  LWDEBUGF(4, "circle_radius=%g, b_distance=%g, diff=%g, percentage=%g", radius, b_distance, diff, diff/radius);
817 
818  /* Is the point b on the circle? */
819  if ( diff < EPSILON_SQLMM )
820  {
821  int a2_side = lw_segment_side(t1, t3, t2);
822  int b_side = lw_segment_side(t1, t3, tb);
823  double angle1 = lw_arc_angle(t1, t2, t3);
824  double angle2 = lw_arc_angle(t2, t3, tb);
825 
826  /* Is the angle similar to the previous one ? */
827  diff = fabs(angle1 - angle2);
828  LWDEBUGF(4, " angle1: %g, angle2: %g, diff:%g", angle1, angle2, diff);
829  if ( diff > EPSILON_SQLMM )
830  {
831  return LW_FALSE;
832  }
833 
834  /* Is the point b on the same side of a1/a3 as the mid-point a2 is? */
835  /* If not, it's in the unbounded part of the circle, so it continues the arc, return true. */
836  if ( b_side != a2_side )
837  return LW_TRUE;
838  }
839  return LW_FALSE;
840 }
841 
842 static LWGEOM*
843 linestring_from_pa(const POINTARRAY *pa, int srid, int start, int end)
844 {
845  int i = 0, j = 0;
846  POINT4D p;
847  POINTARRAY *pao = ptarray_construct(ptarray_has_z(pa), ptarray_has_m(pa), end-start+2);
848  LWDEBUGF(4, "srid=%d, start=%d, end=%d", srid, start, end);
849  for( i = start; i < end + 2; i++ )
850  {
851  getPoint4d_p(pa, i, &p);
852  ptarray_set_point4d(pao, j++, &p);
853  }
854  return lwline_as_lwgeom(lwline_construct(srid, NULL, pao));
855 }
856 
857 static LWGEOM*
858 circstring_from_pa(const POINTARRAY *pa, int srid, int start, int end)
859 {
860 
861  POINT4D p0, p1, p2;
863  LWDEBUGF(4, "srid=%d, start=%d, end=%d", srid, start, end);
864  getPoint4d_p(pa, start, &p0);
865  ptarray_set_point4d(pao, 0, &p0);
866  getPoint4d_p(pa, (start+end+1)/2, &p1);
867  ptarray_set_point4d(pao, 1, &p1);
868  getPoint4d_p(pa, end+1, &p2);
869  ptarray_set_point4d(pao, 2, &p2);
870  return lwcircstring_as_lwgeom(lwcircstring_construct(srid, NULL, pao));
871 }
872 
873 static LWGEOM*
874 geom_from_pa(const POINTARRAY *pa, int srid, int is_arc, int start, int end)
875 {
876  LWDEBUGF(4, "srid=%d, is_arc=%d, start=%d, end=%d", srid, is_arc, start, end);
877  if ( is_arc )
878  return circstring_from_pa(pa, srid, start, end);
879  else
880  return linestring_from_pa(pa, srid, start, end);
881 }
882 
883 LWGEOM*
884 pta_unstroke(const POINTARRAY *points, int srid)
885 {
886  int i = 0, j, k;
887  POINT4D a1, a2, a3, b;
888  POINT4D first, center;
889  char *edges_in_arcs;
890  int found_arc = LW_FALSE;
891  int current_arc = 1;
892  int num_edges;
893  int edge_type; /* non-zero if edge is part of an arc */
894  int start, end;
895  LWCOLLECTION *outcol;
896  /* Minimum number of edges, per quadrant, required to define an arc */
897  const unsigned int min_quad_edges = 2;
898 
899  /* Die on null input */
900  if ( ! points )
901  lwerror("pta_unstroke called with null pointarray");
902 
903  /* Null on empty input? */
904  if ( points->npoints == 0 )
905  return NULL;
906 
907  /* We can't desegmentize anything shorter than four points */
908  if ( points->npoints < 4 )
909  {
910  /* Return a linestring here*/
911  lwerror("pta_unstroke needs implementation for npoints < 4");
912  }
913 
914  /* Allocate our result array of vertices that are part of arcs */
915  num_edges = points->npoints - 1;
916  edges_in_arcs = lwalloc(num_edges + 1);
917  memset(edges_in_arcs, 0, num_edges + 1);
918 
919  /* We make a candidate arc of the first two edges, */
920  /* And then see if the next edge follows it */
921  while( i < num_edges-2 )
922  {
923  unsigned int arc_edges;
924  double num_quadrants;
925  double angle;
926 
927  found_arc = LW_FALSE;
928  /* Make candidate arc */
929  getPoint4d_p(points, i , &a1);
930  getPoint4d_p(points, i+1, &a2);
931  getPoint4d_p(points, i+2, &a3);
932  memcpy(&first, &a1, sizeof(POINT4D));
933 
934  for( j = i+3; j < num_edges+1; j++ )
935  {
936  LWDEBUGF(4, "i=%d, j=%d", i, j);
937  getPoint4d_p(points, j, &b);
938  /* Does this point fall on our candidate arc? */
939  if ( pt_continues_arc(&a1, &a2, &a3, &b) )
940  {
941  /* Yes. Mark this edge and the two preceding it as arc components */
942  LWDEBUGF(4, "pt_continues_arc #%d", current_arc);
943  found_arc = LW_TRUE;
944  for ( k = j-1; k > j-4; k-- )
945  edges_in_arcs[k] = current_arc;
946  }
947  else
948  {
949  /* No. So we're done with this candidate arc */
950  LWDEBUG(4, "pt_continues_arc = false");
951  current_arc++;
952  break;
953  }
954 
955  memcpy(&a1, &a2, sizeof(POINT4D));
956  memcpy(&a2, &a3, sizeof(POINT4D));
957  memcpy(&a3, &b, sizeof(POINT4D));
958  }
959  /* Jump past all the edges that were added to the arc */
960  if ( found_arc )
961  {
962  /* Check if an arc was composed by enough edges to be
963  * really considered an arc
964  * See http://trac.osgeo.org/postgis/ticket/2420
965  */
966  arc_edges = j - 1 - i;
967  LWDEBUGF(4, "arc defined by %d edges found", arc_edges);
968  if ( first.x == b.x && first.y == b.y ) {
969  LWDEBUG(4, "arc is a circle");
970  num_quadrants = 4;
971  }
972  else {
973  lw_arc_center((POINT2D*)&first, (POINT2D*)&b, (POINT2D*)&a1, (POINT2D*)&center);
974  angle = lw_arc_angle((POINT2D*)&first, (POINT2D*)&center, (POINT2D*)&b);
975  int p2_side = lw_segment_side((POINT2D*)&first, (POINT2D*)&a1, (POINT2D*)&b);
976  if ( p2_side >= 0 ) angle = -angle;
977 
978  if ( angle < 0 ) angle = 2 * M_PI + angle;
979  num_quadrants = ( 4 * angle ) / ( 2 * M_PI );
980  LWDEBUGF(4, "arc angle (%g %g, %g %g, %g %g) is %g (side is %d), quadrants:%g", first.x, first.y, center.x, center.y, b.x, b.y, angle, p2_side, num_quadrants);
981  }
982  /* a1 is first point, b is last point */
983  if ( arc_edges < min_quad_edges * num_quadrants ) {
984  LWDEBUGF(4, "Not enough edges for a %g quadrants arc, %g needed", num_quadrants, min_quad_edges * num_quadrants);
985  for ( k = j-1; k >= i; k-- )
986  edges_in_arcs[k] = 0;
987  }
988 
989  i = j-1;
990  }
991  else
992  {
993  /* Mark this edge as a linear edge */
994  edges_in_arcs[i] = 0;
995  i = i+1;
996  }
997  }
998 
999 #if POSTGIS_DEBUG_LEVEL > 3
1000  {
1001  char *edgestr = lwalloc(num_edges+1);
1002  for ( i = 0; i < num_edges; i++ )
1003  {
1004  if ( edges_in_arcs[i] )
1005  edgestr[i] = 48 + edges_in_arcs[i];
1006  else
1007  edgestr[i] = '.';
1008  }
1009  edgestr[num_edges] = 0;
1010  LWDEBUGF(3, "edge pattern %s", edgestr);
1011  lwfree(edgestr);
1012  }
1013 #endif
1014 
1015  start = 0;
1016  edge_type = edges_in_arcs[0];
1017  outcol = lwcollection_construct_empty(COMPOUNDTYPE, srid, ptarray_has_z(points), ptarray_has_m(points));
1018  for( i = 1; i < num_edges; i++ )
1019  {
1020  if( edge_type != edges_in_arcs[i] )
1021  {
1022  end = i - 1;
1023  lwcollection_add_lwgeom(outcol, geom_from_pa(points, srid, edge_type, start, end));
1024  start = i;
1025  edge_type = edges_in_arcs[i];
1026  }
1027  }
1028  lwfree(edges_in_arcs); /* not needed anymore */
1029 
1030  /* Roll out last item */
1031  end = num_edges - 1;
1032  lwcollection_add_lwgeom(outcol, geom_from_pa(points, srid, edge_type, start, end));
1033 
1034  /* Strip down to singleton if only one entry */
1035  if ( outcol->ngeoms == 1 )
1036  {
1037  LWGEOM *outgeom = outcol->geoms[0];
1038  outcol->ngeoms = 0; lwcollection_free(outcol);
1039  return outgeom;
1040  }
1041  return lwcollection_as_lwgeom(outcol);
1042 }
1043 
1044 
1045 LWGEOM *
1047 {
1048  LWDEBUG(2, "lwline_unstroke called.");
1049 
1050  if ( line->points->npoints < 4 ) return lwline_as_lwgeom(lwline_clone_deep(line));
1051  else return pta_unstroke(line->points, line->srid);
1052 }
1053 
1054 LWGEOM *
1056 {
1057  LWGEOM **geoms;
1058  uint32_t i, hascurve = 0;
1059 
1060  LWDEBUG(2, "lwpolygon_unstroke called.");
1061 
1062  geoms = lwalloc(sizeof(LWGEOM *)*poly->nrings);
1063  for (i=0; i<poly->nrings; i++)
1064  {
1065  geoms[i] = pta_unstroke(poly->rings[i], poly->srid);
1066  if (geoms[i]->type == CIRCSTRINGTYPE || geoms[i]->type == COMPOUNDTYPE)
1067  {
1068  hascurve = 1;
1069  }
1070  }
1071  if (hascurve == 0)
1072  {
1073  for (i=0; i<poly->nrings; i++)
1074  {
1075  lwfree(geoms[i]); /* TODO: should this be lwgeom_free instead ? */
1076  }
1077  return lwgeom_clone_deep((LWGEOM *)poly);
1078  }
1079 
1080  return (LWGEOM *)lwcollection_construct(CURVEPOLYTYPE, poly->srid, NULL, poly->nrings, geoms);
1081 }
1082 
1083 LWGEOM *
1085 {
1086  LWGEOM **geoms;
1087  uint32_t i, hascurve = 0;
1088 
1089  LWDEBUG(2, "lwmline_unstroke called.");
1090 
1091  geoms = lwalloc(sizeof(LWGEOM *)*mline->ngeoms);
1092  for (i=0; i<mline->ngeoms; i++)
1093  {
1094  geoms[i] = lwline_unstroke((LWLINE *)mline->geoms[i]);
1095  if (geoms[i]->type == CIRCSTRINGTYPE || geoms[i]->type == COMPOUNDTYPE)
1096  {
1097  hascurve = 1;
1098  }
1099  }
1100  if (hascurve == 0)
1101  {
1102  for (i=0; i<mline->ngeoms; i++)
1103  {
1104  lwfree(geoms[i]); /* TODO: should this be lwgeom_free instead ? */
1105  }
1106  return lwgeom_clone_deep((LWGEOM *)mline);
1107  }
1108  return (LWGEOM *)lwcollection_construct(MULTICURVETYPE, mline->srid, NULL, mline->ngeoms, geoms);
1109 }
1110 
1111 LWGEOM *
1113 {
1114  LWGEOM **geoms;
1115  uint32_t i, hascurve = 0;
1116 
1117  LWDEBUG(2, "lwmpoly_unstroke called.");
1118 
1119  geoms = lwalloc(sizeof(LWGEOM *)*mpoly->ngeoms);
1120  for (i=0; i<mpoly->ngeoms; i++)
1121  {
1122  geoms[i] = lwpolygon_unstroke((LWPOLY *)mpoly->geoms[i]);
1123  if (geoms[i]->type == CURVEPOLYTYPE)
1124  {
1125  hascurve = 1;
1126  }
1127  }
1128  if (hascurve == 0)
1129  {
1130  for (i=0; i<mpoly->ngeoms; i++)
1131  {
1132  lwfree(geoms[i]); /* TODO: should this be lwgeom_free instead ? */
1133  }
1134  return lwgeom_clone_deep((LWGEOM *)mpoly);
1135  }
1136  return (LWGEOM *)lwcollection_construct(MULTISURFACETYPE, mpoly->srid, NULL, mpoly->ngeoms, geoms);
1137 }
1138 
1139 LWGEOM *
1141 {
1142  LWCOLLECTION *ret = lwalloc(sizeof(LWCOLLECTION));
1143  memcpy(ret, c, sizeof(LWCOLLECTION));
1144 
1145  if (c->ngeoms > 0)
1146  {
1147  uint32_t i;
1148  ret->geoms = lwalloc(sizeof(LWGEOM *)*c->ngeoms);
1149  for (i=0; i < c->ngeoms; i++)
1150  {
1151  ret->geoms[i] = lwgeom_unstroke(c->geoms[i]);
1152  }
1153  if (c->bbox)
1154  {
1155  ret->bbox = gbox_copy(c->bbox);
1156  }
1157  }
1158  else
1159  {
1160  ret->bbox = NULL;
1161  ret->geoms = NULL;
1162  }
1163  return (LWGEOM *)ret;
1164 }
1165 
1166 
1167 LWGEOM *
1169 {
1170  LWDEBUG(2, "lwgeom_unstroke called.");
1171 
1172  switch (geom->type)
1173  {
1174  case LINETYPE:
1175  return lwline_unstroke((LWLINE *)geom);
1176  case POLYGONTYPE:
1177  return lwpolygon_unstroke((LWPOLY *)geom);
1178  case MULTILINETYPE:
1179  return lwmline_unstroke((LWMLINE *)geom);
1180  case MULTIPOLYGONTYPE:
1181  return lwmpolygon_unstroke((LWMPOLY *)geom);
1182  case COLLECTIONTYPE:
1183  return lwcollection_unstroke((LWCOLLECTION *)geom);
1184  default:
1185  return lwgeom_clone_deep(geom);
1186  }
1187 }
1188 
GBOX * gbox_copy(const GBOX *box)
Return a copy of the GBOX, based on dimensionality of flags.
Definition: g_box.c:433
int ptarray_remove_point(POINTARRAY *pa, uint32_t where)
Remove a point from an existing POINTARRAY.
Definition: ptarray.c:261
LW_LINEARIZE_TOLERANCE_TYPE
Semantic of the tolerance argument passed to lwcurve_linearize.
Definition: liblwgeom.h:2202
@ LW_LINEARIZE_TOLERANCE_TYPE_MAX_ANGLE
Tolerance expresses the maximum angle between the radii generating approximation line vertices,...
Definition: liblwgeom.h:2223
@ LW_LINEARIZE_TOLERANCE_TYPE_SEGS_PER_QUAD
Tolerance expresses the number of segments to use for each quarter of circle (quadrant).
Definition: liblwgeom.h:2208
@ LW_LINEARIZE_TOLERANCE_TYPE_MAX_DEVIATION
Tolerance expresses the maximum distance between an arbitrary point on the curve and the closest poin...
Definition: liblwgeom.h:2215
LWGEOM * lwline_as_lwgeom(const LWLINE *obj)
Definition: lwgeom.c:330
#define LW_FALSE
Definition: liblwgeom.h:77
LWGEOM * lwcollection_as_lwgeom(const LWCOLLECTION *obj)
Definition: lwgeom.c:300
#define COLLECTIONTYPE
Definition: liblwgeom.h:91
#define COMPOUNDTYPE
Definition: liblwgeom.h:93
double distance2d_pt_pt(const POINT2D *p1, const POINT2D *p2)
Definition: measures.c:2314
LWCOLLECTION * lwcollection_construct_empty(uint8_t type, int srid, char hasz, char hasm)
Definition: lwcollection.c:94
#define CURVEPOLYTYPE
Definition: liblwgeom.h:94
#define MULTILINETYPE
Definition: liblwgeom.h:89
#define MULTISURFACETYPE
Definition: liblwgeom.h:96
#define LINETYPE
Definition: liblwgeom.h:86
#define MULTIPOINTTYPE
Definition: liblwgeom.h:88
POINTARRAY * ptarray_clone_deep(const POINTARRAY *ptarray)
Deep clone a pointarray (also clones serialized pointlist)
Definition: ptarray.c:628
LWGEOM * lwgeom_clone_deep(const LWGEOM *lwgeom)
Deep clone an LWGEOM, everything is copied.
Definition: lwgeom.c:520
POINTARRAY * ptarray_construct(char hasz, char hasm, uint32_t npoints)
Construct an empty pointarray, allocating storage and setting the npoints, but not filling in any inf...
Definition: ptarray.c:62
#define POINTTYPE
LWTYPE numbers, used internally by PostGIS.
Definition: liblwgeom.h:85
#define FLAGS_GET_Z(flags)
Macros for manipulating the 'flags' byte.
Definition: liblwgeom.h:140
#define TINTYPE
Definition: liblwgeom.h:99
#define MULTIPOLYGONTYPE
Definition: liblwgeom.h:90
@ LW_LINEARIZE_FLAG_SYMMETRIC
Symmetric linearization means that the output vertices would be the same no matter the order of the p...
Definition: liblwgeom.h:2232
@ LW_LINEARIZE_FLAG_RETAIN_ANGLE
Retain angle instructs the engine to try its best to retain the requested angle between generating ra...
Definition: liblwgeom.h:2252
void lwfree(void *mem)
Definition: lwutil.c:244
#define FLAGS_NDIMS(flags)
Definition: liblwgeom.h:152
#define POLYGONTYPE
Definition: liblwgeom.h:87
#define POLYHEDRALSURFACETYPE
Definition: liblwgeom.h:97
#define CIRCSTRINGTYPE
Definition: liblwgeom.h:92
LWCIRCSTRING * lwcircstring_construct(int srid, GBOX *bbox, POINTARRAY *points)
Definition: lwcircstring.c:50
POINTARRAY * ptarray_construct_empty(char hasz, char hasm, uint32_t maxpoints)
Create a new POINTARRAY with no points.
Definition: ptarray.c:70
const char * lwtype_name(uint8_t type)
Return the type name string associated with a type number (e.g.
Definition: lwutil.c:218
#define FLAGS_GET_M(flags)
Definition: liblwgeom.h:141
void lwcollection_free(LWCOLLECTION *col)
Definition: lwcollection.c:356
int getPoint4d_p(const POINTARRAY *pa, uint32_t n, POINT4D *point)
Definition: lwgeom_api.c:123
void ptarray_free(POINTARRAY *pa)
Definition: ptarray.c:328
LWPOLY * lwpoly_construct(int srid, GBOX *bbox, uint32_t nrings, POINTARRAY **points)
Definition: lwpoly.c:43
LWCOLLECTION * lwcollection_construct(uint8_t type, int srid, GBOX *bbox, uint32_t ngeoms, LWGEOM **geoms)
Definition: lwcollection.c:43
LWGEOM * lwcircstring_as_lwgeom(const LWCIRCSTRING *obj)
Definition: lwgeom.c:305
int ptarray_append_point(POINTARRAY *pa, const POINT4D *pt, int allow_duplicates)
Append a point to the end of an existing POINTARRAY If allow_duplicate is LW_FALSE,...
Definition: ptarray.c:156
#define MULTICURVETYPE
Definition: liblwgeom.h:95
#define TRIANGLETYPE
Definition: liblwgeom.h:98
LWCOLLECTION * lwcollection_add_lwgeom(LWCOLLECTION *col, const LWGEOM *geom)
Appends geom to the collection managed by col.
Definition: lwcollection.c:187
void * lwalloc(size_t size)
Definition: lwutil.c:229
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:76
LWLINE * lwline_construct(int srid, GBOX *bbox, POINTARRAY *points)
Definition: lwline.c:42
void ptarray_set_point4d(POINTARRAY *pa, uint32_t n, const POINT4D *p4d)
Definition: lwgeom_api.c:435
void lwline_free(LWLINE *line)
Definition: lwline.c:76
#define EPSILON_SQLMM
Tolerance used to determine equality.
LWLINE * lwline_clone_deep(const LWLINE *lwgeom)
Definition: lwline.c:118
double lw_arc_center(const POINT2D *p1, const POINT2D *p2, const POINT2D *p3, POINT2D *result)
Determines the center of the circle defined by the three given points.
Definition: lwalgorithm.c:228
POINTARRAY * ptarray_remove_repeated_points(const POINTARRAY *in, double tolerance)
Definition: ptarray.c:1446
int ptarray_has_z(const POINTARRAY *pa)
Definition: ptarray.c:36
int lw_segment_side(const POINT2D *p1, const POINT2D *p2, const POINT2D *q)
lw_segment_side()
Definition: lwalgorithm.c:64
int ptarray_has_m(const POINTARRAY *pa)
Definition: ptarray.c:43
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:190
static LWGEOM * geom_from_pa(const POINTARRAY *pa, int srid, int is_arc, int start, int end)
Definition: lwstroke.c:874
LWGEOM * lwgeom_unstroke(const LWGEOM *geom)
Definition: lwstroke.c:1168
static LWLINE * lwcircstring_linearize(const LWCIRCSTRING *icurve, double tol, LW_LINEARIZE_TOLERANCE_TYPE tolerance_type, int flags)
Definition: lwstroke.c:413
LWGEOM * lwcurve_linearize(const LWGEOM *geom, double tol, LW_LINEARIZE_TOLERANCE_TYPE type, int flags)
Definition: lwstroke.c:735
LWGEOM * lwgeom_stroke(const LWGEOM *geom, uint32_t perQuad)
Definition: lwstroke.c:768
static LWGEOM * linestring_from_pa(const POINTARRAY *pa, int srid, int start, int end)
Definition: lwstroke.c:843
LWGEOM * pta_unstroke(const POINTARRAY *points, int srid)
Definition: lwstroke.c:884
static int lwarc_linearize(POINTARRAY *to, const POINT4D *p1, const POINT4D *p2, const POINT4D *p3, double tol, LW_LINEARIZE_TOLERANCE_TYPE tolerance_type, int flags)
Segmentize an arc.
Definition: lwstroke.c:135
static double interpolate_arc(double angle, double a1, double a2, double a3, double zm1, double zm2, double zm3)
Definition: lwstroke.c:96
static double lw_arc_angle(const POINT2D *a, const POINT2D *b, const POINT2D *c)
Return ABC angle in radians TODO: move to lwalgorithm.
Definition: lwstroke.c:778
static LWGEOM * circstring_from_pa(const POINTARRAY *pa, int srid, int start, int end)
Definition: lwstroke.c:858
static int pt_continues_arc(const POINT4D *a1, const POINT4D *a2, const POINT4D *a3, const POINT4D *b)
Returns LW_TRUE if b is on the arc formed by a1/a2/a3, but not within that portion already described ...
Definition: lwstroke.c:800
static LWMPOLY * lwmsurface_linearize(const LWMSURFACE *msurface, double tol, LW_LINEARIZE_TOLERANCE_TYPE type, int flags)
Definition: lwstroke.c:647
static LWLINE * lwcompound_linearize(const LWCOMPOUND *icompound, double tol, LW_LINEARIZE_TOLERANCE_TYPE tolerance_type, int flags)
Definition: lwstroke.c:473
static LWCOLLECTION * lwcollection_linearize(const LWCOLLECTION *collection, double tol, LW_LINEARIZE_TOLERANCE_TYPE type, int flags)
Definition: lwstroke.c:693
LWGEOM * lwmpolygon_unstroke(const LWMPOLY *mpoly)
Definition: lwstroke.c:1112
static LWMLINE * lwmcurve_linearize(const LWMCURVE *mcurve, double tol, LW_LINEARIZE_TOLERANCE_TYPE type, int flags)
Definition: lwstroke.c:600
LWLINE * lwcompound_stroke(const LWCOMPOUND *icompound, uint32_t perQuad)
Definition: lwstroke.c:523
LWPOLY * lwcurvepoly_stroke(const LWCURVEPOLY *curvepoly, uint32_t perQuad)
Definition: lwstroke.c:585
LWGEOM * lwpolygon_unstroke(const LWPOLY *poly)
Definition: lwstroke.c:1055
static LWPOLY * lwcurvepoly_linearize(const LWCURVEPOLY *curvepoly, double tol, LW_LINEARIZE_TOLERANCE_TYPE tolerance_type, int flags)
Definition: lwstroke.c:538
LWGEOM * lwcollection_unstroke(const LWCOLLECTION *c)
Definition: lwstroke.c:1140
LWGEOM * lwmline_unstroke(const LWMLINE *mline)
Definition: lwstroke.c:1084
LWGEOM * lwline_unstroke(const LWLINE *line)
Definition: lwstroke.c:1046
int lwgeom_has_arc(const LWGEOM *geom)
Definition: lwstroke.c:55
type
Definition: ovdump.py:41
int32_t srid
Definition: liblwgeom.h:446
POINTARRAY * points
Definition: liblwgeom.h:447
uint32_t ngeoms
Definition: liblwgeom.h:510
GBOX * bbox
Definition: liblwgeom.h:508
LWGEOM ** geoms
Definition: liblwgeom.h:512
int32_t srid
Definition: liblwgeom.h:509
uint8_t flags
Definition: liblwgeom.h:520
int32_t srid
Definition: liblwgeom.h:522
uint32_t ngeoms
Definition: liblwgeom.h:523
LWGEOM ** geoms
Definition: liblwgeom.h:525
int32_t srid
Definition: liblwgeom.h:535
LWGEOM ** rings
Definition: liblwgeom.h:538
uint32_t nrings
Definition: liblwgeom.h:536
uint8_t type
Definition: liblwgeom.h:399
POINTARRAY * points
Definition: liblwgeom.h:425
int32_t srid
Definition: liblwgeom.h:424
LWGEOM ** geoms
Definition: liblwgeom.h:551
uint8_t flags
Definition: liblwgeom.h:546
uint32_t ngeoms
Definition: liblwgeom.h:549
int32_t srid
Definition: liblwgeom.h:548
int32_t srid
Definition: liblwgeom.h:483
LWLINE ** geoms
Definition: liblwgeom.h:486
uint32_t ngeoms
Definition: liblwgeom.h:484
uint32_t ngeoms
Definition: liblwgeom.h:497
LWPOLY ** geoms
Definition: liblwgeom.h:499
int32_t srid
Definition: liblwgeom.h:496
int32_t srid
Definition: liblwgeom.h:561
uint32_t ngeoms
Definition: liblwgeom.h:562
LWGEOM ** geoms
Definition: liblwgeom.h:564
POINTARRAY ** rings
Definition: liblwgeom.h:460
uint32_t nrings
Definition: liblwgeom.h:458
int32_t srid
Definition: liblwgeom.h:457
double y
Definition: liblwgeom.h:331
double x
Definition: liblwgeom.h:331
double m
Definition: liblwgeom.h:355
double x
Definition: liblwgeom.h:355
double z
Definition: liblwgeom.h:355
double y
Definition: liblwgeom.h:355
uint32_t npoints
Definition: liblwgeom.h:374
uint8_t flags
Definition: liblwgeom.h:372
unsigned int uint32_t
Definition: uthash.h:78