PostGIS  2.1.10dev-r@@SVN_REVISION@@
LWGEOM * pta_desegmentize ( POINTARRAY points,
int  type,
int  srid 
)

Definition at line 586 of file lwsegmentize.c.

References COMPOUNDTYPE, geom_from_pa(), LWCOLLECTION::geoms, getPoint4d_p(), lw_arc_angle(), lw_arc_center(), LW_FALSE, lw_segment_side(), LW_TRUE, lwalloc(), lwcollection_add_lwgeom(), lwcollection_as_lwgeom(), lwcollection_construct_empty(), lwcollection_free(), LWDEBUG, LWDEBUGF, lwerror(), lwfree(), LWCOLLECTION::ngeoms, POINTARRAY::npoints, pt_continues_arc(), ptarray_has_m(), ptarray_has_z(), POINT4D::x, and POINT4D::y.

Referenced by lwline_desegmentize(), and lwpolygon_desegmentize().

587 {
588  int i = 0, j, k;
589  POINT4D a1, a2, a3, b;
590  POINT4D first, center;
591  char *edges_in_arcs;
592  int found_arc = LW_FALSE;
593  int current_arc = 1;
594  int num_edges;
595  int edge_type; /* non-zero if edge is part of an arc */
596  int start, end;
597  LWCOLLECTION *outcol;
598  /* Minimum number of edges, per quadrant, required to define an arc */
599  const unsigned int min_quad_edges = 2;
600 
601  /* Die on null input */
602  if ( ! points )
603  lwerror("pta_desegmentize called with null pointarray");
604 
605  /* Null on empty input? */
606  if ( points->npoints == 0 )
607  return NULL;
608 
609  /* We can't desegmentize anything shorter than four points */
610  if ( points->npoints < 4 )
611  {
612  /* Return a linestring here*/
613  lwerror("pta_desegmentize needs implementation for npoints < 4");
614  }
615 
616  /* Allocate our result array of vertices that are part of arcs */
617  num_edges = points->npoints - 1;
618  edges_in_arcs = lwalloc(num_edges + 1);
619  memset(edges_in_arcs, 0, num_edges + 1);
620 
621  /* We make a candidate arc of the first two edges, */
622  /* And then see if the next edge follows it */
623  while( i < num_edges-2 )
624  {
625  unsigned int arc_edges;
626  double num_quadrants;
627  double angle;
628 
629  found_arc = LW_FALSE;
630  /* Make candidate arc */
631  getPoint4d_p(points, i , &a1);
632  getPoint4d_p(points, i+1, &a2);
633  getPoint4d_p(points, i+2, &a3);
634  memcpy(&first, &a1, sizeof(POINT4D));
635 
636  for( j = i+3; j < num_edges+1; j++ )
637  {
638  LWDEBUGF(4, "i=%d, j=%d", i, j);
639  getPoint4d_p(points, j, &b);
640  /* Does this point fall on our candidate arc? */
641  if ( pt_continues_arc(&a1, &a2, &a3, &b) )
642  {
643  /* Yes. Mark this edge and the two preceding it as arc components */
644  LWDEBUGF(4, "pt_continues_arc #%d", current_arc);
645  found_arc = LW_TRUE;
646  for ( k = j-1; k > j-4; k-- )
647  edges_in_arcs[k] = current_arc;
648  }
649  else
650  {
651  /* No. So we're done with this candidate arc */
652  LWDEBUG(4, "pt_continues_arc = false");
653  current_arc++;
654  break;
655  }
656 
657  memcpy(&a1, &a2, sizeof(POINT4D));
658  memcpy(&a2, &a3, sizeof(POINT4D));
659  memcpy(&a3, &b, sizeof(POINT4D));
660  }
661  /* Jump past all the edges that were added to the arc */
662  if ( found_arc )
663  {
664  /* Check if an arc was composed by enough edges to be
665  * really considered an arc
666  * See http://trac.osgeo.org/postgis/ticket/2420
667  */
668  arc_edges = j - 1 - i;
669  LWDEBUGF(4, "arc defined by %d edges found", arc_edges);
670  if ( first.x == b.x && first.y == b.y ) {
671  LWDEBUG(4, "arc is a circle");
672  num_quadrants = 4;
673  }
674  else {
675  lw_arc_center((POINT2D*)&first, (POINT2D*)&b, (POINT2D*)&a1, (POINT2D*)&center);
676  angle = lw_arc_angle((POINT2D*)&first, (POINT2D*)&center, (POINT2D*)&b);
677  int p2_side = lw_segment_side((POINT2D*)&first, (POINT2D*)&a1, (POINT2D*)&b);
678  if ( p2_side >= 0 ) angle = -angle;
679 
680  if ( angle < 0 ) angle = 2 * M_PI + angle;
681  num_quadrants = ( 4 * angle ) / ( 2 * M_PI );
682  LWDEBUGF(4, "arc angle (%g %g, %g %g, %g %g) is %g (side is %d), quandrants:%g", first.x, first.y, center.x, center.y, b.x, b.y, angle, p2_side, num_quadrants);
683  }
684  /* a1 is first point, b is last point */
685  if ( arc_edges < min_quad_edges * num_quadrants ) {
686  LWDEBUGF(4, "Not enough edges for a %g quadrants arc, %g needed", num_quadrants, min_quad_edges * num_quadrants);
687  for ( k = j-1; k >= i; k-- )
688  edges_in_arcs[k] = 0;
689  }
690  i = j-1;
691  }
692  else
693  {
694  /* Mark this edge as a linear edge */
695  edges_in_arcs[i] = 0;
696  i = i+1;
697  }
698  }
699 
700 #if POSTGIS_DEBUG_LEVEL > 3
701  {
702  char *edgestr = lwalloc(num_edges+1);
703  for ( i = 0; i < num_edges; i++ )
704  {
705  if ( edges_in_arcs[i] )
706  edgestr[i] = 48 + edges_in_arcs[i];
707  else
708  edgestr[i] = '.';
709  }
710  edgestr[num_edges] = 0;
711  LWDEBUGF(3, "edge pattern %s", edgestr);
712  lwfree(edgestr);
713  }
714 #endif
715 
716  start = 0;
717  edge_type = edges_in_arcs[0];
718  outcol = lwcollection_construct_empty(COMPOUNDTYPE, srid, ptarray_has_z(points), ptarray_has_m(points));
719  for( i = 1; i < num_edges; i++ )
720  {
721  if( edge_type != edges_in_arcs[i] )
722  {
723  end = i - 1;
724  lwcollection_add_lwgeom(outcol, geom_from_pa(points, srid, edge_type, start, end));
725  start = i;
726  edge_type = edges_in_arcs[i];
727  }
728  }
729  lwfree(edges_in_arcs); /* not needed anymore */
730 
731  /* Roll out last item */
732  end = num_edges - 1;
733  lwcollection_add_lwgeom(outcol, geom_from_pa(points, srid, edge_type, start, end));
734 
735  /* Strip down to singleton if only one entry */
736  if ( outcol->ngeoms == 1 )
737  {
738  LWGEOM *outgeom = outcol->geoms[0];
739  outcol->ngeoms = 0; lwcollection_free(outcol);
740  return outgeom;
741  }
742  return lwcollection_as_lwgeom(outcol);
743 }
double x
Definition: liblwgeom.h:308
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
static double lw_arc_angle(const POINT2D *a, const POINT2D *b, const POINT2D *c)
Return ABC angle in radians TODO: move to lwalgorithm.
Definition: lwsegmentize.c:480
void lwfree(void *mem)
Definition: lwutil.c:190
int npoints
Definition: liblwgeom.h:327
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: lwsegmentize.c:502
#define COMPOUNDTYPE
Definition: liblwgeom.h:68
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:50
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:67
#define LW_FALSE
Definition: liblwgeom.h:52
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:51
LWGEOM ** geoms
Definition: liblwgeom.h:465
static LWGEOM * geom_from_pa(const POINTARRAY *pa, int srid, int is_arc, int start, int end)
Definition: lwsegmentize.c:576
int ptarray_has_m(const POINTARRAY *pa)
Definition: ptarray.c:30
void lwcollection_free(LWCOLLECTION *col)
Definition: lwcollection.c:316
int ptarray_has_z(const POINTARRAY *pa)
Definition: ptarray.c:23
void * lwalloc(size_t size)
Definition: lwutil.c:175
int lw_segment_side(const POINT2D *p1, const POINT2D *p2, const POINT2D *q)
lw_segment_side()
Definition: lwalgorithm.c:62
double y
Definition: liblwgeom.h:308
LWCOLLECTION * lwcollection_construct_empty(uint8_t type, int srid, char hasz, char hasm)
Definition: lwcollection.c:81
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:55
LWCOLLECTION * lwcollection_add_lwgeom(LWCOLLECTION *col, const LWGEOM *geom)
Appends geom to the collection managed by col.
Definition: lwcollection.c:174
int getPoint4d_p(const POINTARRAY *pa, int n, POINT4D *point)
Definition: lwgeom_api.c:217
LWGEOM * lwcollection_as_lwgeom(const LWCOLLECTION *obj)
Definition: lwgeom.c:219

Here is the call graph for this function:

Here is the caller graph for this function: