circ_tree_distance_tree_internal()

static double circ_tree_distance_tree_internal ( const CIRC_NODE *  n1, const CIRC_NODE *  n2, double  threshold, double *  min_dist, double *  max_dist, GEOGRAPHIC_POINT *  closest1, GEOGRAPHIC_POINT *  closest2  )

static

Definition at line 663 of file lwgeodetic_tree.c.

{
        double max;
        double d, d_min;
        uint32_t i;
 
        LWDEBUGF(4, "entered, min_dist=%.8g max_dist=%.8g, type1=%d, type2=%d", *min_dist, *max_dist, n1->geom_type, n2->geom_type);
/*
        circ_tree_print(n1, 0);
        circ_tree_print(n2, 0);
*/
 
        /* Short circuit if we've already hit the minimum */
        if( *min_dist < threshold || *min_dist == 0.0 )
                return *min_dist;
 
        /* If your minimum is greater than anyone's maximum, you can't hold the winner */
        if( circ_node_min_distance(n1, n2) > *max_dist )
        {
                LWDEBUGF(4, "pruning pair %p, %p", n1, n2);
                return FLT_MAX;
        }
 
        /* If your maximum is a new low, we'll use that as our new global tolerance */
        max = circ_node_max_distance(n1, n2);
        LWDEBUGF(5, "max %.8g", max);
        if( max < *max_dist )
                *max_dist = max;
 
        /* Polygon on one side, primitive type on the other. Check for point-in-polygon */
        /* short circuit. */
        if ( n1->geom_type == POLYGONTYPE && n2->geom_type && ! lwtype_is_collection(n2->geom_type) )
        {
                POINT2D pt;
                circ_tree_get_point(n2, &pt);
                LWDEBUGF(4, "n1 is polygon, testing if contains (%.5g,%.5g)", pt.x, pt.y);
                if ( circ_tree_contains_point(n1, &pt, &(n1->pt_outside), NULL) )
                {
                        LWDEBUG(4, "it does");
                        *min_dist = 0.0;
                        geographic_point_init(pt.x, pt.y, closest1);
                        geographic_point_init(pt.x, pt.y, closest2);
                        return *min_dist;
                }
        }
        /* Polygon on one side, primitive type on the other. Check for point-in-polygon */
        /* short circuit. */
        if ( n2->geom_type == POLYGONTYPE && n1->geom_type && ! lwtype_is_collection(n1->geom_type) )
        {
                POINT2D pt;
                circ_tree_get_point(n1, &pt);
                LWDEBUGF(4, "n2 is polygon, testing if contains (%.5g,%.5g)", pt.x, pt.y);
                if ( circ_tree_contains_point(n2, &pt, &(n2->pt_outside), NULL) )
                {
                        LWDEBUG(4, "it does");
                        geographic_point_init(pt.x, pt.y, closest1);
                        geographic_point_init(pt.x, pt.y, closest2);
                        *min_dist = 0.0;
                        return *min_dist;
                }
        }
 
        /* Both leaf nodes, do a real distance calculation */
        if( circ_node_is_leaf(n1) && circ_node_is_leaf(n2) )
        {
                double d;
                GEOGRAPHIC_POINT close1, close2;
                LWDEBUGF(4, "testing leaf pair [%d], [%d]", n1->edge_num, n2->edge_num);
                /* One of the nodes is a point */
                if ( n1->p1 == n1->p2 || n2->p1 == n2->p2 )
                {
                        GEOGRAPHIC_EDGE e;
                        GEOGRAPHIC_POINT gp1, gp2;
 
                        /* Both nodes are points! */
                        if ( n1->p1 == n1->p2 && n2->p1 == n2->p2 )
                        {
                                geographic_point_init(n1->p1->x, n1->p1->y, &gp1);
                                geographic_point_init(n2->p1->x, n2->p1->y, &gp2);
                                close1 = gp1; close2 = gp2;
                                d = sphere_distance(&gp1, &gp2);
                        }
                        /* Node 1 is a point */
                        else if ( n1->p1 == n1->p2 )
                        {
                                geographic_point_init(n1->p1->x, n1->p1->y, &gp1);
                                geographic_point_init(n2->p1->x, n2->p1->y, &(e.start));
                                geographic_point_init(n2->p2->x, n2->p2->y, &(e.end));
                                close1 = gp1;
                                d = edge_distance_to_point(&e, &gp1, &close2);
                        }
                        /* Node 2 is a point */
                        else
                        {
                                geographic_point_init(n2->p1->x, n2->p1->y, &gp1);
                                geographic_point_init(n1->p1->x, n1->p1->y, &(e.start));
                                geographic_point_init(n1->p2->x, n1->p2->y, &(e.end));
                                close1 = gp1;
                                d = edge_distance_to_point(&e, &gp1, &close2);
                        }
                        LWDEBUGF(4, "  got distance %g", d);
                }
                /* Both nodes are edges */
                else
                {
                        GEOGRAPHIC_EDGE e1, e2;
                        GEOGRAPHIC_POINT g;
                        POINT3D A1, A2, B1, B2;
                        geographic_point_init(n1->p1->x, n1->p1->y, &(e1.start));
                        geographic_point_init(n1->p2->x, n1->p2->y, &(e1.end));
                        geographic_point_init(n2->p1->x, n2->p1->y, &(e2.start));
                        geographic_point_init(n2->p2->x, n2->p2->y, &(e2.end));
                        geog2cart(&(e1.start), &A1);
                        geog2cart(&(e1.end), &A2);
                        geog2cart(&(e2.start), &B1);
                        geog2cart(&(e2.end), &B2);
                        if ( edge_intersects(&A1, &A2, &B1, &B2) )
                        {
                                d = 0.0;
                                edge_intersection(&e1, &e2, &g);
                                close1 = close2 = g;
                        }
                        else
                        {
                                d = edge_distance_to_edge(&e1, &e2, &close1, &close2);
                        }
                        LWDEBUGF(4, "edge_distance_to_edge returned %g", d);
                }
                if ( d < *min_dist )
                {
                        *min_dist = d;
                        *closest1 = close1;
                        *closest2 = close2;
                }
                return d;
        }
        else
        {
                d_min = FLT_MAX;
                /* Drive the recursion into the COLLECTION types first so we end up with */
                /* pairings of primitive geometries that can be forced into the point-in-polygon */
                /* tests above. */
                if ( n1->geom_type && lwtype_is_collection(n1->geom_type) )
                {
                        circ_internal_nodes_sort(n1->nodes, n1->num_nodes, n2);
                        for ( i = 0; i < n1->num_nodes; i++ )
                        {
                                d = circ_tree_distance_tree_internal(n1->nodes[i], n2, threshold, min_dist, max_dist, closest1, closest2);
                                d_min = FP_MIN(d_min, d);
                        }
                }
                else if ( n2->geom_type && lwtype_is_collection(n2->geom_type) )
                {
                        circ_internal_nodes_sort(n2->nodes, n2->num_nodes, n1);
                        for ( i = 0; i < n2->num_nodes; i++ )
                        {
                                d = circ_tree_distance_tree_internal(n1, n2->nodes[i], threshold, min_dist, max_dist, closest1, closest2);
                                d_min = FP_MIN(d_min, d);
                        }
                }
                else if ( ! circ_node_is_leaf(n1) )
                {
                        circ_internal_nodes_sort(n1->nodes, n1->num_nodes, n2);
                        for ( i = 0; i < n1->num_nodes; i++ )
                        {
                                d = circ_tree_distance_tree_internal(n1->nodes[i], n2, threshold, min_dist, max_dist, closest1, closest2);
                                d_min = FP_MIN(d_min, d);
                        }
                }
                else if ( ! circ_node_is_leaf(n2) )
                {
                        circ_internal_nodes_sort(n2->nodes, n2->num_nodes, n1);
                        for ( i = 0; i < n2->num_nodes; i++ )
                        {
                                d = circ_tree_distance_tree_internal(n1, n2->nodes[i], threshold, min_dist, max_dist, closest1, closest2);
                                d_min = FP_MIN(d_min, d);
                        }
                }
                else
                {
                        /* Never get here */
                }
 
                return d_min;
        }
}

References circ_internal_nodes_sort(), circ_node_is_leaf(), circ_node_max_distance(), circ_node_min_distance(), circ_tree_contains_point(), circ_tree_get_point(), sort_node::d, edge_distance_to_edge(), edge_distance_to_point(), edge_intersection(), edge_intersects(), circ_node::edge_num, GEOGRAPHIC_EDGE::end, FP_MIN, geog2cart(), geographic_point_init(), circ_node::geom_type, LWDEBUG, LWDEBUGF, lwtype_is_collection(), circ_node::nodes, circ_node::num_nodes, circ_node::p1, circ_node::p2, POLYGONTYPE, circ_node::pt_outside, sphere_distance(), GEOGRAPHIC_EDGE::start, POINT2D::x, and POINT2D::y.

Referenced by circ_tree_distance_tree().

Here is the call graph for this function:

Here is the caller graph for this function: