5

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 A decent polygon

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 An indecent polygon An indecent polygon An indecent polygon

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

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

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

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

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".

Community
  • 1
Janoma
  • 1,406
  • 11
  • 27
  • 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 Feb 09 '12 at 19:26
  • 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 Feb 09 '12 at 19:29
  • 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 Feb 09 '12 at 19:30
  • @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 Feb 09 '12 at 19:41
  • @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 Feb 09 '12 at 19:49
  • @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 Feb 09 '12 at 20:08
  • 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 Feb 09 '12 at 20:16
  • @Janoma I see what you mean now. I think you should explicitly mention the winding number and definition of interior in your question. – Joe Feb 09 '12 at 20:20
  • Well the first question to ask is if it has good manners. – Thomas Eding Feb 10 '12 at 05:18
  • 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 Feb 10 '12 at 16:06
  • 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 Feb 10 '12 at 17:14
  • (Digging old question...) Weakly simple polygon seems to fit your definition. Related post: http://cstheory.stackexchange.com/q/11512/1800 – Hsien-Chih Chang 張顯之 Jul 09 '14 at 21:27

3 Answers3

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

2) check for segment intersection on the expanded polygon;

See this page 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.

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • 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 Feb 09 '12 at 18:40
  • 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 Feb 09 '12 at 18:51
  • 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 Feb 09 '12 at 19:11
  • 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 Feb 09 '12 at 19:16
  • let us continue this discussion in chat – Marzio De Biasi Feb 09 '12 at 19:28
  • @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 Feb 09 '12 at 19:34
  • @Janoma: is my new interpretation wrong? – Marzio De Biasi Feb 10 '12 at 08:04
4

Offhand, it looks like a polygon P is decent if and only if the winding number of P around any point that is not actually on P is either 0 or 1.

Jeffε
  • 23,129
  • 10
  • 96
  • 163
  • 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 Feb 10 '12 at 02:49
  • 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ε Feb 10 '12 at 06:37
  • 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 Feb 10 '12 at 15:41
  • I wondered about the sign issue; your positive examples all have positive winding numbers. – Jeffε Feb 12 '12 at 14:13
  • 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 Feb 13 '12 at 19:07
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.

Joe
  • 1,327
  • 8
  • 19
  • 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 Feb 09 '12 at 19:20
  • 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 Feb 09 '12 at 19:31
  • The first example is not a polygon at all. – Jeffε Feb 09 '12 at 22:42
  • 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 Feb 09 '12 at 23:53
  • @JɛffE Whoops! You're right. I was trying to come up with some illustrative edge cases. I think it's better now. – Joe Feb 10 '12 at 01:03
  • @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ε Feb 10 '12 at 06:40
  • @Janoma After your edit, the question is much clearer. I've considerably cleaned up my definition. What do you think? – Joe Feb 10 '12 at 19:48
  • 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ε Feb 12 '12 at 14:16
  • @JɛffE 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 Feb 13 '12 at 00:10