Looking for an Algorithm

Projects Programming
1

OK, technically not a programming question. But folks here have posted links to some pretty interesting algorithms that have apparently been “well-known” for some time. So, here goes:

Given a simple polygon defined by the (x, y) coordinates of its vertices: (x0, y0), (x1, y1), (x2, y2), …. what would be an algorithm to determine if an arbitrary point (X, Y) lies inside or outside the polygon?

2

Good question!

I guess any polygon can be broken down into a series of the simplest 2D shape, the triangle.

So then the question becomes

  1. How do you break down a polygon into triangles.
  2. Is the point (x,y) inside any of those triangles.
3

You could try implementing this...

4

Draw a line from inside the area to outside and count how many lines of the polygon you cross doing.

a7

1 Like
5

I think conceptually the simplest one is casting a ray from the point to infinity, and see how many times it intersects an edge of the polygon. There are some nasty edge cases though.

6

Boom!

a7

7

some source code here

8

PNPOLY - Point Inclusion in Polygon Test, W. Randolph Franklin (WRF)

9

This topic was automatically closed 180 days after the last reply. New replies are no longer allowed.