On 16 April 2010 20:11, Dan Bron <[email protected]> wrote:
> ......
As Henry mentioned, there are details in this problem that affect
the way it is solved. Let me leave those concerning the arithmetic
precision aside and briefly mention some of the others.
First, a polygon may be self-intersecting, degenerate or simple.
Simple means that its boundary is neither intersecting nor
overlapping at any of its points. Overlapping leads to degeneracy,
up to where a polygon has no internal points at all.
Convexity is not equivalent to non-degeneracy. A polygon is convex
when it is simple and all its vertices are convex (none is concave,
a.k.a. reflex).
For a convex polygon, the point containment problem can be solved in
log n time, while the general case requires linear time.
In the general case, the usual approach is to cast a ray from the
point and count how many times it intersects the boundary. However,
special cases emerge – and should carefully be dealt with – as the
ray passes through a vertex or overlaps with one or more sides.
That makes solving the problem not entirely trivial even for a
simple polygon.
How to treat a point on the boundary is yet another issue. I see
four possibilities:
1. treat as ‘in’,
2. treat as ‘out’,
3. treat as a separate case, ‘on’, or
4. ‘dont't care’, i.e. treat as ‘in’ or ‘out’ and don't pay
attention which one it is in each case.
Here is a solution for a general polygon, including the cases of
self-intersection and degeneracy. The procedure returns -1, 0, or 1
for a point outside, on the boundary, or within it.
(Not thoroughly tested, and surely can be improved in some ways.)
pinp=. 4 : 0
s=. 2&(]\)@(],{.)
o=. ]/:/:@:({:"1)
ps=. o"2...@s y
as=. *-/ .* x,"1 2 ps
vs=. x -"1 ps
if. +/ (as=0) *. 0>:+/"1*/"2 vs do.
0
else.
<:+:~:/(as>0)*.([:(0&<@{.*.1&>@{:)[:{.[:|.|:)"2 vs
end.
)
Examples:
p=. 10 2$1 0 2 1 3 0 4 1 4 3 3 1 2 3 1 3 0 2 1 2
2 2 pinp p
1
(3 2$0 1 1 1 2 2) pinp"1 _ p
_1 0 1
Regards,
Boyko
P.S. As for finding a maximal rectangle contained within the
polygon, I do think that this is a non-trivial task, even for a
convex polygon.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
