[Webinar] Streamline your web hosting managementRegister Today

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

# 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
• 2
• 2
• 2
1 Solution

Commented:
Count how many times a ray from the point to infinity intersects a side of polygon.
0

Commented:
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

Commented:

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

Ciao, Meike
0

Author 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

Commented:
0

Author Commented:
thank you
0

## Featured Post

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