2D CSG: Finding difference between intersection of two polygons

Originally, I have two polygons that do not intersect, call them A and B. I now translate polygon A with a translation vector $V$ such that $A\land B \neq \phi$. I now want to find a factor $\alpha$ to scale $V$ with such that $A\land B = \phi$, but if $\alpha$ was even just slightly bigger, they would intersect. Available data for computation are the two original polygons, the fully translated polygon, the polygon formed by the intersection, and the original translation vector. The green arrow is the scaled original vector represented by the blue arrow. What would be the best way to find $\alpha$? I have never done this before and am kind of stumped on how to go about it.

The application of this is a collision algorithm I am trying to write. Thanks!

• Is it okay to assume your polygons are non-self-intersecting, non-degenerate (not simple points or lines, with zero area), and drawn counterclockwise (in a right-handed coordinate system; for example, one with $x$ axis right and $y$ axis up)? If these restrictions are allowed, the solution is quite easy and not hard at all to implement. You only need the original polygons' vertices in order, and the original translation vector; no need to compute the intersection polygon at all. – Nominal Animal Dec 9 '17 at 2:17
• @NominalAnimal Yes, that is okay to assume. – Gandalf Smith Dec 9 '17 at 2:18
• @NominalAnimal Would you mind elaborating on that a bit? I'm not quite sure how to properly make use of that information. Thanks! – Gandalf Smith Dec 9 '17 at 4:14

Consider the following illustration: The moving polygon is in blue, the stationary polygon in red, and the translation vector is the black arrow. On the left is the situation in original coordinates, on the right it is rotated so that the translation vector points to positive $x$ axis.

To find the distance the blue polygon needs to be moved along the vector, to come into contact (at one or more points, or at an edge; intersecting, but with the area of intersection zero) with the red polygon:

1. Rotate the system so that translation occurs on the $x$ axis, with increasing $x$ coordinates.

If $\vec{T} = ( T_x ,\, T_y )$ is the arbitrary-length translation vector, its length is $$T_d = \sqrt{\vec{T}\cdot\vec{T}} = \sqrt{T_x^2 + T_y^2}$$ If $\hat{u} = ( u_x ,\, u_y )$ is the translation vector scaled to unit length, i.e. $$\hat{u} = \frac{\vec{T}}{\left\lVert\vec{T}\right\rVert} = \frac{\vec{T}}{T_d}$$ then the rotation matrix $\mathbf{R}$ that rotates $\vec{T}$ to the positive $x$ axis is $$\mathbf{R} = \left [ \begin{array}{cc} u_x & u_y \\ u_y & -u_x \end{array} \right ]$$

To verify, consider $\mathbf{R}\hat{u} = ( u_x^2 + u_y^2 ,\, 0 ) = ( 1 ,\, 0)$.

(Below, all coordinates are in the rotated coordinate system; I do sometimes emphasize that as a reminder.)

2. Let $y_{min}$ and $y_{max}$ be the smallest and largest rotated $y$ coordinates, respectively, of the left/blue polygon; and $\gamma_{min}$ and $\gamma_{max}$ similarly for the right/red polygon.

If $y_{max} \lt \gamma_{min}$ or $y_{min} \gt \gamma_{max}$, the two polygons do not intersect at any point, when left/blue polygon is moved along the direction indicated by $\vec{T}$.

3. Using the rotated coordinates for both polygons, for each vertex in the left/blue polygon, find the point in the right/red polygon having the same $y$ as the vertex, and the smallest $x$ coordinate. (This boils down to finding $x$ coordinates at some specified $y$ coordinate, for all edges spanning that $y$ coordinate.) Calculate the difference in the $x$ coordinates (between the point in the right/red polygon, and the corresponding vertex in the left/blue polygon). Let the smallest of these differences be $L_1$.

4. Using the rotated coordinates for both polygons, for each vertex in the right/red polygon, find the point in the left/red polygon having the same $y$ as the vertex, and the largest $x$ coordinate. Calculate the difference in the $x$ coordinates (between the vertex in the right/red polygon, and the corresponding point in the left/blue polygon). Let the smallest of these differences be $L_2$.

5. Let $L$ be the smaller or $L_1$ and $L_2$, i.e. $$L = \min( L_1 ,\, L_2 )$$

6. When the left/blue polygon is translated by distance $L$, it comes into contact with the right/red polygon; "contact" meaning they intersect, but the area of intersection is zero.

