Point Inside A Polygon Javascript

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

Solution 1:

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.

functionsortCMP(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

functionsqrtDist(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 :)