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

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

Рет қаралды 25,672

Жыл бұрын

Source code: gist.github.com/inside-code-y...
🔴 Learn graph theory algorithms: inscod.com/graphalgo
⚙ Learn dynamic programming: inscod.com/dp_course
💡 Learn to solve popular coding interview problems: inscod.com/50problems_course
⌛ Learn time and space complexity analysis: inscod.com/complexity_course
🔁 Learn recursion: inscod.com/recursion_course
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
I also post content on LinkedIn (inscod.com/linkedin) and Instagram (inscod.com/instagram)

Пікірлер: 47

@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 8 ай бұрын

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.

@miguelchenier4817 8 ай бұрын

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

@JamesSarantidis 3 күн бұрын

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?

@toohadi Жыл бұрын

Great video, thanks!

@matshagerlind 3 ай бұрын

Thank you very much, great video! :)

@surenbono6063 8 ай бұрын

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

@pauliusviskaitis9640 Жыл бұрын

Thanks!

@Prakash-cw2ml Жыл бұрын

It very useful🎉

@hhkl3bhhksm466 7 ай бұрын

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 6 ай бұрын

adventofcode 2023 Day 10 pipe maze ?

@hhkl3bhhksm466 6 ай бұрын

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

@WeloveKoora 6 ай бұрын

@@hhkl3bhhksm466 Yes, after 24 hours of searching hhhhh

@WeloveKoora 6 ай бұрын

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

@antonioradu2842 Жыл бұрын

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

@cosmoquissoyt5636 Жыл бұрын

Alto capo me sirvió

@aakashs1806 Ай бұрын

Does this work for bodies in 3D space?

@CrescentP-wi7ps 4 ай бұрын

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

@samsara2024 4 ай бұрын

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

@manolski7615 Жыл бұрын

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

@fnxph03n1x 9 ай бұрын

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 6 ай бұрын

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

@user-px5pj7ux5k 7 ай бұрын

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

@xLainik 6 ай бұрын

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

@juststudying1019 10 ай бұрын

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 10 ай бұрын

But how to know the edges of that directon?

@juststudying1019 10 ай бұрын

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 10 ай бұрын

Why would we count the intersection twice?

@juststudying1019 10 ай бұрын

@@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 10 ай бұрын

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

@andreasbritzemeier6901 9 ай бұрын

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

@user-lx4sp1gl4f 8 ай бұрын

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

@RandomGeometryDashStuff Жыл бұрын

what if ray passes through polygon corner?

@insidecode Жыл бұрын

I think that it will count once

@janasimjanovska855 11 ай бұрын

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

@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

@Phosdoq 3 ай бұрын

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

@colefrankenhoff1428 6 күн бұрын

Nope, they don't

@Phosdoq 6 күн бұрын

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

@SetszawA 6 ай бұрын

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

@igorfujs7349 4 ай бұрын

So true.

@user-gm2im7ws5c 5 ай бұрын

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