| Assume you have N connected points, (x1,y1) -> (x2,y2) -> ... (xN,yN)
connected in that order. Create some (x0,y0) where x0 >> any xI
and y0 >> any yI. Thus, (x0,y0) is some point "way out there".
(It also helps to have (x,y) -> (x0,y0) not parallel to any of
the N vectors).
For I = 1 to N-1 determine if the vector (x,y) -> (x0,y0) intersects
the vector (xI,yI) -> (xI+1,yI+1). This is 2 equations, 2 unknowns
and will always be solvable if the above parallel restriction is
obeyed. (Of course the lines will intersect, but the question is
if the vectors <line segments> intersect).
Count the number of intersections. If the total is odd, (x,y) is
interior to the polygon. Else it is exterior.
John
|
| The problem is not clearly stated, and the solution in .-1 applies only to
the case where the connections form a simple closed curve. If every point
in the set is connected to every other, then you have to identify the
convex hull of the figure (consisting of all the outermost lines) and apply
the odd-even rule to THAT figure. To see why, note that as you move along
the line from outside the figure toward the inside, the number of
intersections is 0,1,2,3... but if the full graph is involved, only the
transition from 0 to 1 marks the change from outside to inside.
There are convex hull algorithms in the literature; some recent ones are
quite fast. I don't have one at hand.
|
| I assume you want to classify a point as lying inside a simple
polygon. (A simple polygon does not contain self intersections).
This can be easily done in order N time, where N is the number of
edges. You scan thru the edges and vertices and compute the closest
distance of your query point to each edge and each vertex. Then
if the closest was an edge, the point is inside if it is oriented
on the inside of the edge, via a right hand rule. If it is a
vertex, then if the vertex is concave, the point is inside, otherwise
outside.
And that's all there is to it.
- Jim
|
| module point_in_polygon_predicate(input, output);
const
dyn_array_lim = 65536;
large = 1.0e12;
type
coord_array_type = array[1..dyn_array_lim] of single;
[global]
function point_in_polygon(n : integer;
xc, yc : single;
var x, y : [readonly] coord_array_type;
var best_d : single) : boolean;
{++}
{
{ Return true if the query point is within the given simple polygon
{
{ Input:
{ n Number of vertices
{ xc, yc Query point
{ x, y Array of n+2 vertices with first two vertices cycliclly
{ repeated, in counterclockwise order
{ Output:
{ best_d Closest distance of query point to polygon boundry
{
{--}
var
i : integer;
d, t : single;
begin
best_d := large;
point_in_polygon := false;
for i := 1 to n do begin
t := ((x[i+1]-x[i])*(xc-x[i])+(y[i+1]-y[i])*(yc-y[i]))/
((x[i+1]-x[i])**2+(y[i+1]-y[i])**2);
if t > 1.0 then begin
d := (xc-x[i+1])**2+(yc-y[i+1])**2;
if d < best_d then begin
best_d := d;
point_in_polygon := (x[i]-x[i+1])*(y[i+2]-y[i+1]) >
(y[i]-y[i+1])*(x[i+2]-x[i+1]);
end
end
else if t > 0.0 then begin
d := (xc-(x[i]+t*(x[i+1]-x[i])))**2+(yc-(y[i]+t*(y[i+1]-y[i])))**2;
if d < best_d then begin
best_d := d;
point_in_polygon := (x[i+1]-x[i])*(yc-y[i]) >
(y[i+1]-y[i])*(xc-x[i]);
end
end
end;
best_d := sqrt(best_d);
end;
end.
|