PostGIS  2.2.7dev-r@@SVN_REVISION@@
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 455 of file lwgeodetic_tree.c.

References circ_node::center, circ_node_is_leaf(), circ_tree_contains_point(), edge_distance_to_point(), edge_intersects(), circ_node::edge_num, GEOGRAPHIC_EDGE::end, FP_LTEQ, geog2cart(), geographic_point_init(), GEOGRAPHIC_POINT::lat, GEOGRAPHIC_POINT::lon, LWDEBUG, LWDEBUGF, circ_node::nodes, circ_node::num_nodes, circ_node::p1, circ_node::p2, PIR_B_TOUCH_RIGHT, PIR_COLINEAR, PIR_INTERSECTS, rad2deg, circ_node::radius, GEOGRAPHIC_EDGE::start, POINT2D::x, and POINT2D::y.

Referenced by circ_tree_contains_point(), circ_tree_distance_tree_internal(), CircTreePIP(), test_tree_circ_pip(), and test_tree_circ_pip2().

456 {
457  GEOGRAPHIC_POINT closest;
458  GEOGRAPHIC_EDGE stab_edge, edge;
459  POINT3D S1, S2, E1, E2;
460  double d;
461  int i, c;
462 
463  /* Construct a stabline edge from our "inside" to our known outside point */
464  geographic_point_init(pt->x, pt->y, &(stab_edge.start));
465  geographic_point_init(pt_outside->x, pt_outside->y, &(stab_edge.end));
466  geog2cart(&(stab_edge.start), &S1);
467  geog2cart(&(stab_edge.end), &S2);
468 
469  LWDEBUG(3, "entered");
470 
471  /*
472  * If the stabline doesn't cross within the radius of a node, there's no
473  * way it can cross.
474  */
475 
476  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));
477  d = edge_distance_to_point(&stab_edge, &(node->center), &closest);
478  LWDEBUGF(3, "edge_distance_to_point=%g, node_radius=%g", d, node->radius);
479  if ( FP_LTEQ(d, node->radius) )
480  {
481  LWDEBUGF(3,"entering this branch (%p)", node);
482 
483  /* Return the crossing number of this leaf */
484  if ( circ_node_is_leaf(node) )
485  {
486  int inter;
487  LWDEBUGF(3, "leaf node calculation (edge %d)", node->edge_num);
488  geographic_point_init(node->p1->x, node->p1->y, &(edge.start));
489  geographic_point_init(node->p2->x, node->p2->y, &(edge.end));
490  geog2cart(&(edge.start), &E1);
491  geog2cart(&(edge.end), &E2);
492 
493  inter = edge_intersects(&S1, &S2, &E1, &E2);
494 
495  if ( inter & PIR_INTERSECTS )
496  {
497  LWDEBUG(3," got stab line edge_intersection with this edge!");
498  /* To avoid double counting crossings-at-a-vertex, */
499  /* always ignore crossings at "lower" ends of edges*/
500 
501  if ( inter & PIR_B_TOUCH_RIGHT || inter & PIR_COLINEAR )
502  {
503  LWDEBUG(3," rejecting stab line grazing by left-side edge");
504  return 0;
505  }
506  else
507  {
508  LWDEBUG(3," accepting stab line intersection");
509  return 1;
510  }
511  }
512  }
513  /* Or, add up the crossing numbers of all children of this node. */
514  else
515  {
516  c = 0;
517  for ( i = 0; i < node->num_nodes; i++ )
518  {
519  LWDEBUG(3,"internal node calculation");
520  LWDEBUGF(3," calling circ_tree_contains_point on child %d!", i);
521  c += circ_tree_contains_point(node->nodes[i], pt, pt_outside, on_boundary);
522  }
523  return c % 2;
524  }
525  }
526  else
527  {
528  LWDEBUGF(3,"skipping this branch (%p)", node);
529  }
530 
531  return 0;
532 }
Two-point great circle segment from a to b.
Definition: lwgeodetic.h:41
#define PIR_B_TOUCH_RIGHT
Definition: lwgeodetic.h:71
GEOGRAPHIC_POINT center
POINT2D * p2
POINT2D * p1
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:50
#define FP_LTEQ(A, B)
Point in spherical coordinates on the world.
Definition: lwgeodetic.h:32
double x
Definition: liblwgeom.h:312
static int circ_node_is_leaf(const CIRC_NODE *node)
Internal nodes have their point references set to NULL.
#define rad2deg(r)
Definition: lwgeodetic.h:60
GEOGRAPHIC_POINT start
Definition: lwgeodetic.h:43
double edge_distance_to_point(const GEOGRAPHIC_EDGE *e, const GEOGRAPHIC_POINT *gp, GEOGRAPHIC_POINT *closest)
Definition: lwgeodetic.c:1166
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.
GEOGRAPHIC_POINT end
Definition: lwgeodetic.h:44
double y
Definition: liblwgeom.h:312
void geog2cart(const GEOGRAPHIC_POINT *g, POINT3D *p)
Convert spherical coordinates to cartesion coordinates on unit sphere.
Definition: lwgeodetic.c:354
int 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:3099
void geographic_point_init(double lon, double lat, GEOGRAPHIC_POINT *g)
Initialize a geographic point.
Definition: lwgeodetic.c:156
double radius
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:55
#define PIR_COLINEAR
Definition: lwgeodetic.h:68
struct circ_node ** nodes
#define PIR_INTERSECTS
Definition: lwgeodetic.h:67

Here is the call graph for this function:

Here is the caller graph for this function: