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)

"Ray casting to every vertex"

I have been trying to implement the "Ray casting to every vertex" algorithm and I honestly don't know how to do it. Especially the pseudo-code:

algorithm naive_better_algorithm($p$, $S$) is
            for each obstacle $b'$ in $S$:
                $r$ := min($r$, distance from $p$ to $b'$)

How would you calculate the distance from a point to an obstacle (which is some convex polygon itself)? From practical perspective, I would like to use the visibility polygon to determine the visible edges (for later rendering), but I am unsure how this algorithm would help me. The resulting set of edges might contain segments (from one edge to the next) which are "empty", i.e. not belonging to a particular obstacle. I would not know how to detect this. Jörg Strebel (talk) 19:13, 3 January 2026 (UTC)

In Wikipedia, the article talk pages are for the work on the improvements of the article in question and not for general discussions. There are plenty of other venues in the internet where you can assk ffor help with algorithms. --Altenmann >talk 00:34, 4 January 2026 (UTC)

My post highlights the inaccuracies and the missing details of the pseudo-code. I tried to implement it and I can honestly say, this pseudo-code is unfit for implementation. Jörg Strebel (talk) 09:00, 18 January 2026 (UTC)