| Re: determining if a point is "inside" or "outside" a shape [message #17487 is a reply to message #17479] |
Thu, 21 October 1999 00:00   |
Job von Rango
Messages: 2
Registered: October 1999
|
Junior Member |
|
|
Ther is another analytic way to solve the problem:
How to determine wether a point lies inside an arbitrary 2-dimensional
polygon
or not?
IDEA:
Look at the sum of all angles tended between all pairs of neighboured
vertics
the polygon and the given point.
IN DETAIL:
Assume we have the n vertices of polgons ordered at the positions:
v_1, v_2, ... ,v_n
The given point is denoted by p.
Now connect the given point p with all n neighboured
vertices, and get the n vectors beginning in p and ending
in the vertices:
vec_1 = vector(p_0, v_1)
...
vec_n = vector(p_0, v_n)
Now add all n angles tended between the 2 vectors vec_i and vec_(i+1):
angle_i = angle(vec_i,vec_(i+1))
and calculate the sum:
n
anglesum = sum angle_i
i=1
(Use vec_1 again for vec_(n+1) in the last angle_n)
RESULT:
_
| 2*pi inside
anglesum = -| if p is the polygon
|_ 0 outside
IMPORTANT:
Take into account the correct sign of the angles
and use the vertices in ascending order!
Use e.g. the vector crossproduct:
vec_i x vec_(i+1)
in order to retrieve the absolut value |...| for the angle:
|angle_i| = inv sin( |vec_i x vec_(i+1)| )
The valid sign for angle_i is given by looking at the scalar product
of the crossproduct from above and a fixed vector vec_perp, perpendicular
to the area of the polygon:
vec_perp * ( vec_i x vec_(i+1) )
sign_i = -------------------------------------
| vec_perp * ( vec_i x vec_(i+1) ) |
Now we get the correct value for all angles:
angle_i = sign_i * |angle_i|
REMARK:
Examine the case of a given point inside the polygon, but very near
to the edge between two vertices v_i and v_(i+1). The contributing
angle will be:
angle_i = + pi - epsilon
(where epsilon denotes a small positive angle.)
If we shift p over the edge to the outside of the polygon
(but very near again to the edge)
the contributing angle will be:
angle_i = - pi + epsilon'
The switch of the sign is the reason for the discontinuity (2*pi <-> 0)
of anglesum for points moving from inside to the outside of the polygon!
------------------------------------------------------------ --
Job v. Rango Medizinische Klinik I
Dipl.-Phys. D-52074 Aachen
Pauwelsstrasse 30
Tel. : 049 / (0)241 / 80-89832
Fax : 049 / (0)241 / 88-88414
Email: jran@pcserver.mk1.rwth-aachen.de
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
