itree_point_in_ring_recursive()

static IntervalTreeResult itree_point_in_ring_recursive ( const IntervalTreeNode *  node, const POINTARRAY *  pa, const POINT2D *  pt, int *  winding_number  )

static

Definition at line 365 of file intervaltree.c.

{
        if (!node) return ITREE_OUTSIDE;
        /*
         * If Y value is not within range of node, we can
         * learn nothing from this node or its children, so
         * we exit early.
         */
        uint8_t node_contains_value = FP_CONTAINS_INCL(node->min, pt->y, node->max) ? 1 : 0;
        if (!node_contains_value)
                return ITREE_OK;
 
        /* This is a leaf node, so evaluate winding number */
        if (node->numChildren == 0)
        {
                const POINT2D *seg1 = getPoint2d_cp(pa, node->edgeIndex);
                const POINT2D *seg2 = getPoint2d_cp(pa, node->edgeIndex + 1);
                double side = itree_segment_side(seg1, seg2, pt);
 
                /* Zero length segments are ignored. */
                // xxxx need a unit test, what about really really short segments?
                // if (distance2d_sqr_pt_pt(seg1, seg2) < FP_EPS*FP_EPS)
                //      return ITREE_OK;
 
                /* A point on the boundary of a ring is not contained. */
                /* WAS: if (fabs(side) < 1e-12), see ticket #852 */
                if (side == 0.0 && itree_point_on_segment(seg1, seg2, pt) == 1)
                        return ITREE_BOUNDARY;
 
                /*
                 * If the point is to the left of the line, and it's rising,
                 * then the line is to the right of the point and
                 * circling counter-clockwise, so increment.
                 */
                if ((seg1->y <= pt->y) && (pt->y < seg2->y) && (side > 0))
                {
                        *winding_number = *winding_number + 1;
                }
 
                /*
                 * If the point is to the right of the line, and it's falling,
                 * then the line is to the right of the point and circling
                 * clockwise, so decrement.
                 */
                else if ((seg2->y <= pt->y) && (pt->y < seg1->y) && (side < 0))
                {
                        *winding_number = *winding_number - 1;
                }
 
                return ITREE_OK;
        }
        /* This is an interior node, so recurse downwards */
        else
        {
                for (uint32_t i = 0; i < node->numChildren; i++)
                {
                        IntervalTreeResult rslt = itree_point_in_ring_recursive(node->children[i], pa, pt, winding_number);
                        /* Short circuit and send back boundary result */
                        if (rslt == ITREE_BOUNDARY)
                                return rslt;
                }
        }
        return ITREE_OK;
}

References IntervalTreeNode::children, IntervalTreeNode::edgeIndex, FP_CONTAINS_INCL, getPoint2d_cp(), ITREE_BOUNDARY, ITREE_OK, ITREE_OUTSIDE, itree_point_in_ring_recursive(), itree_point_on_segment(), itree_segment_side(), IntervalTreeNode::max, IntervalTreeNode::min, IntervalTreeNode::numChildren, and POINT2D::y.

Referenced by itree_point_in_ring(), and itree_point_in_ring_recursive().

Here is the call graph for this function:

Here is the caller graph for this function: