CODEWITHSUNDEEP
algorithmdata-structurespython-3.xpython
Eric
Eric

Reputation: 636

how to efficiently store occupied/unoccupied 2D space (with insertion)

I have an X by Y space, where X and Y are determined by the sizes of the rectangles given to me. I'm inserting oriented rectangles of a certain size into the space, one at a time. Each insertion is as far left as possible, and then as far up as possible (so as close to (0,0) as I can). What's the best way to represent this? I'm implementing this in Python. The top answer to this question is helpful, but I was hoping for some Python-specific advice, as I'm pretty new to the language itself as well.

Thanks!

Upvotes: 1

Views: 253

Answers (3)

Marcelo Cantos
Marcelo Cantos

Reputation: 185862

If you are trying to efficiently pack rectangles, there are some established algorithms. Here's a Python implementation of one particular algorithm. There's also an article on packing lightmaps here for which I have a Python version (I honestly don't remember whether I ported it myself, or got it from somewhere else).

Upvotes: 4

Matt Cooper
Matt Cooper

Reputation: 937

Quadtrees are often used for this sort of thing. It sounds like you want a region quad tree.

Upvotes: 0

S.Lott
S.Lott

Reputation: 391852

You have two choices for working in two-dimensional space like this.

  1. A list of lists. [ [0, 0, ..., 0], [0, 0, ..., 0], ... [0, 0, ..., 0] ] The outer list is the 'X' access, the inner list is the 'Y' access. Each point is space[x][y]. You build it with space = list( list( EMPTY for j in range(Y_size) ) for i in range(X_size) ) or something similar.

    You mask off rectangles with some filler algorithm that sets values into a rectangular patch of space. 

    for x in range( low, high ):
    for y in range ( low, high ):
        space[x][y]= FILLED # or whatever object you're putting there.

  2. A mapping. { (0,0): 0, (0,1): 0, ... (X,Y): 0 }. Each point is space[x,y]. You build it with space = dict( ( (x,y), EMPTY ) for x in range(X_size) for y in range(Y_size) ).

    You mask off rectangles with almost the same filler algorithm. Just change the syntax slightly.

Upvotes: 0

Related Questions