Decomposition to Convex Polygons

Question

This question is a little involved. I wrote an algorithm for breaking up a simple polygon into convex subpolygons, but now I'm having trouble proving that it's not optimal (i.e. minimal number of convex polygons using Steiner points (added vertices)). My prof is adamant that it can't be done with a greedy algorithm such as this one, but I can't think of a counterexample.

So, if anyone can prove my algorithm is suboptimal (or optimal), I would appreciate it.

The easiest way to explain my algorithm with pictures (these are from an older suboptimal version)

What my algorithm does, is extends the line segments around the point i across until it hits a point on the opposite edge.

If there is no vertex within this range, it creates a new one (the red point) and connects to that:

If there is one or more vertices in the range, it connects to the closest one. This usually produces a decomposition with the fewest number of convex polygons:

However, in some cases it can fail -- in the following figure, if it happens to connect the middle green line first, this will create an extra unneeded polygon. To this I propose double checking all the edges (diagonals) we've added, and check that they are all still necessary. If not, remove it:

In some cases, however, this is not enough. See this figure:

Replacing a-b and c-d with a-c would yield a better solution. In this scenario though, there's no edges to remove so this poses a problem. In this case I suggest an order of preference: when deciding which vertex to connect a reflex vertex to, it should choose the vertex with the highest priority:

lowest) closest vertex

med) closest reflex vertex

highest) closest reflex that is also in range when working backwards (hard to explain) --

In this figure, we can see that the reflex vertex 9 chose to connect to 12 (because it was closest), when it would have been better to connect to 5. Both vertices 5 and 12 are in the range as defined by the extended line segments 10-9 and 8-9, but vertex 5 should be given preference because 9 is within the range given by 4-5 and 6-5, but NOT in the range given by 13-12 and 11-12. i.e., the edge 9-12 elimates the reflex vertex at 9, but does NOT eliminate the reflex vertex at 12, but it CAN eliminate the reflex vertex at 5, so 5 should be given preference.

It is possible that the edge 5-12 will still exist with this modified version, but it can be removed during post-processing.

Are there any cases I've missed?

---

Pseudo-code (requested by John Feminella) -- this is missing the bits under Figures 3 and 5

assume vertices in `poly` are given in CCW order
let 'good reflex' (better term??) mean that if poly[i] is being compared with poly[j], then poly[i] is in the range given by the rays poly[j-1], poly[j] and poly[j+1], poly[j]

for each vertex poly[i]
    if poly[i] is reflex
        find the closest point of intersection given by the ray starting at poly[i-1] and extending in the direction of poly[i] (call this lower bound)
        repeat for the ray given by poly[i+1], poly[i] (call this upper bound)

        if there are no vertices along boundary of the polygon in the range given by the upper and lower bounds
            create a new vertex exactly half way between the lower and upper bound points (lower and upper will lie on the same edge)
            connect poly[i] to this new point
        else
            iterate along the vertices in the range given by the lower and upper bounds, for each vertex poly[j]
                if poly[j] is a 'good reflex'
                    if no other good reflexes have been found
                        save it (overwrite any other vertex found)
                    else
                        if it is closer then the other good reflexes vertices, save it
                else
                    if no good reflexes have been found and it is closer than the other vertices found, save it
            connect poly[i] to the best candidate
        repeat entire algorithm for both halves of the polygon that was just split
// no reflex vertices found, then `poly` is convex
save poly

---

Turns out there is one more case I didn't anticipate: [Figure 5]

My algorithm will attempt to connect vertex 1 to 4, unless I add another check to make sure it can. So I propose stuffing everything "in the range" onto a priority queue using the priority scheme I mentioned above, then take the highest priority one, check if it can connect, if not, pop it off and use the next. I think this makes my algorithm O(r n log n) if I optimize it right.

---

I've put together a website that loosely describes my findings. I tend to move stuff around, so get it while it's hot.

Velasquez

Some (pseudo)code would help a lot if you can provide it. It's too hard to tell from prose what's going on here. – Sarabia

Answer 1

I believe the regular five pointed star (e.g. with alternating points having collinear segments) is the counterexample you seek.

Edit in response to comments

In light of my revised understanding, a revised answer: try an acute five pointed star (e.g. one with arms sufficiently narrow that only the three points comprising the arm opposite the reflex point you are working on are within the range considered "good reflex points"). At least working through it on paper it appears to give more than the optimal. However, a final reading of your code has me wondering: what do you mean by "closest" (i.e. closest to what)?

Note

Even though my answer was accepted, it isn't the counter example we initially thought. As @Mark points out in the comments, it goes from four to five at exactly the same time as the optimal does.

Flip-flop, flip flop

On further reflection, I think I was right after all. The optimal bound of four can be retained in a acute star by simply assuring that one pair of arms have collinear edges. But the algorithm finds five, even with the patch up.

I get this:

removing dead ImageShack link

When the optimal is this:

removing dead ImageShack link

Josphinejoss

Can you give a few more details? If I'm not mistaken the optimal solution requires 4 polygons, but why would my algorithm fail? I may have screwed up the edge cases, but assuming I haven't, my algorithm should allow a reflex vertex to connect to collinear vertices and it should all work out nicely. – Velasquez

Even if the reflex vertices don't connect to their neighbours, but attempt to cross the center of the star (perhaps all reflex vertices are equidistant) the "cleanup" step should fix it. – Velasquez

@Mark -- It doesn't seem to work by my reading (I get five polygons), but I may be missing something. 1) Is the "cleanup step" of which you speak part of the pseudo code? 2) Have you actually implemented the algorithm or are you just executing by hand as well? – Josphinejoss

Oh.. no, I forgot to include that in the pseudo code. I've written it just below 'figure 3'. I have a partially implemented algorithm; it doesn't include all my latest revisions. So for the time being, I'm executing 'by hand' too. – Velasquez

I'm afraid I can't picture the star you have in mind from your description. With 5 points, how do you define the opposite arm? By "closest" I mean the Euclidean distance between vertices i and j. i being the reflex vertex we are trying to connect to something, and j iterates over "the range" – Velasquez

Admittedly, the entire algorithm is probably pretty naive, but it seems to work pretty well in practice. – Velasquez

I've added another pic to the question to help clarify things (img6.imageshack.us/img6/5001/explanation.gif) – Velasquez

@Mark the arm opposite the reflex point you are working with. – Josphinejoss

I'm going to give you the checkmark before time runs out... it looks like you may have solved it!! Let me investigate this a bit further... – Velasquez

wait.... if I've interpreted you correctly, then no you haven't. img27.imageshack.us/img27/4557/starduf.gif while this does force the star to be divided into 5 polies instead of 4....the optimal is also 5 now. would you mind doing up a quick pic in MS paint if you had something else in mind? – Velasquez

this is quite easy to see actually: img15.imageshack.us/img15/6057/star2j.gif if you pull each of the points a,c,d,f,h outwards slightly, it meets your condition, but then the "triangle" c,e,h is no longer convex, so this is the best we can do – Velasquez

sigh That's right. Doh! Is there any way to cede reputation points to someone else? I'll do so if you'd rather designate someone else the accepted answer. – Josphinejoss

Hold the presses. I think I was right after all. See pretty pictures, above. – Josphinejoss

Don't worry about, the other answers weren't right either, and you've helped the most. You almost had my convinced with this last example! But the top left diagonal would actually connect straight across to the right (since it prefers vertices over Steiner points), and the the diagonal directly – Velasquez

below it could be removed during the cleanup process! – Velasquez

@Mark -- Man, you're tricky. If I think of another one, I'll post it, but I think the five pointed star case is dead. – Josphinejoss

Answer 2

