Algorithm C for finding the intersection points of two two-dimensional quads?

Question

I have a quad type that 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 these squares on the same plane, I would like to be able to work out the intersection points of these squares. For example, if we have quad A and quad B , if any of B points goes beyond A, the algorithm should produce a quad with points, as shown in the figure below (A is in red, B is in purple):

Edit: Ordering points is not important, because later on I will use these points to build a quad that will be drawn inside A.

Answer 1

If the only reason for this is to draw the resulting polygon, why not use the GPU to do this work for you - you still use OpenGL. So instead of discussing how to build an 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, polygon intersection!

You could probably do it a lot more efficiently if you limited yourself to OpenGL 4 and used various available shaders.

Answer 2

Not a complete implementation, but:

• Write a procedure 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 a four-dimensional procedure, 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 square and the second is in purple (16 tests in total)

   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 each point of the red square, checking the purple square:

   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 each point of the purple square, checking the red square:

   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); 

Answer 3

• Are ATVs guaranteed non-self-intersecting?
• Are ATVs guaranteed convex?

If they are convex, then I believe that any intersection will lead to one polygon with no more than eight vertices. If they cannot be convex, as an intersection you can get two divided polygons.

Assuming convexity, I believe (but did not verify) that the set of vertices as a result will be the set of intersections of lines plus the set of vertices of any input quadrant that are contained in another. Then the intersection would be the (convex) hull of these vertices.

At this point, it’s just a matter of effectively picking these sets.

Answer 4

For convex polygons, I would recommend:

1: check the fact of intersection with the separation axis method (quick)

2: Find the intersection with the algorithm from O'Rourke's Book (C code available)