A C algorithm for finding the intersection points of two 2D quads?

Question

I have a quad type which is defined as:

typedef struct __point {
    float x;
    float y;
} point_t;

typedef struct __quad {
    point_t p1;
    point_t p2;
    point_t p3;
    point_t p4;
} quad_t;

If I have two of those quads on the same plane, I would like to be able to work out the intersection points of those quads. For example, if we have quad A and quad B, if any of B's points fall outside of A, the algoritm should yield a quad with points as shown in the illustration below (A is in red, B is in purple):

Example

Edit: Ordering of the points is not important because I will later use those points to construct a quad that is going to be drawn inside A.

So you want to find the vertices of the overlapping region? Is the ordering of the points important? — Eric, Aug 31 '12 at 14:31
@DavidSchwartz: That won't find two of the points in the diagram — Eric, Aug 31 '12 at 14:33
Gah, this isn't exactly a "homework" question, I need this for my layering engine as I need to clip sublayers to parent layers. — Kristina, Aug 31 '12 at 14:35
The green points in your picture aren't what I'd call "intersection points". — Kerrek SB, Aug 31 '12 at 14:35
@Kerrek: to be fair, the four green points define the vertices of a new quad which represents the intersection of the two quads. — Paul R, Aug 31 '12 at 14:39
"_I will later use those points to construct a quad that is going to be drawn inside A_" - What makes you think the result will be a quad? What about two squares at 45 degrees on top of one another? — Eric, Aug 31 '12 at 14:41
@PaulR: Had the question asked for "the intersection", I'd have been fine with that. But it asks specifically for "intersection *points*", which made me wonder if the OP is clear about the geometry of the problem. — Kerrek SB, Aug 31 '12 at 14:41
@Eric I have not thought of that. I basically need to convert the intersected region to a set of triangle strip vector points that I can feed to `glDrawArray`. — Kristina, Aug 31 '12 at 14:46
Duplicate of http://stackoverflow.com/questions/2272179/a-simple-algorithm-for-polygon-intersection — CAFxX, Aug 31 '12 at 14:52

score 1 · Accepted Answer · answered Aug 31 '12 at 15:03

If the only reason to do this is to draw the resulting polygon, why not use the GPU to do the work for you - you're using OpenGL after all. So instead of messing about working out how to construct the intersection, do the following:-

Set Z values of Polygon A and Polygon B to some constant

Set Z test to no testing (always write Z regardless)

Disable Z test
Enable Z writes
Disable colour writes
Render Polygon A

Set Z test to z equal

Enable Z test
Disable Z write
Enable colour write
Render Polygon B

Hey presto, the intersection polygon!

You could probably make this far more efficient if you restricted yourself to OpenGL 4 and used the various shaders that are available.

Does that work on OpenGL|es 1.1? If so, that would be wonderful! — Kristina, Aug 31 '12 at 15:06
@TinaBrooks: I see no reason why it shouldn't work on the ES version. — Skizz, Aug 31 '12 at 15:07

Eric · Answer 2 · 2012-08-31T15:02:43.903

Not a complete implementation, but:

Write a routine to find the intersection point of two line segments, intersect_segment

bool segments_intersect(
    point_t a0, point_t a1,
    point_t b0, point_t b1,
    /*out*/ point_t* intersection
)

Write a point in quad routine, point_in_quad
```
bool point_in_quad(point_t p, quad_t q)
```

Apply segments_intersect to each pair of segments where the first is in the red quad and the second in the purple (16 tests overall)

point_t temp;
if(segments_intersect(red.p1, red.p2, purple.p1, purple.p2, &temp)))
    found_point(temp);
if(segments_intersect(red.p1, red.p2, purple.p2, purple.p3, &temp))
    found_point(temp);
if(segments_intersect(red.p1, red.p2, purple.p3, purple.p4, &temp))
    found_point(temp);

//10 more

if(segments_intersect(red.p4, red.p1, purple.p2, purple.p3, &temp))
    found_point(temp);
if(segments_intersect(red.p4, red.p1, purple.p3, purple.p4, &temp))
    found_point(temp);
if(segments_intersect(red.p4, red.p1, purple.p4, purple.p1, &temp))
    found_point(temp);

Apply point_in_quad to every point in the red quad testing the purple quad:

if(point_in_quad(red.p1, purple)) found_point(red.p1);
if(point_in_quad(red.p2, purple)) found_point(red.p2);
if(point_in_quad(red.p3, purple)) found_point(red.p3);
if(point_in_quad(red.p4, purple)) found_point(red.p4);

Apply point_in_quad to every point in the purple quad testing the red quad:

if(point_in_quad(purple.p1, red)) found_point(purple.p1);
if(point_in_quad(purple.p2, red)) found_point(purple.p2);
if(point_in_quad(purple.p3, red)) found_point(purple.p3);
if(point_in_quad(purple.p4, red)) found_point(purple.p4);

Wouldn't that be horribly inefficient? This code will run a lot of times (basically, for every layer, and there can be a lot of layers). — Kristina, Aug 31 '12 at 14:40
Note: this strategy may fail when the input quads are concave. — Thom Smith, Aug 31 '12 at 14:50
@ThomSmith: This strategy simply produces an (unordered) list of the vertices. It will still do this for the concave case. It just becomes invalid to assume that the points in that case correspond to a single polygon. — Eric, Aug 31 '12 at 14:54

score 0 · Answer 3 · answered Aug 31 '12 at 14:47

Are the quads guaranteed to be non-self-intersecting?
Are the quads guaranteed to be convex?

If they are convex, then I believe that any intersection will result in a single polygon with at most eight vertices. If they may not be convex, you can end up with two separated polygons as the intersection.

Assuming convex, I believe (but have not verified) that the set of vertices in the result will be the set of line intersections plus the set of vertices of either input quad that are contained in the other. The intersection would then be the (convex) hull of these vertices.

At this point, it's just a matter of getting those sets efficiently.

Yes, the quads are convex. And yes, they cannot be self-intersecting. — Kristina, Aug 31 '12 at 14:53

score 0 · Answer 4 · answered Aug 31 '12 at 16:33

0

For convex polygons I'd recommend:

1: Check the fact of intersection with the separation axes method (fast)

2: Find intersection with algorithm from O'Rourke book (C code available)

answered Aug 31 '12 at 16:33

MBo

77,366
5
53
86

A C algorithm for finding the intersection points of two 2D quads?

4 Answers4