Jump to content

Talk:Visibility polygon

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia


I don't think the naive algorithm works.


---x--p----e---- 
\     |
 \    |
  x   |
   \  |
    \ |
     \|
      p
     /|
    / |
   e  |
  /   |
 /    |
      ^
     ray
    

In the above diagram both edges e are part of the visibility polygon, but the x edges are not, and so both points p have to be added to the polygon from a single ray.

The algorithm should be:

algorithm naive_better_algorithm(, ) is
     := 
    for each obstacle  in :
        for each vertex  of :
            // shoot a ray from  to 
             := distance from  to 
             := 
             := Largest number possible
             := 
             := angle of  with respect to 
            for each obstacle  in :
                 := min(, distance from  to )
                if  != :
                       if  < :
                             := 
                             := 
            add vertex  to 
            if  = :
                if classifyVertex(kissVertex):
                     add vertex  to 
    return 

Where the classifyVertex() function finds if the ray has just kissed a vertex without going into the interior of the obstacle of which it is a part, and so also allows the addition of the point that the ray hits behind that. Without that code, partial edges of the obstacles that should form part of the visibility polygon don't get correctly added. Further, when this happens, both points have the same value, leading to an ambiguity in the subsequent sort by angle. Thus the addition of the two points has to be done in the correct order, which depends whether the vertex kissed points clockwise or anticlockwise; the classification function can work that out too and the result used to decide the order of addition.

— Preceding unsigned comment added by Adrianreprap (talkcontribs) 16:27, 8 June 2020 (UTC)[reply]