I offer the following j-script, which I believe does the trick. It may not
give what you expect if the point is on the boundary. Further I assume the
point to be checked is the origin (clearly no problem).
p=: 13 : '(0>:<./y)*(0<>./y)'
in=: 3 : 0
a=.p 11 o. y,:}.y,{.y
2|0+/ .<(11 o.*/z)*+/11 o. z=.a#"1 y,:+}.y,{.y
)
What I do is count the number of edge crossings as you go to infinity along
the x axis. Since you must allow for 0,1 or 2 crossings there has to be a
lot of checking even if convex. This script should work for any reasonable
polygon, i.e. it doesn't have to be convex, just closed with no boundary
crossings.
Ralph S
On Fri, 7 Mar 2008, Lars Strand wrote:
Inside or outside a convex polygon?
We want to find if a point is outside or inside a convex polygon. The
reasoning is as follows:
If the point to be examined is inside the polygon, the maximum angle
from the point to two of the vertexes has to be greater than p.
The verb within is used to this purpose:
within = 4 : 0 NB.x is point, y the vertexes
reg =:y-x
ang =:v360 "0 (1{"1 *. reg)
if. (ang>o.1) do.ang =:(o.2)-ang end.
(range ang)>o.1
)
where
v360 =: 3 : 'if. (y<0) do. (o.2)+y else. y end.'
range =: >./ - <./
A simple example:
The vertexes of the polygon are given by
vertexes=: 3j1 1j3 0j2 2j0
2j1 within vertexes
1
2j0 within vertexes
0
In a previous message to JForum (Jan 11- 19:55 "manuscript") I presented
a script to find the vertexes of a closed polygon when a number of
points are given.. The script gave as result the vertexes:
bpts=:.2j3.2 4j0.5 5.5j0.5 9.8j4.7 7.6j7.9 4.6j8.4 3j6.1
To see if a point is inside/outside::
5j9 within bpts
0 (inside!)
5j7 within bpts
1 (outside!)
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
