lw_dist2d_seg_arc()

int lw_dist2d_seg_arc	(	const POINT2D *	A1,
		const POINT2D *	A2,
		const POINT2D *	B1,
		const POINT2D *	B2,
		const POINT2D *	B3,
		DISTPTS *	dl
	)

Calculate the shortest distance between an arc and an edge.

Line/circle approach from http://stackoverflow.com/questions/1073336/circle-line-collision-detection

Definition at line 1373 of file measures.c.

{
        POINT2D C;       /* center of arc circle */
        double radius_C; /* radius of arc circle */
        POINT2D D;       /* point on A closest to C */
        double dist_C_D; /* distance from C to D */
        int pt_in_arc, pt_in_seg;
        DISTPTS dltmp;
 
        /* Bail out on crazy modes */
        if (dl->mode < 0)
                lwerror("lw_dist2d_seg_arc does not support maxdistance mode");
 
        /* What if the "arc" is a point? */
        if (lw_arc_is_pt(B1, B2, B3))
                return lw_dist2d_pt_seg(B1, A1, A2, dl);
 
        /* Calculate center and radius of the circle. */
        radius_C = lw_arc_center(B1, B2, B3, &C);
 
        /* This "arc" is actually a line (B2 is collinear with B1,B3) */
        if (radius_C < 0.0)
                return lw_dist2d_seg_seg(A1, A2, B1, B3, dl);
 
        /* Calculate distance between the line and circle center */
        lw_dist2d_distpts_init(&dltmp, DIST_MIN);
        if (lw_dist2d_pt_seg(&C, A1, A2, &dltmp) == LW_FALSE)
                lwerror("lw_dist2d_pt_seg failed in lw_dist2d_seg_arc");
 
        D = dltmp.p1;
        dist_C_D = dltmp.distance;
 
        /* Line intersects circle, maybe arc intersects edge? */
        /* If so, that's the closest point. */
        /* If not, the closest point is one of the end points of A */
        if (dist_C_D < radius_C)
        {
                double length_A;  /* length of the segment A */
                POINT2D E, F;     /* points of intersection of edge A and circle(B) */
                double dist_D_EF; /* distance from D to E or F (same distance both ways) */
 
                dist_D_EF = sqrt(radius_C * radius_C - dist_C_D * dist_C_D);
                length_A = sqrt((A2->x - A1->x) * (A2->x - A1->x) + (A2->y - A1->y) * (A2->y - A1->y));
 
                /* Point of intersection E */
                E.x = D.x - (A2->x - A1->x) * dist_D_EF / length_A;
                E.y = D.y - (A2->y - A1->y) * dist_D_EF / length_A;
                /* Point of intersection F */
                F.x = D.x + (A2->x - A1->x) * dist_D_EF / length_A;
                F.y = D.y + (A2->y - A1->y) * dist_D_EF / length_A;
 
                /* If E is within A and within B then it's an intersection point */
                pt_in_arc = lw_pt_in_arc(&E, B1, B2, B3);
                pt_in_seg = lw_pt_in_seg(&E, A1, A2);
 
                if (pt_in_arc && pt_in_seg)
                {
                        dl->distance = 0.0;
                        dl->p1 = E;
                        dl->p2 = E;
                        return LW_TRUE;
                }
 
                /* If F is within A and within B then it's an intersection point */
                pt_in_arc = lw_pt_in_arc(&F, B1, B2, B3);
                pt_in_seg = lw_pt_in_seg(&F, A1, A2);
 
                if (pt_in_arc && pt_in_seg)
                {
                        dl->distance = 0.0;
                        dl->p1 = F;
                        dl->p2 = F;
                        return LW_TRUE;
                }
        }
 
        /* Line grazes circle, maybe arc intersects edge? */
        /* If so, grazing point is the closest point. */
        /* If not, the closest point is one of the end points of A */
        else if (dist_C_D == radius_C)
        {
                /* Closest point D is also the point of grazing */
                pt_in_arc = lw_pt_in_arc(&D, B1, B2, B3);
                pt_in_seg = lw_pt_in_seg(&D, A1, A2);
 
                /* Is D contained in both A and B? */
                if (pt_in_arc && pt_in_seg)
                {
                        dl->distance = 0.0;
                        dl->p1 = D;
                        dl->p2 = D;
                        return LW_TRUE;
                }
        }
        /* Line misses circle. */
        /* If closest point to A on circle is within B, then that's the closest */
        /* Otherwise, the closest point will be an end point of A */
        else
        {
                POINT2D G; /* Point on circle closest to A */
                G.x = C.x + (D.x - C.x) * radius_C / dist_C_D;
                G.y = C.y + (D.y - C.y) * radius_C / dist_C_D;
 
                pt_in_arc = lw_pt_in_arc(&G, B1, B2, B3);
                pt_in_seg = lw_pt_in_seg(&D, A1, A2);
 
                /* Closest point is on the interior of A and B */
                if (pt_in_arc && pt_in_seg)
                        return lw_dist2d_pt_pt(&D, &G, dl);
        }
 
        /* Now we test the many combinations of end points with either */
        /* arcs or edges. Each previous check determined if the closest */
        /* potential point was within the arc/segment inscribed on the */
        /* line/circle holding the arc/segment. */
 
        /* Closest point is in the arc, but not in the segment, so */
        /* one of the segment end points must be the closest. */
        if (pt_in_arc && !pt_in_seg)
        {
                lw_dist2d_pt_arc(A1, B1, B2, B3, dl);
                lw_dist2d_pt_arc(A2, B1, B2, B3, dl);
                return LW_TRUE;
        }
        /* or, one of the arc end points is the closest */
        else if (pt_in_seg && !pt_in_arc)
        {
                lw_dist2d_pt_seg(B1, A1, A2, dl);
                lw_dist2d_pt_seg(B3, A1, A2, dl);
                return LW_TRUE;
        }
        /* Finally, one of the end-point to end-point combos is the closest. */
        else
        {
                lw_dist2d_pt_pt(A1, B1, dl);
                lw_dist2d_pt_pt(A1, B3, dl);
                lw_dist2d_pt_pt(A2, B1, dl);
                lw_dist2d_pt_pt(A2, B3, dl);
                return LW_TRUE;
        }
 
        return LW_FALSE;
}

References DIST_MIN, DISTPTS::distance, lw_arc_center(), lw_arc_is_pt(), lw_dist2d_distpts_init(), lw_dist2d_pt_arc(), lw_dist2d_pt_pt(), lw_dist2d_pt_seg(), lw_dist2d_seg_seg(), LW_FALSE, lw_pt_in_arc(), lw_pt_in_seg(), LW_TRUE, lwerror(), DISTPTS::mode, DISTPTS::p1, DISTPTS::p2, POINT2D::x, and POINT2D::y.

Referenced by lw_dist2d_arc_arc(), lw_dist2d_ptarray_ptarrayarc(), rect_leaf_node_distance(), rect_leaf_node_intersects(), and test_lw_dist2d_seg_arc().

Here is the call graph for this function:

Here is the caller graph for this function: