5

I'm trying to learn the Separating Axis Theorem, for my programming. I'm making a simple 2D game an I need this as a way to detect wether two polygons are intersecting.

Problem is, I suck at math.

So far, I understand that in order to know if two polygon are intersecting, I need to do the following:

  1. Creata a perpendicular line to every edge of the two polygons.
  2. Project each polygon to each of the new lines created (the axes).

If all projections of the first polygon overlap all projections of the second polygon, the shapes intersect. Else, the shapes do not intersect.

I know how to do step 1. But I don't understand how to perform step two.

Can you explain to me how to project a polygon onto an axis, in a language that a person with pretty basic knowledge at math will be able to understand?

Thanks a lot

user3150201
  • 543
  • 2
  • 5
  • 15

2 Answers2

1

I know this is a 5 year old post, and the answer will probably not be relevant or seen by the original poster, but I'll answer anyway.

Any kind of computational geometry will require knowledge of vectors, dot product and parallelogram area, all expressed with coordinates (pairs of $x$ and $y$). For projection, you need to express the line with an initial point $P$ (midpoint of the edge) and the unit vector $\vec{v}$ that points perpendicular to the edge. Then, each edge of the other polygon can be projected by projecting all the vertices. If projection of $A$ to the line is called $A'$, then the distance $PA'$ can be written as $\vec{PA}\cdot \vec{v}$ (dot product of the vector $PA=A-P$ to the line direction).

Anyway, in most such cases, the first step is to find an algorithm that does what you want. In this case, intersection of two polygons is a basic operation needed by all graphics code in any software package (vector graphics software, rendering on screen, cropping and clipping,...). The described algorithm seems strange, the most straight forward would just be to check if any pair of the edges intersect, so you just need a test for intersection of two line segments. For more, read related answers.

orion
  • 15,781
1

Projecting is a bit like casting a shadow. In this case, if you're looking at the $x$ and $y$ axes, the projections would be the shadow the object would create on the axes if you shined a flashlight behind the object.

Let's say one of your sides goes from $(2,2)$ to $(5,7)$. The projection onto the $x$ axis would be the line segment going from $x=2$ to $x=5$ on the $x$ axis. The projection onto the $y$ axis would be the line segment going from $y=2$ to $y=7$ on the $y$ axis.

Sometimes the projection is meant just to be the length of the shadow.

The more general approach involves taking the two endpoints, and dropping perpendiculars to the axis from those endpoints. The projection is defined by the place where those perpendiculars intersect the axis.

John
  • 26,319