Re: Determining if a point on a 2D polygon is hidden

"Stefan Rybacki" <stefan.rybacki@xxxxxxx> wrote in message
news:3rkr05Fk58ndU2@xxxxxxxxxxxxxxxxx

> The easiest way to determine whether an external point can see
> another one, is to shot a ray from the external point to the other
> one and see whether there is an intersection between the polygon
> and the ray before the ray reaches your point.

This is an O(n^3) algorithm, which is reasonable for a small number
of polygon vertices, and is simple to implement. It is possible to
cull some of the ray-edge tests and reduce some of the computation
time. If P is the external point and V1 is the vertex of the current
query, let <V0,V1,V2> be consecutive vertices of the simple
polygon. You need not test every edge of the polygon against
the segment <P,V1>, only those in the cone defined by <V0,V1,V2>.
This culling is particularly useful in reducing the costs in dynamic path
finding. In fact if the query will be repeated for a large number of
points P, you could preprocess the polygon and store at each vertex
a list of edges that must be tested.

The topic of "visibility graphs" is covered in Joseph O'Rourke's book
"Computational Geometry in C, Second Edition". Section 8.2.2
mentions the O(n^3) algorithm, but points out that use of
"arrangements" leads to an optimal O(n^2) algorithm. Also
mentioned is the paper
S.K. Ghosh and D.M. Mount,
An output-sensitive algorithm for computing visibility graphs,
SIAM J. Comput. vol. 20, pp. 888-910, 1991.
where the algorithm is O(n log n + E), where E is the number of
graph edges. This number is O(n^2), but in practice is usually
small.

--
Dave Eberly
http://www.geometrictools.com


.

Relevant Pages

  • Re: Determining if a point on a 2D polygon is hidden
    ... is to shot a ray from the external point to the other one and see whether there is an intersection between the polygon and the ray before the ray reaches your point. ... This is an Oalgorithm, which is reasonable for a small number ... An output-sensitive algorithm for computing visibility graphs, ...
    (comp.graphics.algorithms)
  • Area of Polygon on a Sphere - Algorithm
    ... Given a polygon with N edges, each of which is a segment of a great ... algorithm, latitude and longitude are expressed in radians. ... involving inverse tangents of square roots ... The planar "square" was a rectangle with width equal to the side ...
    (comp.infosystems.gis)
  • Re: Smallest 4-sided polygon surrounding convex hull ( smallest convex quadrilateral)
    ... "Finally the smallest 4-sided polygon surrounding the segmented code [ ... This is a special case of convex hull ... And I can't find an algorithm for that, ... I believe I'm looking for the minimal enclosing quadrilateral ...
    (comp.graphics.algorithms)
  • Re: RFC: wideline algorithm
    ... > Have you considered using an algorithm for drawing convex ... > necessarily parallel to the x and y axes, so polygon algorithms ... Sure, a thickline is just a rectangle, but how do I go ... dungeon is composed of tiles which are either ...
    (comp.programming)
  • few questions with regards to ray tracing.
    ... I'm developing a ray tracing program which is based on GTD(Geometric ... Theory of Diffraction). ... bounding sphere but the algorithm needs access to points on the object ... What are these Bezier patches? ...
    (comp.graphics.algorithms)
Loading