# source:trunk/anuga_core/source/anuga/geometry/aabb.py@7872

Last change on this file since 7872 was 7872, checked in by hudson, 13 years ago

Fixed a few unit test errors.

File size: 4.8 KB
Line
1"""
2    Axially aligned bounding box.
3    Contains a class describing a bounding box. It contains methods
4    to split itself and return child boxes.
5
6    As of June 2010 this module has a pylint quality rating of 10/10.
7"""
8
9# Allow children to be slightly bigger than their parents to prevent
10# straddling of a boundary
11SPLIT_BORDER_RATIO    = 0.55
12
13class AABB:
14    """ Axially-aligned bounding box class.
15        An axially aligned bounding box (or AABB) defines a box-shaped region
16        of the plane which contains any other arbitrary geometry.
17        It is useful because intersections can be tested against it very
18        rapidly. Once all misses are trivially rejected, a more expensive
19        collision detection can be done against the remaining geometry.
20
21        This class defines a box which can check for intersections with other
22        boxes, or points. It can also subdivide itself, returning
23        smaller AABBs. This can be used as the basis of a recursive tree
24        structure for optimising geometry searches.
25    """
26
27    def __init__(self, xmin, xmax=None, ymin=None, ymax=None):
28        """ Define axially-algned bounding box.
29            xmin is minimum x
30            xmax is maximum x (absolute coord, ie, not size)
31            ymin is minimum y
32            ymax is maximum y (absolute coord, ie, not size)
33        """
34        if xmax is None:
35            # try treating first arg as a list of points
36            try:
37                xmin[0][0]
38            except:
39                raise Exception('Single parameter to AABB must be point list.')
40
41            self.xmin, self.ymin = self.xmax, self.ymax = xmin[0]
42            self.include(xmin[1:])
43        else:
44            self.xmin = xmin
45            self.xmax = xmax
46            self.ymin = ymin
47            self.ymax = ymax
48
49
50    def __repr__(self):
51        return 'AABB(xmin:%f, xmax:%f, ymin:%f, ymax:%f)' \
52               % (round(self.xmin,1), round(self.xmax,1), \
53                  round(self.ymin,1), round(self.ymax, 1))
54
55
56    def grow(self, amount):
57        """ Expand region by given amount.
58            amount is a multiplier, ie 1.1 will expand border by 10%.
59        """
60        self.ymax += (self.ymax-self.ymin)*amount
61        self.xmax += (self.xmax-self.xmin)*amount
62        self.ymin -= (self.ymax-self.ymin)*amount
63        self.xmin -= (self.xmax-self.xmin)*amount
64
65
66    def size(self):
67        """return size as (w,h)"""
68        return self.xmax - self.xmin, self.ymax - self.ymin
69
70
71    def split(self, border=SPLIT_BORDER_RATIO):
72        """Split box along shorter axis.
73           return 2 subdivided AABBs. This is useful for recursive
74           algorithms.
75
76           border is the overlap between the 2 regions - if set to 0.5
77                  it will subdivide them exactly, > 0.5 will create a
78                  shared overlapping area.
79        """
80
81        width, height = self.size()
82        assert width >= 0 and height >= 0
83
84        if (width > height):
85            # split vertically
86            split1 = self.xmin+width*border
87            split2 = self.xmax-width*border
88            return AABB(self.xmin, split1, self.ymin, self.ymax), \
89                   AABB(split2, self.xmax, self.ymin, self.ymax)
90        else:
91            # split horizontally
92            split1 = self.ymin+height*border
93            split2 = self.ymax-height*border
94            return AABB(self.xmin, self.xmax, self.ymin, split1), \
95                   AABB(self.xmin, self.xmax, split2, self.ymax)
96
97
98    def is_trivial_in(self, test):
99        """ Is trivial in.
100            test a box to test against the bounding box
101            return True if the test box falls fully within the
102                   bounding box without intersecting it.
103        """
104        if (test.xmin < self.xmin) or (test.xmax > self.xmax):
105            return False
106        if (test.ymin < self.ymin) or (test.ymax > self.ymax):
107            return False
108        return True
109
110    def contains(self, point):
111        """ is point within box
112            point is a test point
113            return True if the point is contained within the box.
114        """
115        return (self.xmin <= point[0] <= self.xmax) \
116                and (self.ymin <= point[1] <= self.ymax)
117
118    def include(self, point_list):
119        """ Include points in AABB.
120            Bounding box will be expanded to include passed points
121
122            point_list is a list of points.
123        """
124        for point in point_list:
125            pt_x, pt_y = point
126            if pt_x < self.xmin:
127                self.xmin = pt_x
128            if pt_x > self.xmax:
129                self.xmax = pt_x
130            if pt_y < self.ymin:
131                self.ymin = pt_y
132            if pt_y > self.ymax:
133                self.ymax = pt_y
Note: See TracBrowser for help on using the repository browser.