0
$\begingroup$

i have watched numerous tutorials on implementing the SAT, but i think the math eludes me (as it usually does). Say, theoretically, that you are looping over each edge in a programming language, now you have the difference between one vertex and the preceding one, you have a vector. I am a little confused about why precisely this vector would have a bias in a specific direction... But anyway, let's say we have edge ->, now you want to somehow take each edge ->... and somehow make an axis for projection. I see some resources saying this should be the perpendicular line (swap components, invert one sign). I see other resources saying this should be the cross-product (cross-product doesn't make sense to me on a 2D polygon). I think the right answer would be to take the perpendicular ->.

now i lose the plot. Ok, so i expect the perpendicular -> to be away from all the other polygons, i expect that it must be offset to project all the vertices onto it (they must all be to its side). A lot of the time it isn't, like if it's an internal edge

enter image description here

but here is where i get massively confused. Say the edge is taken from the inside of Polygon A, and we normalize it to preserve the direction. I understand that if you take the origin of the normalized axis, and then project (using dot product) a vector from each vertex, this would allow you to... do something? i don't have the angle, and i also don't have any concept of how this would enable me to find the distance to a projected point on the axis.. for comparison / min max stuff.

enter image description here

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

First, we find directions perpendicular (or "normal") to the edges of each polygon ensuring that the perpendicular points outwards from that polygon and not into that polygon. The direction of the edge helps in getting the outward directed perpendicular.

What we do with this direction is to determine whether there is a gap between the two polygons along this axis/direction. Suppose for example, by good luck the direction turns out to be the $X$-axis. Then figuring out whether there is a gap is very simple. If the maximum $X$-coordinate of all the vertices of the left polygon is less than the minimum $X$-coordinate of all the vertices of the right polygon, then clearly there is a gap. We can draw a line parallel to the $Y$-axis in between the maximum $X$-coordinate of the left polygon and the minimum $X$-coordinate of the right polygon and this vertical line would separate the two polygons. Of course, we do not know which of the two polygons is on the left; so we try both possibilities in turn.

In general, we would not be so lucky that the perpendicular direction is parallel to one of the axes. But we can create a new system of axes: the $P$-axis parallel to the perpendicular and the $Q$-axis perpendicular to $P$. (The $P-Q$ coordinate system is just a rotation of the $X-Y$ coordinate system). The outward perpendicular from the polygon edge is now parallel to the new axis ($P$) and we can apply the method of the previous paragraph if we can figure out what would be the $P$-coordinates of each vertex (knowing only its $X$ and $Y$ coordinates). The answer is very simple: the $P$-coordinate is the dot product of the vector representing the vertex with the unit vector in the $P$-direction. (By the vector representing a vertex, I mean the vector from the origin to that vertex).

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.