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

Last change on this file since 7872 was 7872, checked in by hudson, 14 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.