A linear-time algorithm to find any vertex of a polygon visible from other vertex

Question

Suppose there is a polygon with no holes and self-intersections (i.e. a simple polygon) defined by n vertices. Choose a reflex vertex v of this polygon.

I'd like to find any other vertex u of the same polygon which is "visible" from the vertex v. By visible I mean, that a line segment between v and u lies completely inside the polygon.

Is there an algorithm to do that in O(N) time or better? Is there an algorithm that can find all visible vertices in O(N) time?

A quick research suggests that for a given polygon and any point inside this polygon a visibility polygon can be constructed in O(N). I assume that finding a single visible vertex should be even easier.

Answer 1

This problem was solved 30 years ago:

ElGindy and Avis, "A linear algorithm for computing the visibility polygon from a point", J. Algorithms 2, 1981, p. 186--197.

There is a very nice paper by Joe & Simpson, 1985, "Visibility of a simple polygon from a point," that offers carefully verified pseudocode: (PDF download link). This surely has been implemented many times since, in many languages. For example, there is a link at the Wikipedia article on the topic.

Answer 2

I've modified the algorithm as it was incorrect. I hope this time it covers all cases!.

Start from a reflex a, let a' the next vertex and follow the polygon until you find an edge that crosses a--a' in the side a', let b the point of intersection of this edge with the line a--a' and c the end point of the edge (the one to the right of a--c).

Now continue going through the edges of the polygon, and if an edge crosses the segment a--b from left to right then set b to the new point of intersection and c to the end vertex. When you finish we have a triangle a--b--c. Now starting again from c look every vertex to see if it is inside the triangle a--b--c and in that case set c to the new vertex. At the end a--c is a diagonal of the polygon.

Here is an implementation in C that assumes that the reflex point a is in P[0]:

struct pt {
    double x,y;
    friend pt operator+(pt a, pt b){a.x+=b.x; a.y+=b.y; return a;}
    friend pt operator-(pt a, pt b){a.x-=b.x; a.y-=b.y; return a;}
    friend pt operator*(pt a, double k){a.x*=k; a.y*=k; return a;}
    bool leftof(pt a, pt b) const{
        // returns true if the *this point is left of the segment a--b.
        return (b.x-a.x)*(y-a.y) - (x-a.x)*(b.y-a.y) > 0;
    }
};
pt intersect(pt a, pt b, pt c, pt d){// (see O'rourke p.222)
    double s,t, denom;
    denom = (a.x-b.x)*(d.y-c.y)+ (d.x-c.x)*(b.y-a.y);
    s = ( a.x*(d.y-c.y)+c.x*(a.y-d.y)+d.x*(c.y-a.y) )/denom;
    return a + (b-a)*s;
}
/**
    P is a polygon, P[0] is a reflex (the inside angle at P[0] is > pi).
    finds a vertex t such that P[0]--P[t] is a diagonal of the polygon.
**/
int diagonal( vector<pt> P ){
    pt a = P[0], b = P[1]; //alias
    int j=2;
    if( !b.leftof(a,P[j]) ){
        // find first edge cutting a--b to the right of b
        for(int k = j+1; k+1 < int(P.size()); ++k)
            if( P[k].leftof(a,b) && P[k+1].leftof(b,a) && b.leftof(P[k+1],P[k]) )
                j = k,
                b = intersect( a,b,P[k],P[k+1] );
        // find nearest edge cutting the segment a--b 
        for(int k = j+1; k+1 < int(P.size()); ++k)
            if( P[k].leftof(a,b) && P[k+1].leftof(b,a) &&
                a.leftof(P[k+1],P[k]) && b.leftof(P[k],P[k+1]) ){
                b = intersect( a,b,P[k],P[k+1] );
                j = k+1;
            }
    }
    for(int k = j+1; k+1 < int(P.size()); ++k)
        if( P[k].leftof(a,b) && P[k].leftof(b,P[j]) && P[k].leftof(P[j],a) )
            j = k;
    return j;
}