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 |
---|
11 | SPLIT_BORDER_RATIO = 0.55 |
---|
12 | |
---|
13 | class 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 |
---|