Decomposition to Convex Polygons

tags:

geometry

views:

949

answers:

+5 Q:

Decomposition to Convex Polygons

+1 A:

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.

DasBoot 2009-03-29 05:30:00

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.

Mark 2009-03-29 18:11:01

+2 A:

eed3si9n 2009-04-04 07:33:36

You mean this is an optimal solution to a polygon you don't think my algorithm can handle? It's hard to tell exactly, but I believe my algorithm would produce an output like this: http://img17.imageshack.us/img17/7549/27447389.png(I went over yours with orange lines) -- it also produces 9 polies...

Mark 2009-04-04 10:19:13

albeit a bit uglier than yours, it's still optimal. Unless you can do it fewer than 9... I don't think you can?

Mark 2009-04-04 10:20:02

Or maybe like this http://img3.imageshack.us/img3/3633/12991084.pngI can't quite tell if 2,3,13 is reflex or not. If it isn't, this will be the output, otherwise the other one will be the output. Both are 9 anyways.

Mark 2009-04-04 10:26:29

Actually I lied.. you numbered your vertices CW, but the algorithm works CCW (not that it really matters -- it'll fix it automatically). Anyway, working CCW, I came up with this sol'n http://img11.imageshack.us/img11/8818/69174117.pngWhich only uses 8 polies... my algorithm *might* produce this

Mark 2009-04-04 10:33:29

I have to think about it a bit more... it's 3 am. Good example though.. I don't know if this is what you had in mind.

Mark 2009-04-04 10:34:17

Actually I'm pretty sure my algo *would* produce the 8-poly sol'n...

Mark 2009-04-04 18:37:38

I figured a greedy algorithm may commit to a polygon earlier than it should. I didn't think you'd find 8 polygon.

eed3si9n 2009-04-04 18:48:34

You're right... and that's what I'm worried about. In theory, there should be a case where that would happen, I just can't find it.

Mark 2009-04-04 21:10:43

+2 A:

MarkusQ 2009-04-07 00:17:35

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.

Mark 2009-04-07 01:26:22

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.

Mark 2009-04-07 01:27:38

@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?

MarkusQ 2009-04-07 02:32:38

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.

Mark 2009-04-07 02:45:04

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"

Mark 2009-04-07 07:19:17

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

Mark 2009-04-07 07:20:50

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

Mark 2009-04-07 07:36:15

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

MarkusQ 2009-04-07 14:18:25

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

Mark 2009-04-08 00:21:24

wait.... if I've interpreted you correctly, then no you haven't. http://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?

Mark 2009-04-08 00:36:56

http://imageshack.us/ makes it pretty painless to upload

Mark 2009-04-08 00:37:34

this is quite easy to see actually: http://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

Mark 2009-04-08 00:44:46

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

MarkusQ 2009-04-08 16:18:46

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

MarkusQ 2009-04-08 18:59:21

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

Mark 2009-04-08 19:57:40

below it could be removed during the cleanup process!

Mark 2009-04-08 19:58:14

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

MarkusQ 2009-04-08 21:25:23

+2 A:

Phil H 2009-04-07 08:09:17

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

Mark 2009-04-07 18:37:33

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

Mark 2009-04-07 18:39:49

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

Mark 2009-04-07 18:42:24

it somehow seems more random....but maybe I'm just crazy.

Mark 2009-04-07 18:43:16

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

Mark 2009-04-07 18:45:43

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.

Mark 2009-04-07 18:48:19

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

Mark 2009-04-07 18:53:55

@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).

MarkusQ 2009-04-07 19:49:54

Found it :( They're actually quite obvious.

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

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!

Mark 2009-04-09 18:00:03

ansaurus

tags:

views:

answers:

Decomposition to Convex Polygons

related questions