I think your algorithm cannot be optimal because it makes no use of any measure of optimality. You use other metrics like 'closest' vertices, and checking for 'necessary' diagonals.

To drive a wedge between yours and an optimal algorithm, we need to exploit that gap by looking for shapes with close vertices which would decompose badly. For example (ignore the lines, I found this on the intertubenet):

concave polygon which forms a G or U shape http://avocado-cad.wiki.sourceforge.net/space/showimage/2007-03-19_-_convexize.png

You have no protection against the centre-most point being connected across the concave 'gap', which is external to the polygon.

Your algorithm is also quite complex, and may be overdoing it - just like complex code, you may find bugs in it because complex code makes complex assumptions.

Consider a more extensive initial stage to break the shape into more, simpler shapes - like triangles - and then an iterative or genetic algorithm to recombine them. You will need a stage like this to combine any unnecessary divisions between your convex polys anyway, and by then you may have limited your possible decompositions to only sub-optimal solutions.

At a guess something like:

1. decompose into triangles
2. non-deterministically generate a number of recombinations
3. calculate a quality metric (number of polys)
4. select the best x% of the recombinations
5. partially decompose each using triangles, and generate a new set of recombinations
6. repeat from 4 until some measure of convergence is reached

Bothersome

diagonals crossing the gap -- see the tidbit under 'figure 5'. You're quite right that I missed that at first...but it's easy enough to fix, albeit it adds some time complexity. the problem with decomposing into triangles is that it may require two diagonals to remove a single reflex vertex if it – Velasquez

isn't decomposed nicely...my algorithm ensures that the diagonals are placed such that it will always remove a reflex on every iteration. your algorithm, while it should work, seems like it is just as ... "magical". you're using probabilities rather than concrete theorems to achieve optimality – Velasquez

too. which is fine, but it doesn't look much simpler. I could combine mine (or your) algorithm with some ideas from Keil to increase the likelihood of an optimal solution further (by say, trying ALL "good reflexes" and then taking the best solution) but I'm not sure your solution has that advantage – Velasquez

also, probably most importantly, your solution doesn't take advantage of Steiner points :p which probably the biggest advantage my solution has over other algorithms, even if they don't occur terribly frequently -- they shave 1 poly off the final solution 100% of the time I believe – Velasquez

not the poo-poo your algorithm or anything, I just don't see a real advantage. my code is fairly complex, yes, but uh...take a look at Chazelle's algorithm :p I don't think anyone's even bothered to implement it, it's ridiculous :) I think sometimes we have to take that hit. – Velasquez

with regard to exploiting closest vertices -- that's exactly what I've been looking for, but in all the cases I've looked at, where there's a choice between two vertexes with the same priority of different distances.. it doesn't ever seem to matter which is chosen – Velasquez

@Phil H -- I played with something very like this figure earlier, and his algorithm seemed to work on it (it gives four polygons, which I believe is optimal, even without post his processing / cleanup pass). – Josphinejoss

Answer 3

but vertex 5 should be given preference because 9 is within the range given by 4-5 and 6-5

What would you do if 4-5 and 6-5 were even more convex so that 9 didn't lie within their range? Then by your rules the proper thing to do would be to connect 9 to 12 because 12 is the closest reflex vertex, which would be suboptimal.

Mcdaniels

If you mean moving vertices 4 and 6 closer together in Figure 4, then the polygon given by 3,4,5,9,10,11,12 would NOT be convex anyway if 9 was connected to 5 (4,5,9 would be reflex). Therefore, the solution you see now would actually be optimal. – Velasquez

Answer 4

Found it :( They're actually quite obvious.

---

*dead imageshack img*

A four leaf clover will not be optimal if Steiner points are allowed... the red vertices could have been connected.

---

*dead imageshack img*

It won't even be optimal without Steiner points... 5 could be connected to 14, removing the need for 3-14, 3-12 AND 5-12. This could have been two polygons better! Ouch!

Velasquez