<p>Offhand, it looks like a polygon P is decent if and only if the <a href="http://en.wikipedia.org/wiki/Winding_number" rel="nofollow">winding number</a> of P around any point that is not actually on P is either 0 or 1.</p>

CC BY-SA 3.0
2012-02-10T02:49:11.643Z
That might be true (will check tomorrow, it's late here), but I can't use a definition of the form "for all point $P$...", since I have to implement this (efficiently). Ideally, we look for some property on the vertices and other intersection of edges. I will elaborate tomorrow, updating my question with details. I'm too weary right now!
Janoma
CC BY-SA 3.0
2012-02-10T06:37:24.700Z
My proposed condition can be tested easily in O(n log n) time (and possibly in O(n) time, but that would take more thought).  But your objection is frankly weird; do you want something correct and possibly slow, or something fast and possibly wrong?
Jeffε
CC BY-SA 3.0
2012-02-10T15:41:07.100Z
After thinking about this, it looks like the closest to what we want. Actually, change that for "0, -1 or 1, but with no two points with winding numbers 1 and -1". The example **I5** has points with 1 and -1 at the same time. Will think more about this in the next few hours.
Janoma
CC BY-SA 3.0
2012-02-12T14:13:00.290Z
I wondered about the sign issue; your positive examples all have positive winding numbers.
Jeffε
CC BY-SA 3.0
2012-02-13T19:07:20.723Z
I'm setting this as the accepted answer because it seems to be the closest "definition" to my examples. I think I'll have to consider -1 as well in the end, because we don't mind rotation when there is no overlap. Thanks a lot for your answer!
Janoma
CC BY-SA 3.0
2012-02-09T22:48:05.083Z
2012-02-09T22:48:05.083Z
Jeffε
<p>This is a complete rewrite of my answer (I don't know if the interpretation is now correct, so tell me if you need further details) ...</p>

<p>1) solve conflicts in a shared vertex using a small circle centered on it and finding the intersection points between the circle and the segments that share that vertex; and add a small segment between two consecutive in/out segments (just "shorten" the end/start side of two consecutive in/out segments) (see figure)</p>

<p><img src="https://i.sstatic.net/kqC3B.jpg" alt="enter image description here"></p>

<p>2) check for segment intersection on the expanded polygon;</p>

<p>See <a href="http://paulbourke.net/geometry/lineline2d/" rel="nofollow noreferrer">this page</a> for an explanation of the algorithm. If, during a comparison, you find that the two segments are not parallel and $0 &lt; u_a &lt;1 \text{ or } 0 &lt; u_b &lt; 1 $ then the polygon can be classified as <em>indecent</em>.</p>

CC BY-SA 3.0
2012-02-09T18:40:03.397Z
We've thought of that already, but it doesn't work in the case with the shaded figure. In both cases the segments intersect only at their endpoints, yet one of them is decent and the other one is not. What I'm struggling with is how to deal with those overlaps.
Janoma
CC BY-SA 3.0
2012-02-09T18:51:22.617Z
And a point in polygon algorithm is not enough? (http://en.wikipedia.org/wiki/Point_in_polygon) Just compare the "closed" polygons and see if one is contained in another (if you want I can give further details).
Marzio De Biasi
CC BY-SA 3.0
2012-02-09T19:11:08.703Z
Comparing the "closed" polygons is not enough either. See my last example of an indecent polygon. Even if you consider the two triangles (i.e., the two closed polygons after adding the vertex at the intersection), you don't have an overlap, but it is not a case that you want anyway.
Janoma
CC BY-SA 3.0
2012-02-09T19:16:26.327Z
Consider the polygon $P_1=(0,0),(2,0),(1,2)$ and $P_2=(0,0),(2,0),(1,3),(1,2)$. By your definition of sign, $P_1$ and $P_2$ should have different signs, but looking at the picture I don't see that as natural at all. Am I missing something?
Janoma
CC BY-SA 3.0
2012-02-09T19:28:56.487Z
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/2445/discussion-between-vor-and-janoma)
Marzio De Biasi
CC BY-SA 3.0
2012-02-09T19:34:52.423Z
@Vor $O(n^2)$ time is needed for line intersection, but segment intersection can be done much faster $O(n \log n + k)$, and a polygon is a special case of *that* and $O(n + k)$ should be possible.
Joe
CC BY-SA 3.0
2012-02-10T08:04:29.680Z
@Janoma: is my new interpretation wrong?
Marzio De Biasi
CC BY-SA 3.0
2012-02-09T18:19:11.267Z
2012-02-09T20:57:47.563Z
2012-02-09T20:57:47.563Z
Marzio De Biasi
<p>Based on new information in the question, the following are requirements for a decent polygon:</p>

<ol>
<li>The input is a valid polygon. (e.g. it's closed, no stray edges)</li>
<li><p>The polygon does not <em>overlap itself</em></p>

<p>a) Every edge does not intersect the interior of any other edge.</p>

<p>b) Two sub-paths may not cross each other at a vertex (as illustrated by I5)</p>

<p>c) The absolute value of the winding number is at most 1. </p></li>
</ol>

<p>I think that (a), (b) and (c) can each be detected in linear time by walking around the polygon.</p>

<p><a href="http://users.iit.demokritos.gr/~agalex/publications/COMGEO.pdf" rel="nofollow">Relevant reference for winding number</a>.</p>

CC BY-SA 3.0
2012-02-09T19:20:16.727Z
Doesn't work for the same reason as Vor's answer. In your definition you are not considering the direction of the edges (orientation). In my 2nd decent example and 3rd indecent example, no interior of an edge intersects the interior of another edge, so neither would be indecent by your definition.
Janoma
CC BY-SA 3.0
2012-02-09T19:31:32.720Z
It matters because the interior of the indecent one is the interior of the whole big triangle, while in the other one is the difference between the larger and the smaller (the shaded picture). The same set of points define different polygons because of the orientation, so the order in which the vertices are given *does* matter.
Janoma
CC BY-SA 3.0
2012-02-09T22:42:56.680Z
The first example is not a polygon at all.
Jeffε
CC BY-SA 3.0
2012-02-09T23:53:26.757Z
a polygon is built out of undirected edges but a key part of the problem seems to be the directed edges & polygon 1 does not have directed edges following in a path
vzn
CC BY-SA 3.0
2012-02-10T01:03:18.987Z
@JɛﬀE Whoops! You're right. I was trying to come up with some illustrative edge cases. I think it's better now.
Joe
CC BY-SA 3.0
2012-02-10T06:40:45.493Z
@vzn: Technically, a polygon is defined by a cyclic *sequence* of points connected by line segments.  The cycle of vertices defines a direction for every edge.  (Traversing the sequence of vertices backward gives you the "same" polygon, so in some sense the directions are arbitrary, but once you fix a single edge direction, all the other edge directions are well defined.)
Jeffε
CC BY-SA 3.0
2012-02-10T19:48:05.393Z
@Janoma After your edit, the question is *much* clearer. I've considerably cleaned up my definition. What do you think?
Joe
CC BY-SA 3.0
2012-02-12T14:16:54.387Z
Despite what @Joe's reference suggests, summing angles to compute winding numbers is a **terrible** idea.  Shoot an arbitrary ray from the reference point; the winding number is the number of times the polygon crosses the ray from right to left, minus the number of times the polygon crosses the ray from left to right.
Jeffε
CC BY-SA 3.0
2012-02-13T00:10:56.573Z
@JɛﬀE Would you mind discussing why it's a terrible idea, perhaps in chat? I'm not necessarily trying to defend the reference; it was just the first reference I found for an algorithm for calculating the winding number. But I am curious...
Joe
CC BY-SA 3.0
2012-02-09T19:01:00.950Z
2012-02-10T19:53:57.087Z
2012-02-10T19:53:57.087Z
Joe
<blockquote>
<p><strong>Acknowledgments/apologies (Feb 10).</strong> Thanks to those who have taken the time of reading this question and trying to find an answer (I've upvoted the three answers so far). I hope that after some iterations we can get to something good, so please forgive me for changing stuff and for the lack of precision and/or clarity. It's frustrating for me as well, since I'm working for a project where it is expected for us to give priority to performance over (a beautiful) formalization.</p>
<p><strong>Update (Feb 10):</strong> I am changing one decent case to indecent, and explaining why. The reason is practical and it comes from the application.</p>
</blockquote>
<p>I am working on a problem in which polygons are decomposed in a way similar to triangulation. Before actually decomposing the input, we have to classify the polygon in one of two categories:</p>
<ul>
<li><strong>Decent.</strong> The polygon is all we ever wanted. We may proceed to the decomposition.</li>
<li><strong>Indecent.</strong> The polygon needs further processing before being decomposed.</li>
</ul>
<p>After taking a quick look at some books and papers, it seems to me that defining a polygon as a &quot;simple closed curve on the plane&quot; is quite the standard, and also the usual assumption for an input in algorithms (to avoid self-intersections and degenerate cases).</p>
<p>However, we want to make this definition in such a way that <em>simple polygons</em> <span class="math-container">$\subsetneq$</span> <em>decent polygons</em>, that is, the class of decent polygons is greater than the class of simple polygons.</p>
<p>Let's forget about simple polygons, then, since they are so nice, and let's try to define &quot;the rest&quot; of decent polygons. We have a rough idea of what we want to define as <em>decent</em> based of examples.</p>
<h2>Decent polygons</h2>
<p>In the following examples (label them <strong>D1</strong> and <strong>D2</strong>, from left to right), a point on the plane belongs to more than two edges (four edges, in fact), but this is not really a problem since there is no overlap (of a positive area).</p>
<p><img src="https://i.sstatic.net/bnDPz.jpg" alt="A decent polygon" /> <img src="https://i.sstatic.net/vOQIV.jpg" alt="A decent polygon" /></p>
<p>The labels of the edges indicate the order in which they are given. This order is important to us because we want to consider orientation of (sub-)polygons to define the interior of the (whole) polygon.</p>
<h2>Indecent polygons</h2>
<p>Label the following examples <strong>I1</strong>, <strong>I2</strong>, <strong>I3</strong> and <strong>I4</strong>, from left to right. This is what we don't want. There is an overlap in the first two examples we'd rather avoid (for example, separating the input in two different inputs, one with edges 1, 2 and 3, and the other with edges 4, 5 and 6). In <strong>I3</strong> we have some kind of sub-polygon completely contained in the main polygon. We don't want that either. I will explain later why <strong>D2</strong> is not the same as <strong>I3</strong>.</p>
<p><img src="https://i.sstatic.net/FE0xd.jpg" alt="An indecent polygon" /> <img src="https://i.sstatic.net/l22xt.jpg" alt="An indecent polygon" /> <img src="https://i.sstatic.net/UeyHy.jpg" alt="An indecent polygon" /> <img src="https://i.sstatic.net/bDh7M.jpg" alt="An indecent polygon" /></p>
<p>In <strong>I4</strong> there is no overlap, but, as before, we would prefer to have that as two separate inputs, even though we need to introduce an additional vertex. We don't want intersection of segments in points <strong>other than their endpoints</strong> (i.e., the only intersections allowed are in vertices of the polygon).</p>
<p>Even so, the following polygon <strong>I5</strong> is indecent. Note that the triangle 456 is oriented clockwise, and we consider it to have negative area.</p>
<p><img src="https://i.sstatic.net/wppCu.jpg" alt="An indecent polygon" /></p>
<h2>Why <strong>D1</strong> is not the same as <strong>I5</strong></h2>
<p>If you follow the path given by the ordered edges, you have that, in <strong>D1</strong>, the subpath 3-4 (in red) does not cross the subpath 6-1 (in black).</p>
<p><img src="https://i.sstatic.net/AaUmF.jpg" alt="A good self-intersection" /></p>
<p>However, in <strong>I5</strong>, the subpath 3-4 (in red) does cross the subpath 6-1 (in black), and we don't want this.</p>
<p><img src="https://i.sstatic.net/TqxDQ.jpg" alt="A bad self-intersection" /></p>
<h2>Why <strong>D2</strong> is not the same as <strong>I3</strong></h2>
<p>In our application, <strong>D2</strong> is different from <strong>I3</strong>. There is no overlap in <strong>D2</strong> and its interior can be seen as a shaded area in the following figure.</p>
<p><img src="https://i.sstatic.net/WkwmP.jpg" alt="The interior of a decent polygon" /></p>
<h2>How to define this?</h2>
<p>We're trying to find a definition for these cases. As I said before, &quot;simple&quot; is not enough, but what's more important to us is that the definition should be (if possible) algorithmic, in the sense that an (efficient) algorithm, not a human, should decide whether a given polygon is decent or not. Also, we are willing to relax a case or two if there is a definition that works for almost all cases, but provides an efficient algorithm to verify it.</p>
<p>I don't know whether this has been studied before. Feel free to point me to the appropriate literature if you think it would help, but I have checked a few references and all I've found ranges from &quot;we will assume all polygons are simple&quot; to &quot;non-simple/degenerate cases are left as an exercise&quot;.</p>

CC BY-SA 3.0
2012-02-09T19:26:55.323Z
you should label each example. but anyway I think replies should reveal/treat specifically the case of decent #2 vs indecent #3 (as you have). which only have different orderings but are the same if order of vertices is not taken into account. it appears to me you want something that will take order of the vertices into acct but then, what algorithm would distinguish indecent #2 from decent #3?
vzn
CC BY-SA 3.0
2012-02-09T19:29:06.313Z
It seems to me that your second decent and your third indecent polygon should be the same: either both decent or both indecent. I'm not sure why clockwise vs counter clockwise matters for the internal polygon.
Joe
CC BY-SA 3.0
2012-02-09T19:30:49.310Z
it appears the algorithm should take into account the "interior" of a _partially drawn_ polygon maybe as joe is doing, but one has to define what that is exactly
vzn
CC BY-SA 3.0
2012-02-09T19:41:37.497Z
@Joe That depends on the application you have in mind, and we need to distinguish the interior of those two, as explained and depicted. When you draw the internal polygon clockwise, you "discard" part of the interior you have "so far".
Janoma
CC BY-SA 3.0
2012-02-09T19:49:29.563Z
@Janoma The two polygons are isomorphic up to vertex labeling, which would usually mean they are the same for all practical purposes. Your last comment indicates to me that maybe it is different because of a process of UI interaction. Does clockwise always mean discard?
Joe
CC BY-SA 3.0
2012-02-09T20:08:52.500Z
@Joe Examples D2 and I3 might be isomorphic as directed graphs, but they don't define the same polygon (the 5th vertex doesn't coincide, for example).
Janoma
CC BY-SA 3.0
2012-02-09T20:16:34.857Z
BTW, the problem has nothing to do with UI (there's no UI involved at all). Changing orientation means you "reverse" the previous status of the area. A formal definition of interior uses the parity of the winding number. In the decent case, the winding number of a point in the interior of the smaller triangle is 1, while in the indecent case is 0.
Janoma
CC BY-SA 3.0
2012-02-09T20:20:22.817Z
@Janoma I see what you mean now. I think you should explicitly mention the winding number and definition of interior in your question.
Joe
CC BY-SA 3.0
2012-02-10T05:18:50.807Z
Well the first question to ask is if it has good manners.
Thomas Eding
CC BY-SA 3.0
2012-02-10T16:06:11.077Z
after the new edits talking about clockwise vs counterclockwise I have to ask-- what is the evidence that there is actually an algorithm that gives you an answer? is a human generating these examples/counterexamples?
vzn
CC BY-SA 3.0
2012-02-10T17:14:24.703Z
Yep, these examples are generated by humans, each with some position ("this is good/bad because..."). For what we were talking now, rotation is only relevant when there is an overlap. If we can characterize these cases without the notion of direction, so be it, but I had to mention it because it might be strictly necessary to consider it. As for the evidence, we don't have much except for our intuition.
Janoma
CC BY-SA 3.0
2014-07-09T21:27:05.440Z
(Digging old question...)  Weakly simple polygon seems to fit your definition.  Related post: http://cstheory.stackexchange.com/q/11512/1800
Hsien-Chih Chang 張顯之
<cg.comp-geom>
What defines a "decent" polygon?
Janoma
# What defines a "decent" polygon?

(Asked by: username_0 on 2012-02-09)

> **Acknowledgments/apologies (Feb 10).** Thanks to those who have taken the time of reading this question and trying to find an answer (I've upvoted the three answers so far). I hope that after some iterations we can get to something good, so please forgive me for changing stuff and for the lack of precision and/or clarity. It's frustrating for me as well, since I'm working for a project where it is expected for us to give priority to performance over (a beautiful) formalization.
>
> **Update (Feb 10):** I am changing one decent case to indecent, and explaining why. The reason is practical and it comes from the application.

I am working on a problem in which polygons are decomposed in a way similar to triangulation. Before actually decomposing the input, we have to classify the polygon in one of two categories:

* **Decent.** The polygon is all we ever wanted. We may proceed to the decomposition.
* **Indecent.** The polygon needs further processing before being decomposed.

After taking a quick look at some books and papers, it seems to me that defining a polygon as a "simple closed curve on the plane" is quite the standard, and also the usual assumption for an input in algorithms (to avoid self-intersections and degenerate cases).

However, we want to make this definition in such a way that *simple polygons* $\subsetneq$ *decent polygons*, that is, the class of decent polygons is greater than the class of simple polygons.

Let's forget about simple polygons, then, since they are so nice, and let's try to define "the rest" of decent polygons. We have a rough idea of what we want to define as *decent* based of examples.

## Decent polygons

In the following examples (label them **D1** and **D2**, from left to right), a point on the plane belongs to more than two edges (four edges, in fact), but this is not really a problem since there is no overlap (of a positive area).

![A decent polygon](https://i.sstatic.net/bnDPz.jpg) ![A decent polygon](https://i.sstatic.net/vOQIV.jpg)

The labels of the edges indicate the order in which they are given. This order is important to us because we want to consider orientation of (sub-)polygons to define the interior of the (whole) polygon.

## Indecent polygons

Label the following examples **I1**, **I2**, **I3** and **I4**, from left to right. This is what we don't want. There is an overlap in the first two examples we'd rather avoid (for example, separating the input in two different inputs, one with edges 1, 2 and 3, and the other with edges 4, 5 and 6). In **I3** we have some kind of sub-polygon completely contained in the main polygon. We don't want that either. I will explain later why **D2** is not the same as **I3**.

![An indecent polygon](https://i.sstatic.net/FE0xd.jpg) ![An indecent polygon](https://i.sstatic.net/l22xt.jpg) ![An indecent polygon](https://i.sstatic.net/UeyHy.jpg) ![An indecent polygon](https://i.sstatic.net/bDh7M.jpg)

In **I4** there is no overlap, but, as before, we would prefer to have that as two separate inputs, even though we need to introduce an additional vertex. We don't want intersection of segments in points **other than their endpoints** (i.e., the only intersections allowed are in vertices of the polygon).

Even so, the following polygon **I5** is indecent. Note that the triangle 456 is oriented clockwise, and we consider it to have negative area.

![An indecent polygon](https://i.sstatic.net/wppCu.jpg)

## Why **D1** is not the same as **I5**

If you follow the path given by the ordered edges, you have that, in **D1**, the subpath 3-4 (in red) does not cross the subpath 6-1 (in black).

![A good self-intersection](https://i.sstatic.net/AaUmF.jpg)

However, in **I5**, the subpath 3-4 (in red) does cross the subpath 6-1 (in black), and we don't want this.

![A bad self-intersection](https://i.sstatic.net/TqxDQ.jpg)

## Why **D2** is not the same as **I3**

In our application, **D2** is different from **I3**. There is no overlap in **D2** and its interior can be seen as a shaded area in the following figure.

![The interior of a decent polygon](https://i.sstatic.net/WkwmP.jpg)

## How to define this?

We're trying to find a definition for these cases. As I said before, "simple" is not enough, but what's more important to us is that the definition should be (if possible) algorithmic, in the sense that an (efficient) algorithm, not a human, should decide whether a given polygon is decent or not. Also, we are willing to relax a case or two if there is a definition that works for almost all cases, but provides an efficient algorithm to verify it.

I don't know whether this has been studied before. Feel free to point me to the appropriate literature if you think it would help, but I have checked a few references and all I've found ranges from "we will assume all polygons are simple" to "non-simple/degenerate cases are left as an exercise".

**Tags:** cg.comp-geom

> **Comments:**
> **username_1**: you should label each example. but anyway I think replies should reveal/treat specifically the case of decent #2 vs indecent #3 (as you have). which only have different orderings but are the same if order of vertices is not taken into account. it appears to me you want something that will take order of the vertices into acct but then, what algorithm would distinguish indecent #2 from decent #3?  
> **username_2**: It seems to me that your second decent and your third indecent polygon should be the same: either both decent or both indecent. I'm not sure why clockwise vs counter clockwise matters for the internal polygon.  
> **username_1**: it appears the algorithm should take into account the "interior" of a _partially drawn_ polygon maybe as joe is doing, but one has to define what that is exactly  
> **username_0**: @username_2 That depends on the application you have in mind, and we need to distinguish the interior of those two, as explained and depicted. When you draw the internal polygon clockwise, you "discard" part of the interior you have "so far".  
> **username_2**: @username_0 The two polygons are isomorphic up to vertex labeling, which would usually mean they are the same for all practical purposes. Your last comment indicates to me that maybe it is different because of a process of UI interaction. Does clockwise always mean discard?  
> **username_0**: @username_2 Examples D2 and I3 might be isomorphic as directed graphs, but they don't define the same polygon (the 5th vertex doesn't coincide, for example).  
> **username_0**: BTW, the problem has nothing to do with UI (there's no UI involved at all). Changing orientation means you "reverse" the previous status of the area. A formal definition of interior uses the parity of the winding number. In the decent case, the winding number of a point in the interior of the smaller triangle is 1, while in the indecent case is 0.  
> **username_2**: @username_0 I see what you mean now. I think you should explicitly mention the winding number and definition of interior in your question.  
> **username_3**: Well the first question to ask is if it has good manners.  
> **username_1**: after the new edits talking about clockwise vs counterclockwise I have to ask-- what is the evidence that there is actually an algorithm that gives you an answer? is a human generating these examples/counterexamples?  
> **username_0**: Yep, these examples are generated by humans, each with some position ("this is good/bad because..."). For what we were talking now, rotation is only relevant when there is an overlap. If we can characterize these cases without the notion of direction, so be it, but I had to mention it because it might be strictly necessary to consider it. As for the evidence, we don't have much except for our intuition.  
> **username_4**: (Digging old question...)  Weakly simple polygon seems to fit your definition.  Related post: http://cstheory.stackexchange.com/q/11512/1800  

---

## 3 answers

### Answer by username_5 on 2012-02-09. Score: 4 | Accepted answer

Offhand, it looks like a polygon P is decent if and only if the [winding number](http://en.wikipedia.org/wiki/Winding_number) of P around any point that is not actually on P is either 0 or 1.

> **Comments:**
> **username_0**: That might be true (will check tomorrow, it's late here), but I can't use a definition of the form "for all point $P$...", since I have to implement this (efficiently). Ideally, we look for some property on the vertices and other intersection of edges. I will elaborate tomorrow, updating my question with details. I'm too weary right now!  
> **username_5**: My proposed condition can be tested easily in O(n log n) time (and possibly in O(n) time, but that would take more thought).  But your objection is frankly weird; do you want something correct and possibly slow, or something fast and possibly wrong?  
> **username_0**: After thinking about this, it looks like the closest to what we want. Actually, change that for "0, -1 or 1, but with no two points with winding numbers 1 and -1". The example **I5** has points with 1 and -1 at the same time. Will think more about this in the next few hours.  
> **username_5**: I wondered about the sign issue; your positive examples all have positive winding numbers.  
> **username_0**: I'm setting this as the accepted answer because it seems to be the closest "definition" to my examples. I think I'll have to consider -1 as well in the end, because we don't mind rotation when there is no overlap. Thanks a lot for your answer!  

---

### Answer by username_6 on 2012-02-09. Score: 4

This is a complete rewrite of my answer (I don't know if the interpretation is now correct, so tell me if you need further details) ...

1) solve conflicts in a shared vertex using a small circle centered on it and finding the intersection points between the circle and the segments that share that vertex; and add a small segment between two consecutive in/out segments (just "shorten" the end/start side of two consecutive in/out segments) (see figure)

![enter image description here](https://i.sstatic.net/kqC3B.jpg)

2) check for segment intersection on the expanded polygon;

See [this page](http://paulbourke.net/geometry/lineline2d/) for an explanation of the algorithm. If, during a comparison, you find that the two segments are not parallel and $0 < u\_a <1 \text{ or } 0 < u\_b < 1 $ then the polygon can be classified as *indecent*.

> **Comments:**
> **username_0**: We've thought of that already, but it doesn't work in the case with the shaded figure. In both cases the segments intersect only at their endpoints, yet one of them is decent and the other one is not. What I'm struggling with is how to deal with those overlaps.  
> **username_6**: And a point in polygon algorithm is not enough? (http://en.wikipedia.org/wiki/Point_in_polygon) Just compare the "closed" polygons and see if one is contained in another (if you want I can give further details).  
> **username_0**: Comparing the "closed" polygons is not enough either. See my last example of an indecent polygon. Even if you consider the two triangles (i.e., the two closed polygons after adding the vertex at the intersection), you don't have an overlap, but it is not a case that you want anyway.  
> **username_0**: Consider the polygon $P_1=(0,0),(2,0),(1,2)$ and $P_2=(0,0),(2,0),(1,3),(1,2)$. By your definition of sign, $P_1$ and $P_2$ should have different signs, but looking at the picture I don't see that as natural at all. Am I missing something?  
> **username_6**: let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/2445/discussion-between-vor-and-janoma)  
> **username_2**: @Vor $O(n^2)$ time is needed for line intersection, but segment intersection can be done much faster $O(n \log n + k)$, and a polygon is a special case of *that* and $O(n + k)$ should be possible.  
> **username_6**: @username_0: is my new interpretation wrong?  

---

### Answer by username_2 on 2012-02-09. Score: 1

Based on new information in the question, the following are requirements for a decent polygon:

1. The input is a valid polygon. (e.g. it's closed, no stray edges)
2. The polygon does not *overlap itself*

   a) Every edge does not intersect the interior of any other edge.

   b) Two sub-paths may not cross each other at a vertex (as illustrated by I5)

   c) The absolute value of the winding number is at most 1.

I think that (a), (b) and (c) can each be detected in linear time by walking around the polygon.

[Relevant reference for winding number](http://users.iit.demokritos.gr/~agalex/publications/COMGEO.pdf).

> **Comments:**
> **username_0**: Doesn't work for the same reason as Vor's answer. In your definition you are not considering the direction of the edges (orientation). In my 2nd decent example and 3rd indecent example, no interior of an edge intersects the interior of another edge, so neither would be indecent by your definition.  
> **username_0**: It matters because the interior of the indecent one is the interior of the whole big triangle, while in the other one is the difference between the larger and the smaller (the shaded picture). The same set of points define different polygons because of the orientation, so the order in which the vertices are given *does* matter.  
> **username_5**: The first example is not a polygon at all.  
> **username_1**: a polygon is built out of undirected edges but a key part of the problem seems to be the directed edges & polygon 1 does not have directed edges following in a path  
> **username_2**: @JɛﬀE Whoops! You're right. I was trying to come up with some illustrative edge cases. I think it's better now.  
> **username_5**: @username_1: Technically, a polygon is defined by a cyclic *sequence* of points connected by line segments.  The cycle of vertices defines a direction for every edge.  (Traversing the sequence of vertices backward gives you the "same" polygon, so in some sense the directions are arbitrary, but once you fix a single edge direction, all the other edge directions are well defined.)  
> **username_2**: @username_0 After your edit, the question is *much* clearer. I've considerably cleaned up my definition. What do you think?  
> **username_5**: Despite what @username_2's reference suggests, summing angles to compute winding numbers is a **terrible** idea.  Shoot an arbitrary ray from the reference point; the winding number is the number of times the polygon crosses the ray from right to left, minus the number of times the polygon crosses the ray from left to right.  
> **username_2**: @JɛﬀE Would you mind discussing why it's a terrible idea, perhaps in chat? I'm not necessarily trying to defend the reference; it was just the first reference I found for an algorithm for calculating the winding number. But I am curious...  

---

