Fastest way of calculating the projection of a polygon onto a line

Question

Recently I have started doing some research on the SAT (Separating Axis Theorem) for collision detection in a game I am making. I understand how the algorithm works and why it works, what I'm puzzled about is how it expects one to be able to so easily calculate the projection of the shape onto different axes.

I assume the projection of a polygon onto a vector is represented by line segment from point A to point B, so my best guess to find points A and B would be to find the angle of the line being projected onto and calculate the min and max x-values of the coordinates when the shape is rotated to the angle of the projection (i.e. such that it is parallel to the x-axis and the min and max values are simply the min and max values along the x-axis). But to do this for every projection would be a costly operation. Do any of you guys know a better solution, or could at least point me to a paper or document where a better solution is described?

Answer 1

Simple way to calculate the projection of the polygon on line is to calculate projection of all vertex onto the line and get the coordinates with min-max values like you suggested but you dont need to rotate the polygon to do so.

Here is algorithm to find projection of point on line :-

line : y = mx + c
point : (x1,y1)

projection is intersection of line perpendicular to given line and passing through (x1,y1)

perdenicular line :- y-y1 = -1/m(x-x1)     slope of perpendicular line is -1/m

y = -1/m(x-x1) + y1

To find point of intersection solve the equation simultaneously :-

y = mx + c , y = -1/m(x-x1) + y1

mx + c = -1/m(x-x1) + y1

m^2*x + mc = x1-x + my1

(m^2+1)x = x1 + my1 - mc

x = (x1-my1 - mc)/(m^2+1)
y = mx + c  = m(x1-my1-mc)/(m^2+1) + c

Time complexity : For each vertex it takes O(1) time so it is O(V) where V is no of vertex in the polygon

Answer 2

If your polygon is not convex, compute its convex hull first.

Given a convex polygon with n vertices, you can find its rotated minimum and maximum x-coordinate in n log n by binary search. You can always test whether a vertex is a minimum or a maximum by rotating an comparing it and the two adjacent vertices. Depending on the results of the comparison, you know whether to jump clockwise or counterclockwise. Jump by k vertices, each time decreasing k by half (at the start k=n/2).

This may or may not bring real speed improvement. If your typical polygon has a dozen or so vertices, it may make little sense to use binary search.