Talk:Visibility polygon

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( $p$ ,  $S$ ) is
     $V$  :=  $\emptyset$ 
    for each obstacle  $b$  in  $S$ :
        for each vertex  $v$  of  $b$ :
            // shoot a ray from  $p$  to  $v$ 
             $r$  := distance from  $p$  to  $v$ 
             $r0$  :=  $r$ 
             $rBig$  := Largest number possible
             $kissVertex$  :=  $\emptyset$ 
             $\theta$  := angle of  $v$  with respect to  $p$ 
            for each obstacle  $b'$  in  $S$ :
                 $r$  := min( $r$ , distance from  $p$  to  $b'$ )
                if  $r$  !=  $r0$ :
                       if  $r$  <  $rBig$ :
                             $kissVertex$  :=  $b'$ 
                             $rBig$  :=  $r$ 
            add vertex  $(\theta ,r)$  to  $V$ 
            if  $r$  =  $r0$ :
                if classifyVertex(kissVertex):
                     add vertex  $(\theta ,rBig)$  to  $V$ 
    return  $V$

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 $\theta$ 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 (talk • contribs) 16:27, 8 June 2020 (UTC)[reply]