Checking if a point is inside a polygon is RIDICULOUSLY simple (Ray casting algorithm) - Inside code

[@insidecode]

Discover the new graph theory algorithms course: inscod.com/graphalgo 🔴 / \ 🔵-🔴 | | 🔴-🔵

[@vid2422]

That even/odd technic blew my mind, I never expected the method to be simple yet genius at the same time

[@insidecode]

Me neither

[@BlackSharkfr]

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.

[@kleare520]

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.

[@Kobold666]

Using offsets and epsilons introduces a whole bunch of new problems that have to be fixed with more offsets and epsilons. Division by 0 is not an error and the result (infinity) is quite useful in comparisons.

[@iWillRun_K]

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,

[@JamesSarantidis]

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?

[@miguelchenier4817]

Thank you. This worked so well. I've been beating myself up trying to think of a solution.

[@hhkl3bhhksm466]

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

[@WeloveKoora]

adventofcode 2023 Day 10 pipe maze ?

[@hhkl3bhhksm466]

@@WeloveKoora Yeah, haha, did you also use the same method?

[@WeloveKoora]

@@hhkl3bhhksm466 Yes, after 24 hours of searching hhhhh

[@WeloveKoora]

@@hhkl3bhhksm466 it was very challenging problem, but i learned a lot

[@jumpsneak]

No sound???

[@CrescentP-wi7ps]

4:55 You didn't handle divide by zero case.

[@manolski7615]

what if y2 - y1 = 0 for the 2nd cond? Do we just ignore that count?

[@fnxph03n1x]

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

[@gdclemo]

@@fnxph03n1x if y2 == y1 then the first condition ( (yp < y1) != (yp < y2) ) will never be True, so the second condition will not be evaluated.

[@surenbono6063]

...do you have link to the world timezones vertex defined database?..for automatic local GPS clock decoder

[@yusufbulbul7100]

great explanation. thank you.

[@RandomGeometryDashStuff]

what if ray passes through polygon corner?

[@insidecode]

I think that it will count once

[@janasimjanovska855]

@@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?

[@samsaraAI2025]

Nice video thanks. Could you upload the same video for 3D non convex o bjects? :)

[@antonioradu2842]

just got a homework where I need to check if a point is inside a polygon, thx :D

[@aakashs1806]

Does this work for bodies in 3D space?

[@trungkstn]

How about case y1 = y2

[@juststudying1019]

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?

[@insidecode]

But how to know the edges of that directon?

[@juststudying1019]

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

[@insidecode]

Why would we count the intersection twice?

[@juststudying1019]

@@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

[@insidecode]

No we increment the counter only when there's an intersection

[@JehanSaren]

Hi sir, I made a net simulation, how do I know that the particles are inside the net?

[@xLainik]

Check out "Determining if a point lies on the interior of a polygon" by University of Michigan. It's on google

[@matshagerlind]

Thank you very much, great video! :)

[@toohadi]

Great video, thanks!

[@Phosdoq]

some shapes must be treated with their own condition: like circles, rectangles, triangles...

[@colefrankenhoff1428]

Nope, they don't

[@Phosdoq]

@@colefrankenhoff1428 they don't if you are bad programmer. you will gain instant 120% performance if you do so :)

[@Prakash-cw2ml]

It very useful🎉

[@senthil6382]

is it possible to generate all the points inside the polygon, if the polygon is represented by vertices

[@insidecode]

There is an infinity of points inside a polygon

[@pauliusviskaitis9640]

Thanks!

[@andreasbritzemeier6901]

Does anyone know if there is an easy extension to 3D ?

[@ОрландоОрсо]

Project you shape to 2D plane and then try this method.

[@cosmoquissoyt5636]

Alto capo me sirvió

[@SetszawA]

Bad solution if point is in the direction of two or more edges, it will give inconsistent results.

[@igorfujs7349]

So true.

[@解夢人]

Why always think in terms of the plane? How about presenting an algorithm example for three-dimensional space?

[@_danisson]

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