PostGIS  2.2.7dev-r@@SVN_REVISION@@
LWGEOM * pta_unstroke ( const POINTARRAY points,
int  type,
int  srid 
)

Definition at line 586 of file lwstroke.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_unstroke(), and lwpolygon_unstroke().

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_unstroke 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_unstroke 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 
691  i = j-1;
692  }
693  else
694  {
695  /* Mark this edge as a linear edge */
696  edges_in_arcs[i] = 0;
697  i = i+1;
698  }
699  }
700 
701 #if POSTGIS_DEBUG_LEVEL > 3
702  {
703  char *edgestr = lwalloc(num_edges+1);
704  for ( i = 0; i < num_edges; i++ )
705  {
706  if ( edges_in_arcs[i] )
707  edgestr[i] = 48 + edges_in_arcs[i];
708  else
709  edgestr[i] = '.';
710  }
711  edgestr[num_edges] = 0;
712  LWDEBUGF(3, "edge pattern %s", edgestr);
713  lwfree(edgestr);
714  }
715 #endif
716 
717  start = 0;
718  edge_type = edges_in_arcs[0];
719  outcol = lwcollection_construct_empty(COMPOUNDTYPE, srid, ptarray_has_z(points), ptarray_has_m(points));
720  for( i = 1; i < num_edges; i++ )
721  {
722  if( edge_type != edges_in_arcs[i] )
723  {
724  end = i - 1;
725  lwcollection_add_lwgeom(outcol, geom_from_pa(points, srid, edge_type, start, end));
726  start = i;
727  edge_type = edges_in_arcs[i];
728  }
729  }
730  lwfree(edges_in_arcs); /* not needed anymore */
731 
732  /* Roll out last item */
733  end = num_edges - 1;
734  lwcollection_add_lwgeom(outcol, geom_from_pa(points, srid, edge_type, start, end));
735 
736  /* Strip down to singleton if only one entry */
737  if ( outcol->ngeoms == 1 )
738  {
739  LWGEOM *outgeom = outcol->geoms[0];
740  outcol->ngeoms = 0; lwcollection_free(outcol);
741  return outgeom;
742  }
743  return lwcollection_as_lwgeom(outcol);
744 }
double x
Definition: liblwgeom.h:336
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:213
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:480
void lwfree(void *mem)
Definition: lwutil.c:214
int npoints
Definition: liblwgeom.h:355
#define COMPOUNDTYPE
Definition: liblwgeom.h:78
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:50
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:502
#define LW_FALSE
Definition: liblwgeom.h:62
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:61
LWGEOM ** geoms
Definition: liblwgeom.h:493
static LWGEOM * geom_from_pa(const POINTARRAY *pa, int srid, int is_arc, int start, int end)
Definition: lwstroke.c:576
int ptarray_has_m(const POINTARRAY *pa)
Definition: ptarray.c:43
void lwcollection_free(LWCOLLECTION *col)
Definition: lwcollection.c:326
int ptarray_has_z(const POINTARRAY *pa)
Definition: ptarray.c:36
void * lwalloc(size_t size)
Definition: lwutil.c:199
int lw_segment_side(const POINT2D *p1, const POINT2D *p2, const POINT2D *q)
lw_segment_side()
Definition: lwalgorithm.c:50
double y
Definition: liblwgeom.h:336
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
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:74
int getPoint4d_p(const POINTARRAY *pa, int n, POINT4D *point)
Definition: lwgeom_api.c:231
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: