Check if a point is inside a polygon | JavaScript code

Algorithm to test whether a point is inside or outside a polygon

Ray Casting algorithm explanation with JavaScript

[amina]

I recommend to check each point to be in bonding box and then use ray casting for points in bonding box,
you will get better performance especially if most of the points are outside of bonding box

[plasticentmn]

This is exactly what I was looking for. Thank you very much!

[___dp]

Great video!! You have to continue doing these types of videos. They are amazing!

[jwstolk]

If the polygon uses floating point coordinates, you may get incorrect intersect counts when the ray crosses very close to a vertex. This is most likely when the polygon has concave sections and the ray touches a concave point without actually crossing the line at that concave point, just touching it. If the segments can be curved, like an arc, the intersect calculations will have even more rounding errors. As a solution, you could choose one of the other 3 directions, or point the ray at a random angle, until it travels without getting too close to any vertex or tangent point of an arc segment.
To speed it up, you typically divide the space into a grid and for each cell, list all the line segments that are (partially) within that cell. for each cell you define a point in the center of the cell, and save the inside/outside state of that point. Then for each tested point, you choose the corresponding cell, if the cell has no line segments, the state of the center of that cell is your answer. If the cell has line segments, you draw a ray from the test point to the known center point of the cell, and count only the number of intersects with the listed line segments. add 1 if the cell center had an "inside" value. You may have additional rounding errors: if the cell center is very close to a line segment, choose a different reference point. To correctly handle test points very close to a cell edge, also list line segments very close to a cell in that cell (that should be very rare, so does not affect the speed) The calculation speed for test points will only depend on the average number of lines listed in each cell, which for many cells is zero, if the grid resolution is high enough.

[eemilwallin]

I tried implementing this with Python and failed whilst trying to listen to authority even though I had my qualms. In pure mathematics you always need parentheses, and the "clean and nice way" which I am really bad at, is not correct. I am of course talking about y < y1 != y < y2. I believe the implied evaluation in python goes like this.

y < y1 is either true or false. Then due to lax typing, true or false is not equal to y. And finally we compare it to y2. When the intended behaviour is to use parentheses to see (y < y1) != (y < y2). I am actually in awe that JavaScript allows this behaviour as is, either it is smarter or then it has some sort or arbitrary evaluation when it comes to operators. I think this was pointed by codegolfer.

Nevertheless Edgar I thank you for your tutorial. As others pointed out you can choose to append the first element to be also the last element. I like to do a lot of clauses (bad practice, this is why I am watching tutorials), so a clause if i != n+1 then we go as planned, but else we set the elements of b (x, y) from polygon[0].

[rogeriodias]

and if we want to get points as inside if they are at line of polygon?

[cesarl.c.]

Thank you so much, great explanation. The Javascript code works fine. I hope I can write or translate to another programming language.

[vuvuzelomcbubbles]

Hi! And what happens when Y2 == Y1?? With these values in the formula we are dividing by zero...

[teusocost]

how i can see the code running while i'm codding?

[awekeningbro]

But how do we know in which direction the line should be drawn from the point?

[azamd]

Can we use this for polygon selection using mouse? Let say if we click inside the polygon, the shape is selected

[redghost]

how would i deal with a situation where the point is outside and the ray hits a corner?

[Trekiros]

Thank you for the very clear video & graphic explanation, but dear god is the javascript ugly here. Way too many unnecessary variables (which use the var keyword, instead of let or const), no array functions, a super confusing if statement, and then at the end you do a ternary operator to return... the exact same value as your ternary's condition? 🤯
This is why math folks and computer folks can never get along. And I say this as both a math folk and a computer folk, so I'm very much part of the problem 😆

[santiagocastro]

Hello. I must do the same but on a Google map. Can I replace x = lat and y=lng?

[arunu]

Thanks a lot for superb information. Can you pls show a video on barycentric coordinates to find a point inside triangle. Is it better than ray casting? Pls continue videos on computational geometry.

[jasmeetsinghvirdi]

I wanted to create a buffer polygon from a linestring.

Is it possible to get the coordinates of buffer polygon

[samuelribeiro]

Can i check if there is a polygon ( with lat and lng) are crossing another polygon ?

[carlosdavila]

are the (X, Y) points written as (Lat, Lon) ?

[yaroslavvaskiv]

Hi, great video! What is that functions renderPolygon() renderPoint() etc... How could I get it?

[ernststravoblofeld]

Fill the polygon. Check if the point is the fill color.