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

Definition at line 830 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().

831 {
832  int i = 0, j, k;
833  POINT4D a1, a2, a3, b;
834  POINT4D first, center;
835  char *edges_in_arcs;
836  int found_arc = LW_FALSE;
837  int current_arc = 1;
838  int num_edges;
839  int edge_type; /* non-zero if edge is part of an arc */
840  int start, end;
841  LWCOLLECTION *outcol;
842  /* Minimum number of edges, per quadrant, required to define an arc */
843  const unsigned int min_quad_edges = 2;
844 
845  /* Die on null input */
846  if ( ! points )
847  lwerror("pta_unstroke called with null pointarray");
848 
849  /* Null on empty input? */
850  if ( points->npoints == 0 )
851  return NULL;
852 
853  /* We can't desegmentize anything shorter than four points */
854  if ( points->npoints < 4 )
855  {
856  /* Return a linestring here*/
857  lwerror("pta_unstroke needs implementation for npoints < 4");
858  }
859 
860  /* Allocate our result array of vertices that are part of arcs */
861  num_edges = points->npoints - 1;
862  edges_in_arcs = lwalloc(num_edges + 1);
863  memset(edges_in_arcs, 0, num_edges + 1);
864 
865  /* We make a candidate arc of the first two edges, */
866  /* And then see if the next edge follows it */
867  while( i < num_edges-2 )
868  {
869  unsigned int arc_edges;
870  double num_quadrants;
871  double angle;
872 
873  found_arc = LW_FALSE;
874  /* Make candidate arc */
875  getPoint4d_p(points, i , &a1);
876  getPoint4d_p(points, i+1, &a2);
877  getPoint4d_p(points, i+2, &a3);
878  memcpy(&first, &a1, sizeof(POINT4D));
879 
880  for( j = i+3; j < num_edges+1; j++ )
881  {
882  LWDEBUGF(4, "i=%d, j=%d", i, j);
883  getPoint4d_p(points, j, &b);
884  /* Does this point fall on our candidate arc? */
885  if ( pt_continues_arc(&a1, &a2, &a3, &b) )
886  {
887  /* Yes. Mark this edge and the two preceding it as arc components */
888  LWDEBUGF(4, "pt_continues_arc #%d", current_arc);
889  found_arc = LW_TRUE;
890  for ( k = j-1; k > j-4; k-- )
891  edges_in_arcs[k] = current_arc;
892  }
893  else
894  {
895  /* No. So we're done with this candidate arc */
896  LWDEBUG(4, "pt_continues_arc = false");
897  current_arc++;
898  break;
899  }
900 
901  memcpy(&a1, &a2, sizeof(POINT4D));
902  memcpy(&a2, &a3, sizeof(POINT4D));
903  memcpy(&a3, &b, sizeof(POINT4D));
904  }
905  /* Jump past all the edges that were added to the arc */
906  if ( found_arc )
907  {
908  /* Check if an arc was composed by enough edges to be
909  * really considered an arc
910  * See http://trac.osgeo.org/postgis/ticket/2420
911  */
912  arc_edges = j - 1 - i;
913  LWDEBUGF(4, "arc defined by %d edges found", arc_edges);
914  if ( first.x == b.x && first.y == b.y ) {
915  LWDEBUG(4, "arc is a circle");
916  num_quadrants = 4;
917  }
918  else {
919  lw_arc_center((POINT2D*)&first, (POINT2D*)&b, (POINT2D*)&a1, (POINT2D*)&center);
920  angle = lw_arc_angle((POINT2D*)&first, (POINT2D*)&center, (POINT2D*)&b);
921  int p2_side = lw_segment_side((POINT2D*)&first, (POINT2D*)&a1, (POINT2D*)&b);
922  if ( p2_side >= 0 ) angle = -angle;
923 
924  if ( angle < 0 ) angle = 2 * M_PI + angle;
925  num_quadrants = ( 4 * angle ) / ( 2 * M_PI );
926  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);
927  }
928  /* a1 is first point, b is last point */
929  if ( arc_edges < min_quad_edges * num_quadrants ) {
930  LWDEBUGF(4, "Not enough edges for a %g quadrants arc, %g needed", num_quadrants, min_quad_edges * num_quadrants);
931  for ( k = j-1; k >= i; k-- )
932  edges_in_arcs[k] = 0;
933  }
934 
935  i = j-1;
936  }
937  else
938  {
939  /* Mark this edge as a linear edge */
940  edges_in_arcs[i] = 0;
941  i = i+1;
942  }
943  }
944 
945 #if POSTGIS_DEBUG_LEVEL > 3
946  {
947  char *edgestr = lwalloc(num_edges+1);
948  for ( i = 0; i < num_edges; i++ )
949  {
950  if ( edges_in_arcs[i] )
951  edgestr[i] = 48 + edges_in_arcs[i];
952  else
953  edgestr[i] = '.';
954  }
955  edgestr[num_edges] = 0;
956  LWDEBUGF(3, "edge pattern %s", edgestr);
957  lwfree(edgestr);
958  }
959 #endif
960 
961  start = 0;
962  edge_type = edges_in_arcs[0];
963  outcol = lwcollection_construct_empty(COMPOUNDTYPE, srid, ptarray_has_z(points), ptarray_has_m(points));
964  for( i = 1; i < num_edges; i++ )
965  {
966  if( edge_type != edges_in_arcs[i] )
967  {
968  end = i - 1;
969  lwcollection_add_lwgeom(outcol, geom_from_pa(points, srid, edge_type, start, end));
970  start = i;
971  edge_type = edges_in_arcs[i];
972  }
973  }
974  lwfree(edges_in_arcs); /* not needed anymore */
975 
976  /* Roll out last item */
977  end = num_edges - 1;
978  lwcollection_add_lwgeom(outcol, geom_from_pa(points, srid, edge_type, start, end));
979 
980  /* Strip down to singleton if only one entry */
981  if ( outcol->ngeoms == 1 )
982  {
983  LWGEOM *outgeom = outcol->geoms[0];
984  outcol->ngeoms = 0; lwcollection_free(outcol);
985  return outgeom;
986  }
987  return lwcollection_as_lwgeom(outcol);
988 }
double x
Definition: liblwgeom.h:351
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:227
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:724
void lwfree(void *mem)
Definition: lwutil.c:244
#define COMPOUNDTYPE
Definition: liblwgeom.h:92
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
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:746
uint32_t ngeoms
Definition: liblwgeom.h:506
#define LW_FALSE
Definition: liblwgeom.h:76
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:75
LWGEOM ** geoms
Definition: liblwgeom.h:508
static LWGEOM * geom_from_pa(const POINTARRAY *pa, int srid, int is_arc, int start, int end)
Definition: lwstroke.c:820
int getPoint4d_p(const POINTARRAY *pa, uint32_t n, POINT4D *point)
Definition: lwgeom_api.c:113
int ptarray_has_m(const POINTARRAY *pa)
Definition: ptarray.c:43
void lwcollection_free(LWCOLLECTION *col)
Definition: lwcollection.c:342
int ptarray_has_z(const POINTARRAY *pa)
Definition: ptarray.c:36
void * lwalloc(size_t size)
Definition: lwutil.c:229
int lw_segment_side(const POINT2D *p1, const POINT2D *p2, const POINT2D *q)
lw_segment_side()
Definition: lwalgorithm.c:64
double y
Definition: liblwgeom.h:351
LWCOLLECTION * lwcollection_construct_empty(uint8_t type, int srid, char hasz, char hasm)
Definition: lwcollection.c:94
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
LWCOLLECTION * lwcollection_add_lwgeom(LWCOLLECTION *col, const LWGEOM *geom)
Appends geom to the collection managed by col.
Definition: lwcollection.c:187
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:190
LWGEOM * lwcollection_as_lwgeom(const LWCOLLECTION *obj)
Definition: lwgeom.c:299
uint32_t npoints
Definition: liblwgeom.h:370

Here is the call graph for this function:

Here is the caller graph for this function: