Skip to content

Instantly share code, notes, and snippets.

@isedgar

isedgar/ray-casting.js

Created June 4, 2021 00:38
Show Gist options
  • Save isedgar/1f5c5b4cf34a43d4db15f9b4fe58b04f to your computer and use it in GitHub Desktop.
Save isedgar/1f5c5b4cf34a43d4db15f9b4fe58b04f to your computer and use it in GitHub Desktop.
Download ZIP
Check if a 2D point is inside 2D simple polygon. It works with convex and concave polygons.
Raw
ray-casting.js
function ray_casting(point, polygon){
var n=polygon.length,
is_in=false,
x=point[0],
y=point[1],
x1,x2,y1,y2;
for(var i=0; i < n-1; ++i){
x1=polygon[i][0];
x2=polygon[i+1][0];
y1=polygon[i][1];
y2=polygon[i+1][1];
if(y < y1 != y < y2 && x < (x2-x1) * (y-y1) / (y2-y1) + x1){
is_in=!is_in;
}
}
return is_in;
}
@Joseness123plays
Copy link

nice

@bardi-entel
Copy link

I've noticed that the edge between point[n-1] and point[0] is not taken into account. Please check this fixed version:

function rayCasting(point, polygon) {
    const n = polygon.length
    let isIn = false
    const x = point[0]
    const y = point[1]
    let x1, x2, y1, y2

    x1 = polygon[n-1][0]
    y1 = polygon[n-1][1]

    for (let i = 0; i < n; ++i) {
        x2 = polygon[i][0];
        y2 = polygon[i][1];

        if (y < y1 !== y < y2 && x < (x2 - x1) * (y - y1) / (y2 - y1) + x1) {
            isIn = !isIn;
        }
        x1 = x2
        y1 = y2
    }

    return isIn;
}

Best regards! Tamás

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment