Sign in to follow this  
Sock of Eternity

Subdividing an irregular area into rectangles

Recommended Posts

I'm attempting to find a way to automatically subdivide any given area into rectangular sections, but my maths isn't quite up to task. Is there a reasonably efficient way to do this? In the editor for the game I'm working on, the user can set up rectangular areas by clicking and dragging, like you would if selecting multiple files in windows. These areas can then be linked to effects so that they trigger various things in-game if clicked on (I store the areas as top,left and bottom,right co-ordinates which are simple to check against). Unfortunately defining areas that aren't perfectly rectangular manually, by using multiple smaller rectangles, is apparantly too much effort for some people. ;) Can anyone help by providing a method for this automatic subdivision, or, alternatively, simple ways of checking if a point is inside a given irregular area that aren't too calculation heavy? Areas can overlap without any problems, currently, and imposing restrictions so that a method will work won't be a problem - I've already a pretty heavy restriction in place by only allowing rectangles.

Share this post


Link to post
Share on other sites
jyk    2094
Checking to see if a point lies within an arbitrary convex polygon is quite straightforward, and checking against a non-convex polygon is only slightly less so. So I would think removing the 'rectangular' restriction might be an option.

Otherwise, what are the characteristics of the areas you wish to subdivide? Are all the edges axis-aligned, or do they have arbitrary alignments? (From the context, I'm guessing the former.)

Share this post


Link to post
Share on other sites
I looked up the methods you mentioned, and they're a lot more straightforward than I thought they'd be. (:

It should be possible to use those, and likely will be a lot faster, and take less storage, than checking the dozens of tiny rectangles that'd result from the kind of subdividing I was originally after. Thanks for the terms, or I'd never have found them.

As for your other (probably redundant now) question, I think the answer is yes... axis-aligned.

Again, thanks very much!

Share this post


Link to post
Share on other sites
Bob Janova    769
Yeah, I second being allowed to use any simple (i.e. no holes, no crossovers) polygonal shape. For convex polygons it's pretty easy to find out if you're inside it. For concave ones, it's relatively easy to split it into convex ones (I think this is called 'tesselation' or 'polygon splitting').

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