##### Polygon Triangulation With Separating Axis Theorem

I'm learning the Separated Axis Theorem for 2D collisions and response. I want to support collisions with concave polygons, so I'm triangulating polygons using earcut and testing each triangle against each other.

Unfortunately, it still seems to treat concave polygons as if they were convex, for example, given the coordinates `(0, 0)`

, `(0, 50)`

, `(40, 50)`

, and `(10, 40)`

, collisions behave as if the `(10, 40)`

point was not there, effectively making it a triangle. I checked the triangulated coordinates and they appear to be normal: `[1, 0, 3, 3, 2, 1]`

(each number representing the index of the point).

Additionally, my SAT implementation returns false the moment it finds non-overlapping "shadows", but by checking the each of the triangles against each other, individual triangles could be non-overlapping while their parent polygon is colliding. A similar problem is also present in response, where I am grabbing the smallest overlap difference and pushing the collider back, but the smallest overlap with individual triangles might not represent the true overlap amount.

How do I fix both these issues?

**Triangulation**

```
triangulate(){
let pvertices = [];
for(let v of this.vertices){
pvertices.push(v.x, v.y);
}
this.tpoints = earcut(pvertices); // triangulated vertices
this.tsub = []; // triangulated polygons for collision
for(let i = 0; i < this.tpoints.length; i+=3){
this.tsub.push([this.vertices[this.tpoints[i]], this.vertices[this.tpoints[i+1]], this.vertices[this.tpoints[i+2]]]);
}
}
```

**Collision detection**

```
let sprite1 = this;
let sprite2 = cand;
for (let sprite = 0; sprite < 2; sprite++) {
if (sprite == 1) {
// flip to avoid repetitive code
sprite1 = cand;
sprite2 = this;
}
for(let s = 0; s < sprite1.tsub.length; s++){
for (let a = 0; a < sprite1.tsub[s].length; a++) {
const b = (a + 1) % sprite1.tsub[s].length;
// normal to sprite edge (axis projection)
const ap = new Vector(-(sprite1.tsub[s][b].y - sprite1.tsub[s][a].y), sprite1.tsub[s][b].x - sprite1.tsub[s][a].x);
// find min max for both sprites
let min1, max1, min2, max2;
for (let t of sprite1.tsub) {
for(let p of t){
let q = ap.dot(p);
min1 = Math.min(min1 ?? q, q);
max1 = Math.max(max1 ?? q, q);
}
}
for (let t of sprite2.tsub) {
for(let p of t){
let q = ap.dot(p);
min2 = Math.min(min2 ?? q, q);
max2 = Math.max(max2 ?? q, q);
}
}
if (!(max2 >= min1 && max1 >= min2))
return false;
}
}
}
return true;
```

**Voters**

can i give you the function i use

i didn't write it, but i use it.

@Coder100 ok

@realTronsi

@Coder100 where is concave handling occurring?

uh

from what i can tell apparently it doesn't need it let me find the article explaining how it was made @realTronsi

@Coder100 it looks to be using something similar to or is SAT, which only works for convex. The source article would be helpful thanks

http://www.dyn4j.org/2010/01/sat/ @realTronsi

@Coder100 could you create a simple demo to show concave collisions with the provided code? The article does not handle concave polygons anywhere in the code

ok @realTronsi