A linear-time algorithm to find any vertex of a po

问题:

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.

回答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.

回答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;
}

回答3:

You can test any individual vertex in O(n) time, and hence test all vertices in O(n^2). To test any if any individual vertex U is visible from V, construct the line between V and U. Let us call this line L. Now, test L to see if it intersects any of the polygon edges. If it does not, U is not obscured from V. If it does, U is obscured.

Further, you can test if L lies within the polygon like so: Assume the incident edges on V are E1 and E2. Calculate the signed angles between E1 and E2 (call this a1) and between E1 and L (call this a2). The sign of a2 should be the same as a1 (i.e., L is on the 'same' side of E1 as E2 is), and a2 should be smaller than a1 (i.e., L 'comes before' E2).

Be careful with your intersection tests, as L will trivially intersect the polygon edges incident to V. You can ignore these intersections.

Also, if U shares any of the edges incident to V, U is trivially visible from V.

回答4:

You could use a triangulation of the polygon.

Assuming you have a triangulation T, a set of visible vertices U for a vertex V could be found by examining associated internal edges in the triangulation. Specifically, if the set of triangles attached to V are traversed and the internal edges identified (those that appear twice!), the set U is all edge vertices except V.

Note that this is not necessarily all visible vertices from V, just a set with |U| >= 0 (must be at least one internal edge from V). It is efficient though - only O(m) where m is the number of triangles/edges visited, which is essentially O(1) for reasonable inputs.

Of course, you would need to build a triangulation first. There are efficient algorithms that allow a constrained Delaunay triangulation to be built in O(n*log(n)), but that's not quite O(n). Good constrained Delaunay implementations can be found in Triangle and CGAL.

回答5:

Just keep going in some direction through vertices starting with V and update list of visible vertices. If I didn't miss anything, that will be O(n).

For simplicity let's call V visible.

I've tried for a day to put it in words, failed and used pseudo-code :)

visible_vertices = {V}
for each next segment in counter-clockwise polygon traversal
  if segment is counter-clockwise (looking from V)
    if (visible_vertices.last -> segment.end) is counter-clockwise
      visible_vertices.add(segment.end)
  else
    while segment hides visible_vertices.last or segment.start=visible_vertices.last
      visible_vertices.remove_last