5
$\begingroup$

In the context of writing a ray-tracing program, I must be able to determine if a polygon in three-dimensional space is a planar simple convex polygon. My conjecture is that if I take the sum of the exterior angles (absolute values, always in the range $[0, \pi]$) then this sum is equal to $2\pi$ if and only if it is a planar simple convex polygon.

I firmly believe this to be true, but I seek somewhat rigorous proof. I already managed to show that the sum equals $2\pi$ for convex polygons and that it exceeds $2\pi$ for concave ones. However, I do not have any ideas on how to continue to prove that complex and non-planar polygons have a sum of exterior angles greater than $2\pi$.

For complex planar polygons, I managed to show (w.l.o.g.) that the exterior angles which "turn to the right" minus those that "turn to the left" must be a $2\pi n$ for some natural $n$. From there it's trivial to show that if $n>1$ then the total must be greater than $2\pi$, but for $n=0$ and $n=1$ I do not know how to proceed.

For non-planar polygons, I thought about what would happen if we project it to 2-dimensions then somehow show that the projection has an exterior angle sum strictly between $2\pi$ and that of the non-planar version, but I once again cannot fathom how to show that. (Edit: this idea does not work since there are counterexamples of non-planar polygons whose projections onto two-dimensional space have a larger exterior angle sum.)

$\endgroup$
2
  • $\begingroup$ I assume you know how to show that it is planar? Than for a simple case of 4 you may see that the 3D could be more than $2\pi$ if I understand your question. $\endgroup$
    – Moti
    Mar 12, 2021 at 2:47
  • $\begingroup$ @Moti I'm sorry I'm not quite sure what you mean. I know how to determine if a polygon is planar, but I don't see how that helps. Also, what do you mean by your second sentence? Which simple case of 4? What do you mean by show it could be more than $2\pi$? I need to show that all 3d polygons sum to more than $2\pi$ $\endgroup$ Mar 12, 2021 at 3:13

3 Answers 3

3
+100
$\begingroup$

The answer lies in Lemma 2.1 of Sullivan, Curves of Finite Total Curvature.

The paper refers to exterior angles as turning angles, and for a polygon $P$ designates the sum of turning angles (total curvature) as $TC(P)$

Here's a paraphrased version of the key lemma:

Lemma 2.1. Suppose $P$ is a polygon in $\mathbb R^3$. If $P'$ is obtained from $P$ by deleting one vertex $v_n$ then $TC(P') ≤ TC(P)$. We have equality here if $v_{n−1}v_n v_{n+1}$ are collinear in that order, or if $v_{n−2}v_{n−1}v_{n}v_{n+1}v_{n+2}$ lie convexly in some plane, but never otherwise.

Please refer to the paper for a proof, along with background and definitions. It's a short simple argument, using a mapping that takes 3D polygons $P$ to spherical polygons $P_S$ on the unit sphere $\mathbb S^2$. The total curvature of $P$ is the same as the boundary length of $P_S$.

Lemma 2.1 nicely takes care of both cases.

For a non-planar polygon $P$, removing vertices until only a triangle $T$ is left defines a sequence of polygons whose total curvature is strictly decreasing in at least one pair of the sequence (corresponding to where some $v_{n−2}v_{n−1}v_{n}v_{n+1}v_{n+2}$ is not planar). Since $TC(T)=2\pi$ we conclude that $TC(P)>2\pi$.

Similarly, for complex planar polygons $P$ there will be vertex sequences $v_{n−2}v_{n−1}v_{n}v_{n+1}v_{n+2}$ that are not convex and again $TC(P)>2\pi$.

$\endgroup$
3
  • $\begingroup$ Thank you so much for your answer! I had seen that paper before, but your explanation really helped me understand it and how to apply it to my conjecture. However, I don't see how this proof holds for complex planar polygons. Some complex planar polygons only have convex vertices, contrary to your claim, such as a star polygon. I don't really need a proof for complex polygons though, since I already answered that myself. $\endgroup$ Mar 16, 2021 at 1:02
  • 1
    $\begingroup$ You're welcome! I futzed around with your claim wondering how to prove it and eventually remembered the John Milnor proof that a closed curve with total curvature less than $4\pi$ cannot be a knot. That led me to the paper. As for complex polygons, 'convex' means more than turning right at every vertex. I think It's more like the convex hull of the vertices also corresponds to the edges and interior of that part of the polygon (which isn't true for the star). I have to admit I kind of skimmed over that part, so if you don't buy my distinction let me know and I'll look at it more closely. $\endgroup$
    – brainjam
    Mar 16, 2021 at 2:29
  • 1
    $\begingroup$ I was thinking about this question and realized that if the conjecture were true it would probably be true for the integral of the changes in direction of a smooth curve, which would imply it for polygons. My friend Peter Renz found this proof: ics.uci.edu/~eppstein/junkyard/knot-curvature.html - too late to post as an answer here. $\endgroup$ Mar 16, 2021 at 18:48
1
$\begingroup$

After many days of thought, I have come up with a proof for complex polygons. I will not accept my answer until I either edit it with a proof for non-planar polygons too or someone else is able to answer that part of my question.


The first thing to do is to disqualify any polygon with overlapping colinear (not necessarily consecutive) edges. If a walk through the edges would demonstrate that these edges are walked through in the same direction twice that means that a total turn of at least $2\pi$ has already been made between the two edges, yet the traversal has not yet concluded. Otherwise, if the edges are walked over in opposite directions, that would require a total turn of at least $\pi$ to turn around at each end of these edges. If that is all the turns that there are, then this sequence of points has only two significant points and does not form a polygon. The number of significant (non-colinear) vertices will have to be checked separately.

Now that we've gotten that out of the way, we may proceed with the assumption that no edges overlap. Note, this also means that no interior angle is equal to 0, $\pi$ or $2\pi$ radians, which means that no exterior angle is $\pm\pi$ or 0 radians, which in turn means that no turn (the absolute value of the exterior angle) is 0 or $\pi$ radians.

For any complex polygon $P$, we are able to find a sequence of consecutive vertices of $P$ which when appended to an intersection point of $P$ forms a simple polygon in the following way.

We choose any arbitrary point on the polygon's bounding path. Then from that point we trace the bounding path, marking any intersection points we encounter. Once we arrive at an intersection point which we've previously encountered, we stop. Let this intersection point be called $I$.

The closed path which we traced from the first encounter with $I$ to our second encounter with $I$ is a simple polygon (see figure).

enter image description here

Figure: Extracting a simple polygon from a complex one. This complex polygon is a pentagram with vertices $v_0$ through $v_4$. $S$ is the arbitrarily chosen starting point. The orange arrowhead marks the bounding edges of a simple polygon $E = (v_0, v_4, v_3, I)$ embedded in the complex pentagram. $I$ is the first (and necessarily the only) intersection point of the pentagram which we encountered twice.

The embedded polygon $E$ found with this procedure must be simple since we stop our trace at the first intersection point we encounter twice. Thus all of $P$'s intersection points are touched only once by $E$, except for point $I$ which is the start and end point, so is not an intersection point of $E$ either.

Let $\alpha \in (0, 2\pi) - \{\pi\}$ be the interior angle of $E$ at vertex $I$, and let $\beta = \pi - \alpha \in (-\pi, \pi) - \{0\}$ be the exterior angle of the same.

Suppose now we were to 'walk' a cycle through the edges of $P$ starting at the midpoint of the line segment formed by $I$ and one of the two vertices adjacent to $I$ which is common to both $P$ and $E$ (either $v_0$ or $v_3$ in the figure). Suppose we start walking in the direction away from $I$ and are only allowed to walk forward and turn.

The first time we reach $I$, we will have already turned all the turns of $E$ but one --- $T_E(I)$ (the turn of polygon $E$ at vertex $I$), which is equal to $|\beta|$. We immediately pass $I$ and enter a section of the path which is no longer part of $E$. Let us analyze the current position.

Since $I$ is an intersection point of $P$, we will in future be forced to encounter it again before arriving finally at the start. However, since we've just passed $I$, it is positioned a small distance directly behind us. This means that in order to reach it in future, our path must force us to make some turns which sum to at least $\pi$ radians.

This now allows us to formulate our first inequality. ($\sum T_P$ means the total turn of the polygon $P$, that is the sum of the turn at each of its vertices) \begin{equation} \sum T_P \geq \sum T_E - |\beta| + \pi \end{equation}

Since we know that $\sum T_E \geq 2\pi$ due to the simplicity of $E$, and that $\beta \neq \pm\pi$ from the first paragraph of the proof, we can from the previous inequality come to the following conclusion. \begin{equation} \sum T_P \geq 3\pi - |\beta| > 2\pi \end{equation}

$\endgroup$
0
$\begingroup$

I think your conjecture is true, but that you do not need it to reach your conclusion programmatically in essentially the same time with a loop through consecutive pairs of edges.

In that loop, first check for planarity by checking that all pairs have the same normal (up to a constant factor). You do that by calculating the cross products. Then find the exterior angles. The polygon will be simple and convex if and only if there are no sign changes and they sum to $\pm 2\pi$.

You may have to worry about numerical instability if consecutive edges are nearly collinear.

$\endgroup$
9
  • $\begingroup$ Checking the cross products shows us to discard non-planar and concave polygons, but does not tell us anything about certain complex polygons (consider a star polygon). For this you are relying on the sum of the exterior angles. What I seek is proof that all complex polygons have exterior angles which sum to more than 2π, which is also necessary to prove the correctness of your algorithm. $\endgroup$ Mar 13, 2021 at 17:43
  • $\begingroup$ For a plane polygon with no change in sign of the exterior angles the sum of the exterior angles will be $2\pi n$ where $n$ is the winding number about any point in the interior. $|n| \ge 1$ always and $|n| > 1$ for star polygons. $\endgroup$ Mar 13, 2021 at 20:20
  • $\begingroup$ fair point, thanks. But it doesn't really answer the question. If my conjecture is correct calculating and comparing cross products would be a waste of CPU cycles, so I seek proof of that. Thank you though $\endgroup$ Mar 13, 2021 at 20:23
  • 1
    $\begingroup$ Yes, I have not proved your conjecture (which I think is true). Are you sure you are not optimizing too soon? If your polygons are often/usually nonplanar then the cross product test will allow you to break early from a loop. If they are usually planar but often not convex you can save the planarity test for the end. Perhaps write the code and profile it to see where it bottlenecks. (I hope the downvote wasn't yours.) $\endgroup$ Mar 13, 2021 at 20:28
  • $\begingroup$ Most of the polygons i'll be checking I expect to be convex and planar. so ultimately I'd have to do all the checks for almost all of them. therefore less checks is better $\endgroup$ Mar 13, 2021 at 20:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .