| If you are solving a 2D geometry problem here are two methods.
The first method is based on the angles. When a point is inside a polygon,
the sum of angles from that point to each 2 contiguous vertices is 2*Pi.
I never implemented that method.
The second method is based on intersections:
An arbitrary straight line starting from this point (and in the same plane
as the polygon) will intersect the polygon:
- An ODD number of times if the point is inside the polygon.
- An EVEN number of times if the point is outside.
Warnings:
1) You must orient the polygon and define clearly what "Inside" and
"Outside" means. The polygon could be the outline of a hole.
2) "Arbitrary" is also an issue. You may draw a line from the given point
to a vertex, find only one intersection point and conclude the point is inside.
I already implemented that method successfully.
|
|
A polygon is not uniquelydefined by the vertices. Different polygons
may have the same vertices. A polycon can be defined by the edges,
e.g., as linear forms
L(j)(x,y) = 0; j=1..N
and with the proper choice of signs can the "interior" be defined
as all the points for which
L(j)(x,y) > 0; j=1..N
|