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

NB: This video is ad-free, you can choose to support Inside code by purchasing one of the courses above or dropping a super thanks!
NB2: Discounts of courses above are permanent

[insidecode]

🔴
/ \
🔵—🔴
| |
🔴—🔵

[vid]

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

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

[kleare]

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.

[hhklbhhksm]

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

[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,

[miguelchenier]

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

[CrescentP-wips]

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

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

[manolski]

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

[antonioradu]

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

[surenbono]

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

[RandomGeometryDashStuff]

what if ray passes through polygon corner?

[aakashs]

Does this work for bodies in 3D space?

[juststudying]

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?

[JehanSaren]

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

[samsaraAI]

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

[andreasbritzemeier]

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

[SetszawA]

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

[senthil]

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