Algorithm for edge intersection?

Question

Given Polygon P which I have its verticies in order. and I have a rectangle R with 4 verticies how could I do this:

If any edge of P (line between adjacent vertexes) intersects an edge of R, then return TRUE, otherwise return FALSE.

Thanks

 *             *


*              *

Answer 1

http://www.ytechie.com/2009/08/determine-if-a-point-is-contained-within-a-polygon.html

Answer 2

I think your problem is equivalent to convex polygon intersection, in which case this might help. See also: http://stackoverflow.com/questions/753140/how-do-i-determine-if-two-convex-polygons-intersect

Answer 3

Untested, obviously, but in rough pseudocode:

// test two points against an edge
function intersects ( side, lower, upper, pt1Perp, pt1Par, pt2Perp, pt2Par )
{
    if ( ( pt1Perp < side and pt2Perp > side ) or ( pt1Perp > side and pt2Perp < side )
    {
        intersection = (side - pt1Perp) * (pt2Par - pt1Par) / (pt2Perp - pt1Perp);
        return (intersection >= lower and intersection <= higher);
    }
    else
    {
        return false;
    }
}

// left, right, bottom, top are the bounds of R
for pt1, pt2 adjacent in P  // don't forget to do last,first
{
    if ( intersects ( left, bottom, top, pt1.x, pt1.y, pt2.x, pt2.y )
         or intersects ( right, bottom, top, pt1.x, pt1.y, pt2.x, pt2.y )
         or intersects ( top, left, right, pt1.y, pt1.x, pt2.y, pt2.x )
         or intersects ( bottom, left, right, pt1.y, pt1.x, pt2.y, pt2.x ) )
    {
        return true;
    }
}

Basically, if two adjacent P vertices are on opposite sides of one of the R's edges, check whether the intersection point falls in range.

Answer 4

What you want is a quick way to determine if a line-segment intersects an axis-aligned rectangle. Then just check each line segment in the edge list against the rectangle. You can do the following:

1) Project the line onto the X-axis, resulting in an interval L_x.
2) Project the rectangle onto the X-axis, resulting in an interval R_x.
3) If L_x and R_x do not intersect, the line and rectangle do not intersect.

[Repeat for the Y-axis]:

4) Project the line onto the Y-axis, resulting in an interval L_y.
5) Project the rectangle onto the Y-axis, resulting in an interval R_y.
6) If L_y and R_y do not intersect, the line and rectangle do not intersect.

7) ...
8) They intersect.

Note if we reach step 7, the shapes cannot be separated by an axis-aligned line. The thing to determine now is if the line is fully outside the rectangle. We can determine this by checking that all the corner points on the rectangle are on the same side of the line. If they are, the line and rectangle are not intersecting.

The idea behind 1-3 and 4-6 comes from the separating axis theorem; if we cannot find a separating axis, they must be intersecting. All these cases must be tested before we can conclude they are intersecting.

Here's the matching code:

#include <iostream>
#include <utility>
#include <vector>

typedef double number; // number type

struct point
{
    number x;
    number y;
};

point make_point(number pX, number pY)
{
    point r = {pX, pY};
    return r;
}

typedef std::pair<number, number> interval; // start, end
typedef std::pair<point, point> segment; // start, end
typedef std::pair<point, point> rectangle; // top-left, bottom-right

namespace classification
{
    enum type
    {
        positive = 1,
        same = 0,
        negative = -1
    };
}

classification::type classify_point(const point& pPoint,
                                    const segment& pSegment)
{
    // implicit line equation
    number x = (pSegment.first.y - pSegment.second.y) * pPoint.x +
                (pSegment.second.x - pSegment.first.x) * pPoint.y +
                (pSegment.first.x * pSegment.second.y -
                 pSegment.second.x * pSegment.first.y);

    // careful with floating point types, should use approximation
    if (x == 0)
    {
        return classification::same;
    }
    else
    {
        return (x > 0) ? classification::positive :classification::negative;
    }
}

bool number_interval(number pX, const interval& pInterval)
{
    if (pInterval.first < pInterval.second)
    {
        return pX > pInterval.first && pX < pInterval.second;
    }
    else
    {
        return pX > pInterval.second && pX < pInterval.first;
    }
}

bool inteveral_interval(const interval& pFirst, const interval& pSecond)
{
    return number_interval(pFirst.first, pSecond) ||
            number_interval(pFirst.second, pSecond) ||
            number_interval(pSecond.first, pFirst) ||
            number_interval(pSecond.second, pFirst);
}

bool segment_rectangle(const segment& pSegment, const rectangle& pRectangle)
{
    // project onto x (discard y values)
    interval segmentX =
                std::make_pair(pSegment.first.x, pSegment.second.x);
    interval rectangleX =
                std::make_pair(pRectangle.first.x, pRectangle.second.x);

    if (!inteveral_interval(segmentX, rectangleX))
        return false;

    // project onto y (discard x values)
    interval segmentY =
                std::make_pair(pSegment.first.y, pSegment.second.y);
    interval rectangleY =
                std::make_pair(pRectangle.first.y, pRectangle.second.y);

    if (!inteveral_interval(segmentY, rectangleY))
        return false;

    // test rectangle location
    point p0 = make_point(pRectangle.first.x, pRectangle.first.y);
    point p1 = make_point(pRectangle.second.x, pRectangle.first.y);
    point p2 = make_point(pRectangle.second.x, pRectangle.second.y);
    point p3 = make_point(pRectangle.first.x, pRectangle.second.y);

    classification::type c0 = classify_point(p0, pSegment);
    classification::type c1 = classify_point(p1, pSegment);
    classification::type c2 = classify_point(p2, pSegment);
    classification::type c3 = classify_point(p3, pSegment);

    // test they all classify the same
    return !((c0 == c1) && (c1 == c2) && (c2 == c3));
}

int main(void)
{
    rectangle r = std::make_pair(make_point(1, 1), make_point(5, 5));
    segment s0 = std::make_pair(make_point(0, 3), make_point(2, -3));
    segment s1 = std::make_pair(make_point(0, 0), make_point(3, 0));
    segment s2 = std::make_pair(make_point(3, 0), make_point(3, 6));
    segment s3 = std::make_pair(make_point(2, 3), make_point(9, 8));

    std::cout << std::boolalpha;
    std::cout << segment_rectangle(s0, r) << std::endl;
    std::cout << segment_rectangle(s1, r) << std::endl;
    std::cout << segment_rectangle(s2, r) << std::endl;
    std::cout << segment_rectangle(s3, r) << std::endl;
}

Hope that makes sense.

Answer 5

Just FYI, geometrictools is a great resource for such things (especially the Math section)