rect_tree_distance_tree_recursive()

static double rect_tree_distance_tree_recursive ( RECT_NODE *  n1, RECT_NODE *  n2, RECT_TREE_DISTANCE_STATE *  state  )

static

Definition at line 1290 of file lwtree.c.

{
        double min, max;
 
        /* Short circuit if we've already hit the minimum */
        if (state->min_dist < state->threshold || state->min_dist == 0.0)
                return state->min_dist;
 
        /* If your minimum is greater than anyone's maximum, you can't hold the winner */
        min = rect_node_min_distance(n1, n2);
        if (min > state->max_dist)
        {
                //lwnotice("pruning pair %p, %p", n1, n2);
                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 = rect_node_max_distance(n1, n2);
        if (max < state->max_dist)
                state->max_dist = max;
 
        /* Both leaf nodes, do a real distance calculation */
        if (rect_node_is_leaf(n1) && rect_node_is_leaf(n2))
        {
                return rect_leaf_node_distance(&n1->l, &n2->l, state);
        }
        /* Recurse into nodes */
        else
        {
                int i, j;
                double d_min = FLT_MAX;
                rect_tree_node_sort(n1, n2);
                if (rect_node_is_leaf(n1) && !rect_node_is_leaf(n2))
                {
                        for (i = 0; i < n2->i.num_nodes; i++)
                        {
                                min = rect_tree_distance_tree_recursive(n1, n2->i.nodes[i], state);
                                d_min = FP_MIN(d_min, min);
                        }
                }
                else if (rect_node_is_leaf(n2) && !rect_node_is_leaf(n1))
                {
                        for (i = 0; i < n1->i.num_nodes; i++)
                        {
                                min = rect_tree_distance_tree_recursive(n1->i.nodes[i], n2, state);
                                d_min = FP_MIN(d_min, min);
                        }
                }
                else
                {
                        for (i = 0; i < n1->i.num_nodes; i++)
                        {
                                for (j = 0; j < n2->i.num_nodes; j++)
                                {
                                        min = rect_tree_distance_tree_recursive(n1->i.nodes[i], n2->i.nodes[j], state);
                                        d_min = FP_MIN(d_min, min);
                                }
                        }
                }
                return d_min;
        }
}

References FP_MIN, rect_node::i, rect_node::l, LWDEBUGF, rect_tree_distance_state::max_dist, rect_tree_distance_state::min_dist, RECT_NODE_INTERNAL::nodes, RECT_NODE_INTERNAL::num_nodes, rect_leaf_node_distance(), rect_node_is_leaf(), rect_node_max_distance(), rect_node_min_distance(), rect_tree_distance_tree_recursive(), rect_tree_node_sort(), and rect_tree_distance_state::threshold.

Referenced by rect_tree_distance_tree(), and rect_tree_distance_tree_recursive().

Here is the call graph for this function:

Here is the caller graph for this function: