PostGIS  3.1.6dev-r@@SVN_REVISION@@

◆ ptarray_dp_findsplit_in_place()

static uint32_t ptarray_dp_findsplit_in_place ( const POINTARRAY pts,
uint32_t  it_first,
uint32_t  it_last,
double  max_distance_sqr 
)
static

Definition at line 1531 of file ptarray.c.

1532 {
1533  uint32_t split = it_first;
1534  if ((it_first - it_last) < 2)
1535  return it_first;
1536 
1537  const POINT2D *A = getPoint2d_cp(pts, it_first);
1538  const POINT2D *B = getPoint2d_cp(pts, it_last);
1539 
1540  if (distance2d_sqr_pt_pt(A, B) < DBL_EPSILON)
1541  {
1542  /* If p1 == p2, we can just calculate the distance from each point to A */
1543  for (uint32_t itk = it_first + 1; itk < it_last; itk++)
1544  {
1545  const POINT2D *pk = getPoint2d_cp(pts, itk);
1546  double distance_sqr = distance2d_sqr_pt_pt(pk, A);
1547  if (distance_sqr > max_distance_sqr)
1548  {
1549  split = itk;
1550  max_distance_sqr = distance_sqr;
1551  }
1552  }
1553  return split;
1554  }
1555 
1556  /* This is based on distance2d_sqr_pt_seg, but heavily inlined here to avoid recalculations */
1557  double ba_x = (B->x - A->x);
1558  double ba_y = (B->y - A->y);
1559  double ab_length_sqr = (ba_x * ba_x + ba_y * ba_y);
1560  /* To avoid the division by ab_length_sqr in the 3rd path, we normalize here
1561  * and multiply in the first two paths [(dot_ac_ab < 0) and (> ab_length_sqr)] */
1562  max_distance_sqr *= ab_length_sqr;
1563  for (uint32_t itk = it_first + 1; itk < it_last; itk++)
1564  {
1565  const POINT2D *C = getPoint2d_cp(pts, itk);
1566  double distance_sqr;
1567  double ca_x = (C->x - A->x);
1568  double ca_y = (C->y - A->y);
1569  double dot_ac_ab = (ca_x * ba_x + ca_y * ba_y);
1570 
1571  if (dot_ac_ab <= 0.0)
1572  {
1573  distance_sqr = distance2d_sqr_pt_pt(C, A) * ab_length_sqr;
1574  }
1575  else if (dot_ac_ab >= ab_length_sqr)
1576  {
1577  distance_sqr = distance2d_sqr_pt_pt(C, B) * ab_length_sqr;
1578  }
1579  else
1580  {
1581  double s_numerator = ca_x * ba_y - ca_y * ba_x;
1582  distance_sqr = s_numerator * s_numerator; /* Missing division by ab_length_sqr on purpose */
1583  }
1584 
1585  if (distance_sqr > max_distance_sqr)
1586  {
1587  split = itk;
1588  max_distance_sqr = distance_sqr;
1589  }
1590  }
1591  return split;
1592 }
static const POINT2D * getPoint2d_cp(const POINTARRAY *pa, uint32_t n)
Returns a POINT2D pointer into the POINTARRAY serialized_ptlist, suitable for reading from.
Definition: lwinline.h:101
static double distance2d_sqr_pt_pt(const POINT2D *p1, const POINT2D *p2)
Definition: lwinline.h:35
double y
Definition: liblwgeom.h:404
double x
Definition: liblwgeom.h:404

References distance2d_sqr_pt_pt(), getPoint2d_cp(), POINT2D::x, and POINT2D::y.

Referenced by ptarray_simplify_in_place().

Here is the call graph for this function:
Here is the caller graph for this function: