# Subdividing an irregular area into rectangles

This topic is 4260 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
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 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 on other sites
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').

1. 1
2. 2
3. 3
Rutin
19
4. 4
5. 5

• 10
• 14
• 30
• 13
• 11
• ### Forum Statistics

• Total Topics
631785
• Total Posts
3002346
×