• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
DMatovich

Decomposing a Rectilinear Polygon

10 posts in this topic

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). Example 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]
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
Here's an idea I had.
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
returns: QuadArray Q s.t. each quad is specified COUNTER CLOCK WISE

Q Decompose(V):
quads = 0
Quad Q'

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)

Q[quads] = Q'
quads = quads + 1

return Q


Hope that makes sense. Is it useful to you?

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

Share this post


Link to post
Share on other sites
Quote:
Original post by Naxos
Here'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
0

Share this post


Link to post
Share on other sites
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:


New Test


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]
0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
Quote:
Original post by Naxos
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?


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
0

Share this post


Link to post
Share on other sites
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]
0

Share this post


Link to post
Share on other sites
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! ;-)
0

Share this post


Link to post
Share on other sites
Quote:
Original post by DMatovich
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! ;-)


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]
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0