I'm looking for an algorithm that given a 2D convex polygon and point outside it, returns the two points of the polygon which are the two extremities of the polygon when viewed from that point.
One option I came up with is calculate the dot product between the vector to the center of the polygon and the vector to each of the circumference points, normalized to length 1 and compare the resulting cos(angle). The problem with this is that it's too slow. Ideally I'd like to have an algorithm with no square roots or anything like that.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
Then by examining $p_i$ with this primitive, you can determine if the search should stop, or advance cw or ccw. Then one can build a binary search on this primitive, and achieve logarithmic search time. It is not completely straightforward to write perfect code for this, but with care it can be implemented correctly.
$\endgroup$
4
This can be solved in $O(\log n)$ time for a convex polygon of $n$ vertices, assuming the polygon vertices are ordered around the boundary (thanks to Gerhard Paseman for pointing out this assumption).
Let $x$ be the exterior point, and $p_i$ vertices of the polygon. Write a primitive that can determine when $p_i$ is extreme in the counterclockwise (ccw) direction by comparison of $x p_i$ with $x p_{i-1}$ and $x p_{i+1}$, and if not extreme, to which side (cw or ccw) of the extreme:
Then by examining $p_i$ with this primitive, you can determine if the search should stop, or advance cw or ccw. Then one can build a binary search on this primitive, and achieve logarithmic search time. It is not completely straightforward to write perfect code for this, but with care it can be implemented correctly.
No square roots or trig functions are needed. For example, echoing the OP's query, let $\triangle (x,y,z)$ be the signed area of the triangle with corners $x,y,z$. Then compute $a=\triangle (p_i,x,p_{i-1})$ and $b=\triangle (p_{i+1},x,p_i)$. If both $a,b>0$, move ccw. If both $a,b<0$, move cw. If $a$ and $b$ are opposite signs, an extreme has been reached. (Some care is needed when either or both $a$ and $b$ are zero.)
answered Jul 27, 2015 at 15:59
-
$\begingroup$ You need to take care. O(log n) is possible when the list of vertices is already sorted by this orientation, or nearly so. It is not clear to me that the polygon is presented in such a form, nor is it clear that n is small enough not to matter. Gerhard "Without Chaos, Can't Appreciate Order" Paseman, 2015.07.27 $\endgroup$ Jul 27, 2015 at 16:46
-
$\begingroup$ maybe something like
sign(det(xpi-1, xpi)) != sign(det(xpi, xpi+1))? $\endgroup$– shooshJul 27, 2015 at 19:57 -
$\begingroup$ @GerhardPaseman: You are right, I assumed the polygon is given by its vertices in order (ccw or cw), as they would be from e.g., a convex hull algorithm. If the vertices are completely unordered, $\Omega(n \log n)$ is a lowerbound (in a comparison model). $\endgroup$ Jul 27, 2015 at 20:33
-
$\begingroup$ @shoosh: Yes. I elaborated along the same lines as you suggest. $\endgroup$ Jul 27, 2015 at 20:48