Point inside a polygon javascript

Question

I'm working in javascript finding that if the point i have is inside a polygon. I'm using ray-casting algorithm to compare that if the point is inside the polygon or not.

The algo is working perfect for some case. But for some case it show the point is outside even when the points are lying all inside the polygon.

!https://www.dropbox.com/s/rpxqnw9re3q6vsi/Screen%20Shot.png?dl=0

The area marked A1 is the parent polygon, and A2 and A3 are inside the parent polygon. Below the the function i'm using to check if the point is inside or not

function isPointInside(point, vs)
{
// ray-casting algorithm based on
var x = point[0], y = point[1];

var inside = false;
for (var i = 0, j = vs.length - 1; i < vs.length; j = i++)
{
    var xi = vs[i][0], yi = vs[i][1];
    var xj = vs[j][0], yj = vs[j][1];
    var intersect = ((yi > y) != (yj > y))&& (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
    if (intersect) inside = !inside;
}

return inside;
};

Below are the point array for the parent polygon as well as child polygons

 A1 Array 
0[0, 0] (2)
1[6096000, 0] (2)
2[6096000, 0] (2)
3[6096000, 6096000] (2) 
4[6096000, 6096000] (2)
5[0, 6096000] (2)
6[0, 6096000] (2)
7[0, 0] (2)
8[0, 0] (2)
9[0, 0] (2)


A2 Array (10)
 0[0, 0] (2)
 1[0, 3048000] (2)
 2[0, 3048000] (2)
 3[1524000, 3048000] (2)
 4[1524000, 3048000] (2)
 5[1524000, 0] (2)
 6[1524000, 0] (2)
 7[0, 0] (2)
 8[0, 0] (2)
 9[0, 0] (2)


A3 Array (10)
 0[4572000, 0] (2)
 1[4572000, 6096000] (2)
 2[4572000, 6096000] (2)
 3[6096000, 6096000] (2)
 4[6096000, 6096000] (2)
 5[6096000, 0] (2)
 6[6096000, 0] (2)
 7[4572000, 0] (2)
 8[4572000, 0] (2)
 9[4572000, 0] (2)

Why is that the points of A3 are not considered inside. Is there something wrong in the algo? Any help will be appreciated.

The algo, which I know works with convex polygons, so if you have some which is not convex polygon you have to split it into several convex polygons. Then to sort each polygon's point and iterate over it. Algorithm complexity is n*logn. Does this satisfy you and do you wish to describe it entirely? (It is about 2D, not 3D) — Kamen Stoykov, Apr 20 '16 at 06:40
it would be great if you can describe a little and i will find a way to split the polygon into several polygons — gurmandeep, Apr 20 '16 at 06:43
@lovechillcool I'm not aware of such. It shouldn't be that hard to implement it for rectangles though. Have a look at my answer below and just copy these JS functions. — Kamen Stoykov, Jul 05 '21 at 16:11

score 1 · Answer 1 · answered Apr 20 '16 at 07:03

Let's start with few utility functions.

First of them is area(Point, Point, Point). It takes as argument 3 points (order is very important). First and second point forms a vector and if 3th point if on the left side of this vector the function returns positive value, if 3th point is on the right side it returns negative value and finally if 3th point lays on the vector it returns 0.

function area(p1 , p2, p3) {
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
};

Next utility function is sortCMP(Point, Point), which is used as comparator while sorting each polygon points.

function sortCMP(p1, p2) {
    var result_area = area(target, p1 ,p2);
    if(result_area == 0.0) {
        return (sqrtDist(target, p1) - sqrtDist(target, p2) > 0.0)? 1 : -1;
    }
    return (result_area > 0.0)? -1 : 1;
};

Let's consider your polygon contains of N points from P1 to PN and they are stored in array named POINTS. In previous function (sortCMP) there is variable TARGET, which should be point with lowest X and Y coordinate among all points from P1 to PN.

Next function is sqrdDist, which actually returns the distance between 2 points

function sqrtDist(p1, p2) {
        var dx = p1.x - p2.x;
        var dy = p1.y - p2.y;
        return dx * dx + dy * dy;
};

So now let's back to the array names POINTS, which contains all points from your polygon. We have already found one which is with lowest X and Y coordinates (Target variable). Now we have to move it to be first element in the array and then sort the entire array but STARTING FROM ELEMENT WITH INDEX 1.

After the array is sorted we have just to iterate over it and check the area(Pi, Pi+1, T) returns always positive value (or 0 as well if you want to lay on the polygon itself). If somewhere area function returns negative value them the point T is always your polygon. Point T is point which you are testing if it is inside polygon.

As I said in my comment in order this to work your polygon should be convex polygon. This could be checked in the very last step of previous algorithm. So when you have all polygon's point sorted then you can check if area(Pi, Pi+1, Pi+2) always returns positive value (or 0) for all polygon's point. If it somewhere returns negative it will means that your polygon is not convex. When it returns negative value it will means also that Point with index i+1 is the point where you have to split your polygon. For more details you how exactly to split it maybe you have to search in google, because I can't remember right now.

Hope this will help you a little bit. If you have any further questions feel free to ask and I'll make my best to answer you during the day :)

Thank you very much Kamen, i will use you approach and hope that i get the result. — gurmandeep, Apr 20 '16 at 08:48

Point inside a polygon javascript

1 Answers1

Linked