PostGIS  2.5.7dev-r@@SVN_REVISION@@

## ◆ circ_tree_contains_point()

 int circ_tree_contains_point ( const CIRC_NODE * node, const POINT2D * pt, const POINT2D * pt_outside, int * on_boundary )

Walk the tree and count intersections between the stab line and the edges.

odd => containment, even => no containment. KNOWN PROBLEM: Grazings (think of a sharp point, just touching the stabline) will be counted for one, which will throw off the count.

Definition at line 495 of file lwgeodetic_tree.c.

496 {
497  GEOGRAPHIC_POINT closest;
498  GEOGRAPHIC_EDGE stab_edge, edge;
499  POINT3D S1, S2, E1, E2;
500  double d;
501  uint32_t i, c;
502
503  /* Construct a stabline edge from our "inside" to our known outside point */
504  geographic_point_init(pt->x, pt->y, &(stab_edge.start));
505  geographic_point_init(pt_outside->x, pt_outside->y, &(stab_edge.end));
506  geog2cart(&(stab_edge.start), &S1);
507  geog2cart(&(stab_edge.end), &S2);
508
509  LWDEBUG(3, "entered");
510
511  /*
512  * If the stabline doesn't cross within the radius of a node, there's no
513  * way it can cross.
514  */
515
516  LWDEBUGF(3, "working on node %p, edge_num %d, radius %g, center POINT(%g %g)", node, node->edge_num, node->radius, rad2deg(node->center.lon), rad2deg(node->center.lat));
517  d = edge_distance_to_point(&stab_edge, &(node->center), &closest);
519  if ( FP_LTEQ(d, node->radius) )
520  {
521  LWDEBUGF(3,"entering this branch (%p)", node);
522
523  /* Return the crossing number of this leaf */
524  if ( circ_node_is_leaf(node) )
525  {
526  int inter;
527  LWDEBUGF(3, "leaf node calculation (edge %d)", node->edge_num);
528  geographic_point_init(node->p1->x, node->p1->y, &(edge.start));
529  geographic_point_init(node->p2->x, node->p2->y, &(edge.end));
530  geog2cart(&(edge.start), &E1);
531  geog2cart(&(edge.end), &E2);
532
533  inter = edge_intersects(&S1, &S2, &E1, &E2);
534
535  if ( inter & PIR_INTERSECTS )
536  {
537  LWDEBUG(3," got stab line edge_intersection with this edge!");
538  /* To avoid double counting crossings-at-a-vertex, */
539  /* always ignore crossings at "lower" ends of edges*/
540
541  if ( inter & PIR_B_TOUCH_RIGHT || inter & PIR_COLINEAR )
542  {
543  LWDEBUG(3," rejecting stab line grazing by left-side edge");
544  return 0;
545  }
546  else
547  {
548  LWDEBUG(3," accepting stab line intersection");
549  return 1;
550  }
551  }
552  }
553  /* Or, add up the crossing numbers of all children of this node. */
554  else
555  {
556  c = 0;
557  for ( i = 0; i < node->num_nodes; i++ )
558  {
559  LWDEBUG(3,"internal node calculation");
560  LWDEBUGF(3," calling circ_tree_contains_point on child %d!", i);
561  c += circ_tree_contains_point(node->nodes[i], pt, pt_outside, on_boundary);
562  }
563  return c % 2;
564  }
565  }
566  else
567  {
568  LWDEBUGF(3,"skipping this branch (%p)", node);
569  }
570
571  return 0;
572 }
#define FP_LTEQ(A, B)
void geographic_point_init(double lon, double lat, GEOGRAPHIC_POINT *g)
Initialize a geographic point.
Definition: lwgeodetic.c:180
uint32_t edge_intersects(const POINT3D *A1, const POINT3D *A2, const POINT3D *B1, const POINT3D *B2)
Returns non-zero if edges A and B interact.
Definition: lwgeodetic.c:3540
double edge_distance_to_point(const GEOGRAPHIC_EDGE *e, const GEOGRAPHIC_POINT *gp, GEOGRAPHIC_POINT *closest)
Definition: lwgeodetic.c:1218
void geog2cart(const GEOGRAPHIC_POINT *g, POINT3D *p)
Convert spherical coordinates to cartesian coordinates on unit sphere.
Definition: lwgeodetic.c:404
Definition: lwgeodetic.h:80
#define PIR_COLINEAR
Definition: lwgeodetic.h:88
#define PIR_INTERSECTS
Definition: lwgeodetic.h:87
#define PIR_B_TOUCH_RIGHT
Definition: lwgeodetic.h:91
static int circ_node_is_leaf(const CIRC_NODE *node)
Internal nodes have their point references set to NULL.
int circ_tree_contains_point(const CIRC_NODE *node, const POINT2D *pt, const POINT2D *pt_outside, int *on_boundary)
Walk the tree and count intersections between the stab line and the edges.
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
GEOGRAPHIC_POINT start
Definition: lwgeodetic.h:63
GEOGRAPHIC_POINT end
Definition: lwgeodetic.h:64
Two-point great circle segment from a to b.
Definition: lwgeodetic.h:62
Point in spherical coordinates on the world.
Definition: lwgeodetic.h:53
double y
Definition: liblwgeom.h:331
double x
Definition: liblwgeom.h:331
uint32_t num_nodes
POINT2D * p2
struct circ_node ** nodes