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

Dave Eberly wrote:
"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.

Well I didn't tell anything about a special implementation but its ok, before the next question follows that deal with the acceleration of this occlusion test.
But I've an additional question. Why is it O(n^3) IMHO its O(n) in worst case. Since I have n edges and one ray. So I have to test n edges in worst case? I also could do a presorting as well as "backedge"-culling to reduce n. Where does O(n^3) come from?

Regards
Stefan


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
    ... > and the ray before the ray reaches your point. ... This is an Oalgorithm, which is reasonable for a small number ... of polygon vertices, ... The topic of "visibility graphs" is covered in Joseph O'Rourke's book ...
    (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