[Webinar] Streamline your web hosting managementRegister Today

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 284
  • Last Modified:

Need an algorithm

I need an algorithm to find out if a point is inside a shape defined by a bunch of coordinate points.  The shape might not be a standard polygon - it might be a star or similar shape that turns in on itself.

Any help appreciated.
0
youse_libe
Asked:
youse_libe
  • 2
  • 2
  • 2
1 Solution
 
ozoCommented:
Count how many times a ray from the point to infinity intersects a side of polygon.
0
 
LischkeCommented:
ozo is a bit short here, but he mentioned the usual approach:

1) create a vector from the given point and a point which is guaranteed to lie outside the polygon (direction doesn't matter
2) go through all edges in the polygon and check if they cross the vector created in 1)
3) if the number of intersections is equal then the given point is not in the polygon otherwise it is

Ciao, Mike
0
 
LischkeCommented:
Oops, it should read:

3) if the number of intersections is even then...

Ciao, Meike
0
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
youse_libeAuthor Commented:
ok, I see.

Now, could you just tell me what kind of math I need to know to do this calculation.  I've only had through calculus, long ago.  I don't think I've had anything that will do geometry like this.
0
 
youse_libeAuthor Commented:
thank you
0

Featured Post

The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

  • 2
  • 2
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now