5
$\begingroup$

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

Improve this question
$\endgroup$
12
  • $\begingroup$ 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? $\endgroup$
    – vzn
    Commented Feb 9, 2012 at 19:26
  • $\begingroup$ 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. $\endgroup$
    – Joe
    Commented Feb 9, 2012 at 19:29
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Commented Feb 9, 2012 at 19:30
  • $\begingroup$ @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". $\endgroup$
    – Janoma
    Commented Feb 9, 2012 at 19:41
  • $\begingroup$ @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? $\endgroup$
    – Joe
    Commented Feb 9, 2012 at 19:49

3 Answers 3

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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! $\endgroup$
    – Janoma
    Commented Feb 10, 2012 at 2:49
  • $\begingroup$ 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? $\endgroup$
    – Jeffε
    Commented Feb 10, 2012 at 6:37
  • $\begingroup$ 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. $\endgroup$
    – Janoma
    Commented Feb 10, 2012 at 15:41
  • $\begingroup$ I wondered about the sign issue; your positive examples all have positive winding numbers. $\endgroup$
    – Jeffε
    Commented Feb 12, 2012 at 14:13
  • $\begingroup$ 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! $\endgroup$
    – Janoma
    Commented Feb 13, 2012 at 19:07
4
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Janoma
    Commented Feb 9, 2012 at 18:40
  • $\begingroup$ And a point in polygon algorithm is not enough? (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). $\endgroup$
    – Marzio De Biasi
    Commented Feb 9, 2012 at 18:51
  • $\begingroup$ 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. $\endgroup$
    – Janoma
    Commented Feb 9, 2012 at 19:11
  • $\begingroup$ 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? $\endgroup$
    – Janoma
    Commented Feb 9, 2012 at 19:16
  • $\begingroup$ let us continue this discussion in chat $\endgroup$
    – Marzio De Biasi
    Commented Feb 9, 2012 at 19:28
1
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Janoma
    Commented Feb 9, 2012 at 19:20
  • $\begingroup$ 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. $\endgroup$
    – Janoma
    Commented Feb 9, 2012 at 19:31
  • $\begingroup$ The first example is not a polygon at all. $\endgroup$
    – Jeffε
    Commented Feb 9, 2012 at 22:42
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Commented Feb 9, 2012 at 23:53
  • $\begingroup$ @JɛffE Whoops! You're right. I was trying to come up with some illustrative edge cases. I think it's better now. $\endgroup$
    – Joe
    Commented Feb 10, 2012 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.