The rectangles module

Manages lists of rectangular objects and quickly finds them.

class Rectangles(objects=None)[source]

Bases: object

Manages a list of rectangular objects and quickly finds objects at some point, in some rectangle or intersecting some rectangle.

The implementation uses four lists of the objects sorted on either coordinate, so retrieval is fast.

Bulk adding is done in the constructor or via the bulk_add() method (which clears the indexes, that are recreated on first search). Single objects can be added and deleted, keeping the indexes, but that’s slower.

You should inherit from this class and implement the method get_coords(obj) to get the rectangle of the object (x, y, x2, y2). These are requested only once. x should be < x2 and y should be < y2.

get_coords(obj)[source]

You should implement this method.

The result should be a four-tuple with the coordinates of the rectangle the object represents (x, y, x2, y2). These are requested only once. x should be < x2 and y should be < y2.

add(obj)[source]

Adds an object to our list. Keeps the index intact.

bulk_add(objects)[source]

Adds many new items to the index using the function given in the constructor.

After this, the index is cleared and recreated on the first search operation.

remove(obj)[source]

Removes an object from our list. Keeps the index intact.

clear()[source]

Empties the list of items.

at(x, y)[source]

Returns a set() of objects that are touched by the given point.

inside(left, top, right, bottom)[source]

Returns a set() of objects that are fully in the given rectangle.

intersecting(left, top, right, bottom)[source]

Returns a set() of objects intersecting the given rectangle.

width(obj)[source]

Return the width of the specified object.

This can be used for sorting a set returned by at(), inside() or intersecting(). For example:

for r in sorted(rects.at(10, 20), key=rects.width):
    # ...
height(obj)[source]

Return the height of the specified object. See also width().

closest(obj, side)[source]

Returns the object closest to the given one, going to the given side.

nearest(x, y)[source]

Return the object with the shortest distance to the point x, y.

The point (x, y) is outside the object. Use at() to get objects that touch the point (x, y). If there are no objects, None is returned.