• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Decomposing a Rectilinear Polygon

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

10 replies to this topic

### #1DMatovich  Members

Posted 18 August 2007 - 06:48 AM

I'm having difficulty coming up with a simple algorithm for decomposing a rectilinear polygon into a non-overlapping rectangular cover. I stress simple when I say it because I'll be implementing the solution in Second Life which has an extremely limited scripting language. (Although scripts do have access to a pretty decent geometric and math API, memory and storage flexibility is quite limited). Edited in thumbnail. We're getting a few graphics in here Assume that the polygon in Figure 1 is perfectly rectilinear. Figure 2 shows a (fairly ideal) solution to the problem. Figure 3 is incorrect. While the entire polygon is indeed covered, there are overlaps, and this will not be acceptable given the type of geometry I'll be outputting. Figure 4 is also incorrect because the entire polygon isn't covered. I just cannot think of a good solution here, and I've been playing with it for some time. The problem seems pretty simple at first glance, so maybe I'm just missing something. I am not looking to necessarily output the minimal or optimal set of covering rectangles. Although that would be nice, the simplicity of the algorithm is most important. That being said, converting the given polygon into more than, say, 8-10 rectangles would be a blatant misuse of resources. Anybody have any ideas? [help] -Dave [Edited by - DMatovich on August 19, 2007 2:48:12 AM]

### #2kRogue  Members

Posted 18 August 2007 - 07:17 AM

Hi,

This is a relatively simple idea, but the solution will have lots of potentially small rectangles:

for each vertex (a,b) of the polygon, draw the vertical line x=a and the horizontal line y=b. If you do this for all vertices of the rectilinear poly, then you will be left with a bunch of rectangles, now the tricky part is to decide from these grid lines which rectangles are "in" the polygon and which are not.

we now will "paint" the rectangles with integer values:

  S= set of rectangles made by doing the grid system of above.  i=0;  while(S is not empty)  {    pick A in S,      Let T=rectangles adjacent to A that are in S AND the grid line seperating it from A is not from your original polygon. (there will be exactly 4 such rectangles)    while(T is not empty)    {      pick B in T.      remove B from T      remove B from S      mark B with i.    }     ++i  }

after this code is run, each component of the grid system will be marked, most importantly all the blocks within the original polygon will be marked with the same integer, and only those blocks within the polygon will have that value.

so what is left to do is to just pick a rectangle from the grid system that you know is in the polygon. To do that pick a vertex (a,b) and note it must have a vertical and horizontal line segment coming out of it, there are 4 cases, (i.e left and down, right and down, left and up, right and up) from those 4 cases you will know a rectangle which must be in the polygon. and voila you have it done!

though how to code it in a simple script language might be harder, but the algo can be refined.

### #3Naxos  Members

Posted 18 August 2007 - 07:37 AM

Basically what it does is collapse the edges into each other until there aren't any points left:

Here's a picture:
Pic
psuedocode:

function: Decompose
parameters: VertexArray V s.t. the vertices are presented as a line loop defining the rectilinear polygon in CLOCKWISE order

Q Decompose(V):

while V.vcount > 0

index1 = 0
for i = 0 to V.vcount
if V[i].yval > V[index].yval
index = i

index0 = index1+1
if V[index1].yval = V[index1-1].yval
indexT = index1
index1 = index1-1
index0 = indexT

Vector V2, V3
V2 = V[index1-1]
V3 = V[index0+1]

if V[index1-1].yval > V[index0+1].yval
V3.yval = V2.yval
else if V[index1-1].yval < V[index0+1].yval
V2.yval = V3.yval

Q'.point1 = V[index0]
Q'.point2 = V[index1]
Q'.point3 = V2
Q'.point4 = V3

V.removePointFromList(V[index0])
V.removePointFromList(V[index1])
if V2 = V[index1-1]
V.removePointFromList(V2)
if V3 = V[index0-1]
V.removePointFromList(V3)

return Q


Hope that makes sense. Is it useful to you?

[Edited by - Naxos on August 19, 2007 8:37:32 AM]

### #4DMatovich  Members

Posted 18 August 2007 - 08:38 AM

Quote:
 Original post by NaxosHere's an idea I had.Basically what it does is collapse the edges into each other until there aren't any points left:

This is an interesting idea. If you wanted to scrunch it down like that, the blue rectangle would need to be divided (assuming it's collapsing down on each vertical vertex level), but that's still only 7 polygons vs the 5 in the ideal set (I can't think of a better way to divide it than 5.)

I'll have to see if there are any wierd edge cases where this doesn't work as expected. On a plus side, the code would be fairly trivial to implement.

Thanks for the idea!

Anybody have any other interesting solutions?

-Dave

### #5DMatovich  Members

Posted 18 August 2007 - 12:57 PM

Well, I threw together a quick 20 minute C# application to test out various theories, and after running your algo through a pretty convoluted polygon, I get this:

So...Interesting idea, but I think I'm going to have to refine it a bit. Also, I found quite a few cases where it generated quads outside of the polygon (which is obviously a no-no).

I'm going to see if I can take the idea and make it work a bit better.

-Dave

[Edited by - DMatovich on August 19, 2007 2:57:51 AM]

### #6Naxos  Members

Posted 18 August 2007 - 07:09 PM

Yeah I made a quick prototype and discovered that the algorithm doesn't work. Sorry, it's close, but there are a few cases that mess it up. I also discovered that you need to inject a new point after most collapses. I'm not really sure how to fix it though, sorry. Maybe inspiration will hit me ( or you! ) :)

Have you considered kRogues algo?

### #7DMatovich  Members

Posted 18 August 2007 - 08:47 PM

Quote:
 Original post by NaxosYeah I made a quick prototype and discovered that the algorithm doesn't work. Sorry, it's close, but there are a few cases that mess it up. I also discovered that you need to inject a new point after most collapses. I'm not really sure how to fix it though, sorry. Maybe inspiration will hit me ( or you! ) :)Have you considered kRogues algo?

Hehe. I did finally figure out how to make the collapser work on the given problem set. However, after working on it for a few hours, the collapse algorithm has a serious bug (when it tries to collapse an edge and the polygon "branches" at that point). Which I found out by using this test polygon.

I almost got collapse working with this one, but it had too much logic for edge cases, so I've discarded that algorithm (it worked beautifully for a while after quite a bit of tweaking).

So...I've gotten to this point. Given a certain rectilinear polygon, you traverse the outer edge. For every edge that involves a left turn, you project a chord that would continue straight along the original path (stopping at the next polygon boundary).

I've gotten it to work in my rectilinear algo application (even have some nifty debug drawing functionality now), but now I've come up to yet another interesting problem.

Given this:

What's the best way to turn that into rectangles? IE, dicing the polygon up exactly as it's situated there. I can always combine rectangles that share edges at a later optimization step. Maybe I've been thinking in polygons too much today, because I can't think of an efficient way to do it.

Well, at least I have some decent progress. BTW, the original polygon outline is white, with blue dots denoting the actual vertices. Chords are yellow dotted lines. Note that a chord must start from a vertex, but doesn't necessarily have to end on one (but it could).

-Dave

### #8Naxos  Members

Posted 19 August 2007 - 02:31 AM

Hey cool, I was actually thinking of something along those lines last night while I was dozing off. Anyway, I think I've come up with a working method based on what you've just done (Hopefully!)

Okay. So here's the jist:

Traverse along the edge of the shape until a left turn.

We will call the index in the list of the point at this left turn ILP.

Then, project the line as you had done previously.

IF this line intersects the line segment ILP+2 -> ILP+3 (the intersection we will call N):
- Then add a quad to the list with points (ILP, ILP+1, ILP+2, N).
- Remove points ( ILP+1, ILP+2 ) from the point list, and add (N) AFTER ILP.

ELSE:
- Project a line from ILP that would be a 'right turn' from ILP.
- IF this line intersects the line segment ILP-2->ILP-3 at point N:
- - Then add a quad to the list with points (ILP, ILP-1, ILP-2, N).
- - Remove points ( ILP-1, ILP-2 ) from the point list, and add (N) BEFORE ILP.

Repeat this until there are only 4 points left.

A picture to demostrate:

Green indicates a successful intersection test. Red a failed. White is the remove quads, and blue is the remaining line strip.
Clicky(~600kb)

Looks good to me :)

Good luck!

EDIT:
In my description, I didn't list the points of the Quad in any specific order. Just order them as you need so that they will draw properly.

[Edited by - Naxos on August 19, 2007 11:31:49 AM]

### #9DMatovich  Members

Posted 19 August 2007 - 05:03 AM

Hrmm...kinda like ear clipping (but for rectangles). Interesting idea. I'll give it a look-see in a bit.

Thanks for all your help, BTW!

-Dave

Edit: Didn't your mother ever teach you not to upload 1/2MB uncompressed BMP files? I hope you didn't do that in paint.exe! ;-)

### #10Naxos  Members

Posted 19 August 2007 - 05:17 AM

Quote:
 Original post by DMatovichHrmm...kinda like ear clipping (but for rectangles). Interesting idea. I'll give it a look-see in a bit.Thanks for all your help, BTW!-DaveEdit: Didn't your mother ever teach you not to upload 1/2MB uncompressed BMP files? I hope you didn't do that in paint.exe! ;-)

Well I was going to upload a JPEG, but it was too lossy on parts of it, making it hard to see what was happening.

So... I guess I could edit it and turn it into a link...

Anywho, thanks for posting the problem, trying to solve it was fun :) Let me know how it goes.

Haven't heard of this ear clipping... *wanders off to google*

[Edited by - Naxos on August 19, 2007 11:17:15 AM]

### #11DMatovich  Members

Posted 17 September 2007 - 05:17 AM

BTW, if anyone is still following this ;-).

Naxos's last proposed algorithm (which I affectionately named Naxos2) works just fine with two simple additions:

1) If the intersection hits an existing vertex, do not add a new point.

2) The polygon must remain rectilinear at all times. The important part of that definition here is that "useless" vertices, ones that lie in between two other vertices, must be removed.

   (1)------(2)-------(3)    |                  |    |                  |    |                  |   (5)----------------(4)

I.E., vertex 2 needs to be removed in this example because it lies on the line segment between vert 1 and vert 3.

You could probably create some logic to detect and remove these useless verts when they are created, but I simply scan the entire polygon every time a rectangle is "clipped" from it.

Much thanks to Naxos!

-Dave

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.