# SAT Collision: Spaces between polygons in collision

by fsdss   Last Updated January 14, 2018 03:13 AM

I tried to implement SAT collision for my program, however, when ever there is a angled line in either polygons (all convex), collision detection does not work properly. I even tried two different ways of coding the algorithm, but I ended up with the same results. Both implementations follow a tutorial, but it doesn't seem to work for me.

Here is an image to show what I mean:

``````public class SAT2 {
public static boolean collide(Shape p1, Shape p2) {

Vector2d[] p1Vertices = p1.getVertices();
Vector2d[] p2Vertices = p2.getVertices();

Vector2d[] p1Edges = getEdges(p1Vertices);
Vector2d[] p2Edges = getEdges(p2Vertices);

for (int i = 0; i < p1Edges.length; i++) {

//get normal
Vector2d axis = p1Edges[i].perp(true);

double[] a = project(p1, axis);
double[] b = project(p2, axis);
if (!overlap(a, b)) {
return false;
}
}

for (int i = 0; i < p2Edges.length; i++) {
Vector2d axis = p2Edges[i].perp(false);
double[] a = project(p1, axis);
double[] b = project(p2, axis);
if (!overlap(a, b)) {
return false;
}
}

return true;
}

private static boolean contains(double n, double[] range) {
double a = range[0];
double b = range[1];
if (b < a) {
a = b;
b = range[0];
}
return (n >= a && n < b);
}

private static boolean overlap(double[] a, double[] b) {
if (contains(a[0], b)) return true;
if (contains(a[1], b)) return true;
if (contains(b[0], a)) return true;
if (contains(b[1], a)) return true;
return false;
}

private static Vector2d[] getEdges(Vector2d[] vertices) {
Vector2d[] edges = new Vector2d[vertices.length];

for (int i = 0; i < vertices.length; i++) {
Vector2d vc = vertices[i];
Vector2d vn = vertices[(i + 1) == vertices.length ? 0 : (i + 1)];
edges[i] = Vector2d.sub(vc, vn);
}

return edges;
}

public static double[] project(Shape p, Vector2d axis) {
Vector2d[] vertices = p.getVertices();
axis.normalize();

double min = Vector2d.dot(vertices[0], axis);
double max = min;

for (int i = 0; i < vertices.length; i++) {
double proj = Vector2d.dot(vertices[i], axis);
if (proj < min) {
min = proj;
}

if (proj > max) {
max = proj;
}
}

return new double[] {min, max};
}
}
``````
Tags :