Javascript collision of two point array polygons

Question

I have searched all over, and I have found answers for rectangle circle and sprite collisions. Nothing that provides collision detection between two arrays of points like for example,

var poly1=[
    [0,0],
    [20,50],
    [50,70],
    [70,20],
    [50,0]
];
// each point from one to the next represent a line in the shape, then the last point connects to the first to complete it.
var poly2=[
    [50,30],
    [40,90],
    [70,110],
    [90,70],
    [80,20]
];
var collided=arraysCollided(poly1,poly2);

Does anyone know of a library that can do just this? My research has come up with nothing that supports just that, and isnt associated with some game engine library.

For example a collision is triggered true when one or more points is inside the polygon of the other.

what is considered a collision, can you provide some desired outputs along with your inputs? — Rick, Jun 06 '17 at 03:02
If one of the points of one of the polygons is "inside" or "touching" the other we could say they collided (depending your definition). Do you agree? Ok, if you do, now you need to solve a [point and polygon collison](https://stackoverflow.com/a/13217508/402022). — Theraot, Jun 06 '17 at 03:08
True but that still provides just for a rectangle, not a as you could say eformed polygon, like those two in the question. — ModerateJavaScriptDev, Jun 06 '17 at 03:10
The linked solution was for a point and a polygon (I assure you, as I said in that answer, I provided a general solution). Although, after consideration, I see you can create intersecting polygons without placing vertex of one inside the other. The SAT approach looks promising, although I don't know how ti would work for arbitrary polygons. I propose something else: if a segment from one polygon intersects a segment of the other they collide. Otherwise, the polygons are either not touching or one is completely inside the other, then testing for a point can discriminate those cases. — Theraot, Jun 06 '17 at 03:42
Divide your polygons into triangles and run the algorithms on each triangle in comparison with the other group (don't run the algorithm on triangles of the same group/polygon) — Elie Nassif, Jun 06 '17 at 06:33
This library seems to fix your problems http://jriecken.github.io/sat-js/ and is pretty lightweight — Imbue, Jun 06 '17 at 07:22
sat.js got it for me, thank you, https://cryogena.net/iwork/ @Imbue put as an answer :D — ModerateJavaScriptDev, Jun 06 '17 at 12:15

score 0 · Accepted Answer · answered Jun 06 '17 at 12:33

SAT.js was the anser for me, I just put every point into SAT.Vector then into SAT.Polygon, then test them with SAT.testPolygonPolygon(SAT.Polygon,SAT.Polygon);

var poly1={
    name:"poly2",
    x:400,
    y:60,
    rotation:0,
    runner:function(){

    },
    points:[
        [20,-50],
        [-30,-50],
        [-30,30],
        [10,60],
        [50,20]
    ]
};
var poly2={
    name:"poly2",
    x:50,
    y:70,
    runner:function(){
        this.x+=1;
    },
    points:[
        [-20,-40],
        [-60,50],
        [10,70],
        [50,30],
        [30,-20]
    ]
};
pGon=(poly)=>{
    var center=SAT.Vector(0,0);
    var pts=[];
    for(var i in poly.points){
        var point=poly.points[i];
        // point = [0:x,1:y]
        pts[pts.length]=new SAT.Vector(point[0]+poly.x,point[1]+poly.y);
    }
    var poly_a=new SAT.Polygon(center,pts);
    return poly_a;
};
pCollide=(p1,p2)=>{
    var p1_poly=pGon(p1);
    var p2_poly=pGon(p2);
    var res=new SAT.Response();
    var collided=SAT.testPolygonPolygon(p1_poly,p2_poly,res);
    console.log(collided);
    console.log(res);
    return collided;
};
var collided=pCollided(poly1,poly2);

With that, it maps each point to a polygon on the coordinate system, then tests it from there. So collided = true

score 0 · Answer 2 · answered Feb 22 '20 at 18:39

I checked for if each point of each polygon is in the other polygon. This is the code for checking if a point is in a polygon:

function pip(x, y, polygon) {
let odd = false;

let v = polygon.va; //The vertices array
let j = v.length - 2;

for (let i=0; i<v.length-1; i+=2) {
    if ((v[i+1]<= y && v[j+1]>=y ||  v[j+1]<= y && v[i+1]>=y)
        && (v[i]<=x || v[j]<=x)) {
          odd ^= (v[i] + (y-v[i+1])*(v[j]-v[i])/(v[j+1]-v[i+1])) < x; 
    }

    j=i; 
}
if(odd === false) odd = 0;
    return odd;
}

I got this from Here, but modified it to work for an array like this [x1,y1,x2,y2,x3,y3...]. To make it work for x,y pairs, you would just change the for loops modifier thing and look at polygon.va[i][0] as x and polygon[i][1] as y.

Javascript collision of two point array polygons

2 Answers2