Simple and fast algorithm, but it has one small edge case (literally). This code behaves inconsistently when the point is located on one of the polygon's edges : some edges will count as inside, and others will count as outside. To fix this : check whether the point is on any of the edges before actually running this algorithm.
Hey, this is kinda weird, but I was doing a programming challenge and you needed to know where a certain point needed to be in a list of coordinates for a polygon. This video helped a lot, and the solution worked like a charm. Keep up the good work
I was thinking to check where point lines relative to each vector representing polygon side, it is also O(n) (in worst case) time and it works faster than above algorithm since it don't have to iterate through each side of polygon,
Awesome. I watch searching for an explanation on ray casting and yours was perfect. Now, I have a different problem to solve. I want to generate the shape of a city starting from a rectangle and want to morph semi-randomly in a way that it contains some Point of Interest (POI) while it excludes Points of Avoidance (POA). Any Idea as to how to do this smartly; without checking each time if every single deformation left some POI out or let some POA in?
I'd say a proper and rigorous implementation that works for ANY points and polygon is RIDICULOUSLY difficult for what it acheives. I'm not talking about the edge cases "what if you select a point on the edge", I'm talking about the (very annoying edge case) where the raycast intersect with a vertex of the polygon. In that case, you have no choice but to pick another random direction, and then the math become way more difficult and messy. Also you need to run tons of test to avoid division by 0. Thankfully there are some workarround. If you can ensure that your polygone coordinates are integers, then just offset the y raycast coordinate by 0.5.
If y2 == y1, it means that you have a horizontal line, then you can check if your point is on this line too or not. if y2 == y1, check if yp == y1 (or == y2, both are equal), if yes, your point is on the same direction as the line y1 == y2, and then you can check the x-condition. If x-condition is also satisfied, it means that your point is on the edge itself. It's up to you if you want the points on the edge to be included in or not. If you wanted it included, increment the counter
Yes that's right, but in this case will we count the point intersection twice and it will be even, for example a point in a square if we count it with the four edges it will be 4, is that right? so it is outside but if we only calculate the intersection with left edge for example it will be odd then it is inside @@insidecode
Discover the new graph theory algorithms course: inscod.com/graphalgo
🔴
/ \
🔵-🔴
| |
🔴-🔵
That even/odd technic blew my mind, I never expected the method to be simple yet genius at the same time
Me neither
Simple and fast algorithm, but it has one small edge case (literally).
This code behaves inconsistently when the point is located on one of the polygon's edges : some edges will count as inside, and others will count as outside.
To fix this : check whether the point is on any of the edges before actually running this algorithm.
No sound???
Hey, this is kinda weird, but I was doing a programming challenge and you needed to know where a certain point needed to be in a list of coordinates for a polygon. This video helped a lot, and the solution worked like a charm. Keep up the good work
adventofcode 2023 Day 10 pipe maze ?
@@WeloveKoora Yeah, haha, did you also use the same method?
@@hhkl3bhhksm466 Yes, after 24 hours of searching hhhhh
@@hhkl3bhhksm466 it was very challenging problem, but i learned a lot
Thank you. This worked so well. I've been beating myself up trying to think of a solution.
I was thinking to check where point lines relative to each vector representing polygon side, it is also O(n) (in worst case) time and it works faster than above algorithm since it don't have to iterate through each side of polygon,
Awesome. I watch searching for an explanation on ray casting and yours was perfect. Now, I have a different problem to solve. I want to generate the shape of a city starting from a rectangle and want to morph semi-randomly in a way that it contains some Point of Interest (POI) while it excludes Points of Avoidance (POA). Any Idea as to how to do this smartly; without checking each time if every single deformation left some POI out or let some POA in?
I'd say a proper and rigorous implementation that works for ANY points and polygon is RIDICULOUSLY difficult for what it acheives. I'm not talking about the edge cases "what if you select a point on the edge", I'm talking about the (very annoying edge case) where the raycast intersect with a vertex of the polygon. In that case, you have no choice but to pick another random direction, and then the math become way more difficult and messy. Also you need to run tons of test to avoid division by 0.
Thankfully there are some workarround. If you can ensure that your polygone coordinates are integers, then just offset the y raycast coordinate by 0.5.
just got a homework where I need to check if a point is inside a polygon, thx :D
what if y2 - y1 = 0 for the 2nd cond? Do we just ignore that count?
If y2 == y1, it means that you have a horizontal line, then you can check if your point is on this line too or not. if y2 == y1, check if yp == y1 (or == y2, both are equal), if yes, your point is on the same direction as the line y1 == y2, and then you can check the x-condition. If x-condition is also satisfied, it means that your point is on the edge itself. It's up to you if you want the points on the edge to be included in or not. If you wanted it included, increment the counter
@@fnxph03n1x if y2 == y1 then the first condition ( (yp < y1) != (yp < y2) ) will never be True, so the second condition will not be evaluated.
How about case y1 = y2
...do you have link to the world timezones vertex defined database?..for automatic local GPS clock decoder
4:55 You didn't handle divide by zero case.
what if ray passes through polygon corner?
I think that it will count once
@@insidecode what if the point is outside of a concave quadrilateral, we cast a line along the x - axis, and the line passes through a vertex?
Does this work for bodies in 3D space?
Nice video thanks. Could you upload the same video for 3D non convex o bjects? :)
Thanks, but why to check the intersection of the point with each edge? isn't it enough to check for one direction and the equilivant edges?
But how to know the edges of that directon?
Yes that's right, but in this case will we count the point intersection twice and it will be even, for example a point in a square if we count it with the four edges it will be 4, is that right? so it is outside but if we only calculate the intersection with left edge for example it will be odd then it is inside
@@insidecode
Why would we count the intersection twice?
@@insidecode I mean ehen we loop through each edge of the shape when the point is inside it will be counter 4 times if the shape is square
No we increment the counter only when there's an intersection
Thank you very much, great video! :)
Hi sir, I made a net simulation, how do I know that the particles are inside the net?
Check out "Determining if a point lies on the interior of a polygon" by University of Michigan. It's on google
Great video, thanks!
It very useful🎉
is it possible to generate all the points inside the polygon, if the polygon is represented by vertices
There is an infinity of points inside a polygon
Thanks!
Does anyone know if there is an easy extension to 3D ?
Project you shape to 2D plane and then try this method.
some shapes must be treated with their own condition: like circles, rectangles, triangles...
Nope, they don't
@@colefrankenhoff1428 they don't if you are bad programmer. you will gain instant 120% performance if you do so :)
Alto capo me sirvió
Bad solution if point is in the direction of two or more edges, it will give inconsistent results.
So true.
Why always think in terms of the plane? How about presenting an algorithm example for three-dimensional space?
what question is that ? a lot of things works in terms of the plane. If you have a three dimensional space maybe you can use another algorithm