patternMinor
Convex-hull of a star shaped polygon in O(n)
Viewed 0 times
convexstarhullshapedpolygon
Problem
I'm trying to develop an algorithm to find a convex hull of a star shaped polygon in $O(n)$ time. The specific problem, which is also described here, is as follows:
A polygon $P$ is star-shaped if there exists a point $p$ in the interior of $P$ that is in the shadow of every point on the boundary of $P$. The set of all such points $p$ is called the kernel of $P$.
Given an $n$-vertex, star-shaped polygon $P$ specified by its vertices in counterclockwise order, how to compute convex hull of this polygon in linear time.
According to these slides (slide $64$), it's really possible to find such a convex hull in linear time using Graham's Scan. This result is given as a corollary. This means that we probably need only the "scan" part of the Graham's Scan algorithm to solve this problem.
Imagine we have the following star-shaped polygon $P$:
and lets pick the point with the lowest $y$ coordinate of $P$, i.e., $p_2''$. If I'm not wrong, start from there, the steps applied would be:
-
Pick the next vertex, i.e., $p_3''$.
-
Lets consider the vertex $a$. We check if $p_2''p_3''a$ is a left or right turn, by using the cross product $(p_3'' - p2'') \times (p_3''- a)$. Since it's a left turn, we pick $a$.
-
We now consider $p_3''ab$. It's also a left turn, so we pick $b$.
-
We now consider $abc$. We also have a left turn, so we pick $c$.
-
Consider $bcp_1'$. It's a left turn, so we alsp pick $p_1'$.
-
$cp_1'p2'$ is a right turn. Thus we need to remove from the stack $p_1'$. Thus, so far we have included the following vertices in the $CH(P) = p_2'', p_3'', a, b, c, p_2'$.
-
We consider $cp_2'p_3' = cp_2'p_1''$ (just notation). It's a left turn, so we should include $p_3' = p_1''$. $CH(P) = p_2'', p_3'', a, b, c, p_2', p_3'$.
-
We now consider $p_2'p_3'p_2''$. It's a right turn, so we should remove all points which create a right turn with $p_2''$, i.e. , $p_3' = p_1''$, but also $p_2'$, because of $cp_2'p_2''$. So, now our final $$CH(P) = p_2'', p_3'', a, b, c
A polygon $P$ is star-shaped if there exists a point $p$ in the interior of $P$ that is in the shadow of every point on the boundary of $P$. The set of all such points $p$ is called the kernel of $P$.
Given an $n$-vertex, star-shaped polygon $P$ specified by its vertices in counterclockwise order, how to compute convex hull of this polygon in linear time.
According to these slides (slide $64$), it's really possible to find such a convex hull in linear time using Graham's Scan. This result is given as a corollary. This means that we probably need only the "scan" part of the Graham's Scan algorithm to solve this problem.
Imagine we have the following star-shaped polygon $P$:
and lets pick the point with the lowest $y$ coordinate of $P$, i.e., $p_2''$. If I'm not wrong, start from there, the steps applied would be:
-
Pick the next vertex, i.e., $p_3''$.
-
Lets consider the vertex $a$. We check if $p_2''p_3''a$ is a left or right turn, by using the cross product $(p_3'' - p2'') \times (p_3''- a)$. Since it's a left turn, we pick $a$.
-
We now consider $p_3''ab$. It's also a left turn, so we pick $b$.
-
We now consider $abc$. We also have a left turn, so we pick $c$.
-
Consider $bcp_1'$. It's a left turn, so we alsp pick $p_1'$.
-
$cp_1'p2'$ is a right turn. Thus we need to remove from the stack $p_1'$. Thus, so far we have included the following vertices in the $CH(P) = p_2'', p_3'', a, b, c, p_2'$.
-
We consider $cp_2'p_3' = cp_2'p_1''$ (just notation). It's a left turn, so we should include $p_3' = p_1''$. $CH(P) = p_2'', p_3'', a, b, c, p_2', p_3'$.
-
We now consider $p_2'p_3'p_2''$. It's a right turn, so we should remove all points which create a right turn with $p_2''$, i.e. , $p_3' = p_1''$, but also $p_2'$, because of $cp_2'p_2''$. So, now our final $$CH(P) = p_2'', p_3'', a, b, c
Solution
Graham scan for a convex hull works if you have an ordering of points $a_1,a_2,...a_N$ such that you have a sequence $p_1 < p_2 <...< p_k$ where your convex hull is $a_{p_1}, a_{p_2},...,a_{p_k}$ of which it is not possible to have a winding number greater than $1$.
In general for any polygon $P$ this might not work, but for a star shaped polygon, you could observe that from the point $p$ visible to all points, in counter-clockwise order, will be have the aforementioned property.
In general for any polygon $P$ this might not work, but for a star shaped polygon, you could observe that from the point $p$ visible to all points, in counter-clockwise order, will be have the aforementioned property.
Context
StackExchange Computer Science Q#66313, answer score: 2
Revisions (0)
No revisions yet.