Definiton: monotone polygon – a polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $P$ at most twice.
I am interested in building an algorithm for testing any given polygon for monotonicity. In my opinion, we should consider every vertex with inner angle $>180^{circ}$, because a perpendicular from $L$ might intersect only adjacent edges of reflex vertex ($>180^{circ}$). In addition, slope of $L$ also should be taken into account, and should be between the slopes of adjacent edges of reflex vertex. It looks like the above theory should be enough for constructing an algorithm. What’s your opinion? How to test polygon for monotonicity?
Asked By : com
Answered By : JeffE
IsMonotone(X[0..n-1], Y[0..n-1]) local_mins ← 0 for i ← 0 to n-1 if (X[i] < X[i+1 mod n]) and (X[i] < X[i-1 mod n]) local_mins ← local_mins + 1 return (local_mins = 1)
If you’re worried that your polygon might have vertical edges, use the following subroutine in place of the comparison X[i] < X[j] to consistently break ties:
IsLess(X, i, j): return ((X[i] < X[j]) or (X[i] = X[j] and i < j))
Finally, if $L$ is some other line of the form $ax+by=c$, modify IsLess as follows:
IsLess(X, Y, i, j): Di ← a·X[i] + b·Y[i] Dj ← a·X[j] + b·Y[j] return ((Dj < Dj) or (Di = Dj and i < j))
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1577
