Collision Detection: Separating Axis Theorem

To put it simply:

• A vector, “vector,” also called a vector, is a quantity that has magnitude and direction, such as acceleration and force.
• A scalar has only a quantity of magnitude, such as time or temperature.

In geometry, vectors are represented by directed line segments as follows:

Vector V calculation method:

• V = C2 – C1
• V = (7-3, 7, 2)
• V = (4, 5)

Normal vector: The perpendicular vector of a vector, swapping the x and y components, and then inverting the x component of the coordinate. The normal vector to V up here is minus 5,4.

Convex polygon

When a straight line passes through a Polygon, the Polygon is to Convex Polygon if it intersects the Polygon no more than twice.

Concave polygon

When a straight line passes through a Polygon, if the line intersects the Polygon more than twice, the Polygon is Concave Polygon.

With the above principle, the following problems need to be considered when converting into an algorithm:

1. How do I get all the potential sub-axes?
2. What is the basis of projection overlap?

Question 1

The answer to the first question, based on research, is that in 2D, all the potential splines are normals to each edge of the shape.

A normal is simply a normal vector with no direction. This is described in the previous knowledge points. Here is an approximate logical implementation:

const vertices = [] // Set of coordinates for vertices, assuming values already exist
const axes = [] // Store the splitter
const verticesLen = vertices.length;

for (let i = 0; i < verticesLen; i++) {
  const p1 = vertices[i];
  const p2 = vertices[i + 1 == vertices.length ? 0 : i + 1];
  // Find a vector algebraic representation of each edge. Step 27 Subtract p1 from P2
  const edge = subtract(p1,p2);
  (x, y) => (-y, x) or (y, -x)
  const normal = normalAxes(edge);
  axes.push(normal);
}
Copy the code

Question 2

In the above introduction to SAT, it can be clearly observed in the diagram that in the algorithm implementation, all vertices and sub-axes of the shape need to be traversed to perform the dot product, and the minimum and maximum values can be obtained by comparison. Then mark the minimum and maximum values roughly on an axis to see if there is any overlap.

Here is an approximate logical implementation:

Suppose we have polygons A and B.

const verticesA = []; // Set of all vertex coordinates of A shape
const verticesB = []; // Set of coordinates for all vertices of the B shape
const axes = [] // Store all the subaxes obtained
const axesLen = axes.length;

for (let i = 0; i < axesLen; i++) {
  const separateAxes = axes[i];
  // The getProject method gets the maximum and minimum values of the projection
  const projectA = getProject(separateAxes,verticesA);
  const aMin = projectA.min;
  const aMax = projectA.max;
  const projectB = getProject(separateAxes,verticesB);
  const bMin = projectB.min;
  const bMax = projectB.max;
  // The projection overlaps.
  if ( (aMin <= bMax && aMin >= bMin) || (bMin <= aMax && bMin >= aMin) ) {
    continue;
  } else {
    return false; }}Copy the code

validation

According to the above idea, take the upper left corner of the web page as the origin of coordinates, the horizontal left as the X-axis, and the vertical down as the Y-axis. Describe coordinate points in terms of CSS units.

This is the test page, the mobile terminal is as follows:

In the above test page, unoverlapped projection data is taken as an example, and the detected data is projected onto an axis:

You can see there’s no overlap.