Rotate a rectangle until it hits a triangle, and determine the point of intersection

Question

This problem is in 3D space.
There is a rectangle, defined by 4 vertices. We rotate it around one of its sides.
There is a triangle, defined by 3 vertices.
After a full 360 degree rotation, will the rectangle ever intersect/touch the triangle?
If so, what is the angle of rotation at which intersection first occurs? And what is the point of this first intersection?

After thinking about this for a while, it seems like there are 3 main cases:

triangle vertex touches rectangle surface
triangle surface touches rectangle vertex
triangle edge touches rectangle edge

And there are 2 unlikely cases where the two are perpendicular when the intersect:

rectangle edge hits triangle surface
rectangle surface hits triangle edge

However identifying these cases hasn't really gotten me closer to a solution. I'm hoping someone can point me in the right direction for how to solve this problem. I want to solve it fast for a small number of rectangles x a large number of triangles.

Context: the larger problem I'm trying to solve is I want to wrap a rectangle around a closed polygonal mesh. I wish to do this step by step by rotating the rectangle until it intersects, then rotating the remaining rectangle around the intersection point, etc.

welcome to SO, we don't do any kind of homework for people, just help them out if they're stuck. post your code, let us see what you attempted to do so we could better point you to a solution — svarog
@svarog Hey, this isn't homework, sorry if it seems that way ): I've been thinking about this all day with no progress, which is why I posted here. I don't have any code yet because I haven't thought of any approaches to try. I'm not really looking for code either, I'm mainly looking for someone to point me towards an algorithm for this task or a similar task. — Jordan

M Oehm M Oehm · Accepted Answer · 2015-11-12T10:23:54

When you rotate a rectangle around one of its sides, you get a cylinder. Intersect each of the lines with the cylinder. The position of the intersection points gives you the rotation angles. Since this doesn't catch the case where the triangle is completely contained within the cylinder, test whether the vertices' distance to the cylinder's axis is smaller than the cylinder's radius, too.

Say your rectangle has the vertices A to D. You want to rotate around the side AB. The radius of your cylinder is then r = |AD|.

First, transform the coordinates so that the rectangle is placed with the side that you want to rotate about along the z axis and the adjacent side along the x axis.

A′ = {M} · A = {0, 0, 0}
B′ = {M} · B = {0, 0, |AB|}
C′ = {M} · C = {r, 0, 0}

Apply the same transformation {M} to the vertices of the triangle.

Now find the intersections of all three sides of the triangle with the cylinder. Because the cylinder is aligned to the z axis, the problem can be separated into two subproblems: (1) Find any intersections with the top and bottom surfaces a z == 0 and z == |AB|. (2) Find the intersections with the "coat" of the cylinder; this is the intersection of a line with a circle in the xy plane.

You can then calculate the rotation angles with the tangent function of the y and x coordinates of these points as atan2(y, x).

If you need the coordinates of the intersection points in the original coordinates, don't forget to undo the transformation.

Rotate a rectangle until it hits a triangle, and determine the point of intersection

1 Answers