If we use $\alpha\vec{T}$ to denote the translation into contact, then $$\alpha = \frac{L}{T_d}$$ because $$\alpha\vec{T} = L\hat{u} = L\frac{\vec{T}}{\lVert\vec{T}\rVert} = \frac{L}{T_d}\vec{T}$$

The above algorithm works for all polygons, including self-intersecting ones.

However, if the polygons are non-self-intersecting, with no degenerate (zero-length) edges, and are always drawn counterclockwise (or always clockwise), a lot of optimizations become available. In particular, only edges on the side towards the other polygon need to be considered; and checking the order of the rotated $y$ coordinates for the edge endpoints reveals which side it is on.

In practical programming terms, you can often speed up the implementation by creating a structure to represent each edge (containing the minimum rotated $y$ coordinate for the edge and the corresponding $x$ coordinate, the maximum rotated $y$ coordinate for the edge, and the inverse slope ($\Delta x / \Delta y$) of the edge in rotated coordinates), to make it as computationally cheap as possible to find a point on the rotated edge with a given rotated $y$ coordinate.

Essentially, if $(x_0 ,\, y_0)$ is the edge end point with smallest $y$ coordinate (in rotated coordinates, as always), $g$ is the inverse slope, $g = (x_1 - x_0)/(y_1 - y_0)$, and $y_1$ is the $y$ coordinate for the other edge end point, then $$x(y) = x_0 + g (y - y_0)$$ yields the $x$ coordinates corresponding to the specified $y$ coordinate on the edge, for $y_0 \le y \le y_1$.

If the edge is horizontal, $y_0 = y_1$, then the inverse slope $g$ can be set to zero, with $x_0$ set to the largest (left/blue polygon) or smallest (right/red polygon) $x$ coordinate in that edge. This way you can avoid division-by-zero, while still using only one edge structure without special cases, for all edges.

Finally, note that the intersection points and/or edges may be interesting to an application, for example if realistic collisions are to be approximated. I personally would consider storing the intersection points/edges as point pairs (from-to; with both being the same point for point contacts) in some sort of list, if asked by the caller. In C, I'd use something like

typedef struct {
double  x;
double  y;
} vec2d;

typedef struct {
vec2d   from;
vec2d   to;
} line2d;

typedef struct {
line2d *line;
size_t  count;     /* Number of lines defined */
size_t  max_count; /* Number of lines allocated */
} line2d_array;


with the caller specifying NULL if they are not interested in the intersections, and a non-NULL pointer to a line2d_array otherwise.

• I'm speechless. Your answer is absolutely amazing. Thank you so so much, it makes so much sense! I hope people that run into a similar situation get to see your answer. – Gandalf Smith Dec 9 '17 at 7:32
• (Off topic, but may I ask you for advice on how to best learn about these topics? I know my basic calculus and proofs, but not a whole lot more. And I can't take any classes on that matter either since my university schedule is quite packed already.) – Gandalf Smith Dec 9 '17 at 7:36
• @GandalfSmith: You're welcome. I am not a mathematician myself, just a computational physicist with interests in visualization and sonification. I rely very heavily on vector algebra, and a bit of linear algebra for rotation matrices (square orthonormal matrices), plus the properties of versors (unit quaternions describing rotations, easily converted to a rotation matrix) for orientations and interpolating between orientations/rotations. Many computer graphics books describe these, I believe, but you might wish to look into the older ones (rather than newest ones), [...] – Nominal Animal Dec 9 '17 at 8:34
• [...] to ensure you get into the math itself, and not just an overview of how to use some library. Before I had access to internet, I started reading on descriptive geometry topics in the library; afterwards, I've relied completely on internet, especially open articles on various algorithms described in Wikipedia and elsewhere... I really do not have any good book references for you. I also learned to program before University, on C64 (6502) and early IBM clones (80286 in my case, [...] – Nominal Animal Dec 9 '17 at 8:39
• [...] so I have similar difficulty in directing others towards good programming books (I mostly answer C questions on stackoverflow.com); in fact, the only one that I can really point to, is Weiss' Data Structures and Algorithm Analysis in C, which really helped me see how important data structure and algorithm design is -- any code optimization is just a tiny dusting of sprinkles on top, in comparison. – Nominal Animal Dec 9 '17 at 8:42