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
I'am using circle based always get the futher point of the polygon then use it as a radius to make a cricle arround it and use circle based first, i know it is less performatic than boundaty box align with X and Y but i can make this step before circle if i want... But it is really cool
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.
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].
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 😆
Hi Vuvuzelo. If y2==y1, the point is outside because doesn't meet the first condition: y < y1 != y < y2 So the code won't read the "division by zero" error. Cheers!
Then you need a more robust algorithm because of rounding errors. Check this: en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm Robust method: github.com/mikolalysenko/robust-point-in-polygon
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.
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.
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!!!
@@SimonHalfSoul yeahhh, maybe... but i not even remember now why i did it that big... anyway it worked and my game now can do more fun collision stuff without lean into having a third party lib or something else LOL
@@viniciusschadeck4992 great it worked for you! I'm looking to implement something similar for an app for hunting, for a quick check whether my GPS location is whitin the property I am allowed to hunt on or not, based on property polygon.
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😂
![A Virtual World - JavaScript Course: Lesson 4 / 11 [Polygon Operations in JavaScript]](/img/n.gif)
Python version: ua-cam.com/video/l_UlG-oVxus/v-deo.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
I'am using circle based always get the futher point of the polygon then use it as a radius to make a cricle arround it and use circle based first, i know it is less performatic than boundaty box align with X and Y but i can make this step before circle if i want... But it is really cool
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.
Great video!! You have to continue doing these types of videos. They are amazing!
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].
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 😆
This is exactly what I was looking for. Thank you very much!
Thank you so much, great explanation. The Javascript code works fine. I hope I can write or translate to another programming language.
You;re very welcome 🙏
Hi! And what happens when Y2 == Y1?? With these values in the formula we are dividing by zero...
Hi Vuvuzelo. If y2==y1, the point is outside because doesn't meet the first condition:
y < y1 != y < y2
So the code won't read the "division by zero" error.
Cheers!
Fill the polygon. Check if the point is the fill color.
Totally agree, and those who write "I don't want a colored polygon" - no one tells you to display this color, just keep it on a virtual 👍
Can we use this for polygon selection using mouse? Let say if we click inside the polygon, the shape is selected
Sure 👍
how i can see the code running while i'm codding?
But how do we know in which direction the line should be drawn from the point?
It’s arbitrary .
how would i deal with a situation where the point is outside and the ray hits a corner?
Then you need a more robust algorithm because of rounding errors. Check this: en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm
Robust method: github.com/mikolalysenko/robust-point-in-polygon
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.
Thank you very much for your comment. I'll keep in mind the barycentric coordinates video. Cheers.
did u figure it out?
and if we want to get points as inside if they are at line of polygon?
Hello. I must do the same but on a Google map. Can I replace x = lat and y=lng?
Yes. But only for small areas of the map (convert lat long to x y first).
can you show us the idnex.html code?
And style.css code
Hi, great video! What is that functions renderPolygon() renderPoint() etc... How could I get it?
Thank you. Those functions are just for visual aid, they are not important for the purpose of the video
@@EdgarProgrammator ok, thanks you are very pleasant, what would you recommend for drawing such polygons and others?
@@yaroslavvaskiv6315 SVG.js
svgjs.dev/docs/3.1/
Thank u, works nice
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.
Segment AB; A and B are vertex points.
A = (x1,y1), B = (x2, y2)
@@EdgarProgrammator You could have assigned them without mapping to an object. I'm guessing you did it for readability for the viewers?
@@IhsanMujdeci exactly, that was my intention.
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!!!
Holy, there must have been a more concise way to write this comment.
@@SimonHalfSoul yeahhh, maybe... but i not even remember now why i did it that big... anyway it worked and my game now can do more fun collision stuff without lean into having a third party lib or something else LOL
@@viniciusschadeck4992 great it worked for you! I'm looking to implement something similar for an app for hunting, for a quick check whether my GPS location is whitin the property I am allowed to hunt on or not, based on property polygon.
I wanted to create a buffer polygon from a linestring.
Is it possible to get the coordinates of buffer polygon
Hello jasmeet singh virdi. If you mean the "outline" of a polygon, take a look at this: pomax.github.io/bezierjs/#outline
Cheers :)
@@EdgarProgrammator
I think offset is what I am looking for.
Will explore more on it.
Thanks
@@jasmeetsinghvirdi77 You are very welcome !
are the (X,Y) points written as (Lat,Lon) ?
No, they are Cartesian coordinates.
Can i check if there is a polygon ( with lat and lng) are crossing another polygon ?
do you mean polygon intersection ? for each segment line of the polygons do a two-line intersection check...
@@EdgarProgrammator yeah that will work but it s not really efficient, you should check out the SAT or the Gjk algorithm
@@papesldjnsjkfjsn Thank you for the suggestion ! I will take a look
Excelent!!!!!
Thank you!
How to get intersection point (x,y)
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😂