Python version: kzfaq.info/get/bejne/osWFn6pe1Lzcpac.html

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

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

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

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

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

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

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

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

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.

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

Thank u, works nice

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

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

I wanted to create a buffer polygon from a linestring. Is it possible to get the coordinates of buffer polygon

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].

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.

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

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

can you show us the idnex.html code?

Excelent!!!!!

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

what is the essence of var x1 = side.a.x, var x2 = side.b.x, var y1 = side.a.y, var y1 = side.b.y, I have gone through the slide show but still can't understand. The rest of the code is very clear. Great work.

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

Pre-Edit: Thanks it works!!! really glad i found your video. After my original comment i will add some extra text Original comment: Well, for sure you have using some lib or functions made before, i'am really bad on coding geometry based stuff... you code i guess not will work, could please you tell the lib or how i convert into more math level code? i'am actually trying to check if circle is inside a polygon, i have done polygon against polygon, but i not understand exactly the dark magic on that code, i just test it and works, but i need to get a circle in polygon, what i did? i used another black magic i get that trys lines against circle and pass all lines of my polygon within the circle, but i already get a small circle inside the polygon that not are coliding because is inside but i want to colide, so, if i check center point of circle inside polygon it will work, but I really not understand how convert your video into code, i mean, the idea looks simples to understand but the logic behind it converted into code is not for me... thanks for helping... i will try myself but any help i will be even more glad Edit: Well i copy it to my code, i know it not will work properly, my code already has a function that return array of objects with x and y, soo i modify the function to receive center point as a object with x and y and a list of objects with x and y. Inside i modify the variables names to be more readable, i mean x, x1, x2, y, y1, y2 is hard to understand soo i shifted those to pointX pointY startLineX startLineY endLineX endLineY and used the same math principles, isIn i just add polygon so isInPolygon... it really work, i not sure exactly how it works at first, but works... i mean i understand the concept and the code, but i not understand the math portion of equation 100% after understanding better the logic i noticed that those validations check the point within all lines in a way that it keep shifting isInPolygon and get a better understand, the idea of the line getting horizontally sideways as in the video is burly to me in the code, but the position of the point relative to each line make some sense, if the point is totally below values of both startPoint and endPoint in Y axis it is already shutdown, but in the second part is really more wierd to udnerstand because it gets the diff between some stuff as endPointx - startPointX multiplied with the diference between centerPointY - startPointY and this get not sense to me, but to get even worst, this all is divided by endPointX - startPointX sum startPointX and this entire confusition is only compared to be bigger tham the value of centerPointX how those both maths works is the magic to me... i totally need to see step by step of this equation to maybe understand it better as happens to me when understand about circle against circle colision detection... you make de diff of X and diff of Y it creates a triangle without hypotenusa, soo you math down it, knowing how far you are from each other center point, beucase of circles is center point and radious if you sum radious of each circle and compare to hypotenusa of that triangle between both center point of each circle you know can totally tell if it is coliding or not, hypo < radious sum is coliding... even more complex math i got better when drawn step by step, my education in math is really por i just use rule of 3 to solve everthing on my academic life and not has any class of enginnery or geometry or anything that uses it. I just has logic thinking and thrist of knowlegde to reach my goals, and again thanks for you video, i not get it properly, but for sure it is why i could finally make my colision betwhen circle and polygon work... i'am creating a game in javascript and now can colide circles with circle squares with scare (axis aligned or not, because of polygon with polygon colision as well) circles with line and now point within polygons that finally complete my polygons with circles, because i just get all lines of my polygon and try the closest 2 points into a line to check my other function of line with circle colision if is not close enought i check using the function you posted here to finally check if the entire circle is inside the polygon i still have work to get it in better shape and increase performance, but already works, many thanks!!!

How to get intersection point (x,y)

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 😆

I 💖you

The explanation is great I just wonder why would yo use a ternary to return true or false for that kind of conditions instead of changing te conditional itself😂