| 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 | Defines a box which can check for intersections with other boxes, |
|---|
| 16 | or if a point lies within it. |
|---|
| 17 | """ |
|---|
| 18 | |
|---|
| 19 | def __init__(self, xmin, xmax=None, ymin=None, ymax=None): |
|---|
| 20 | """ Define axially-algned bounding box. |
|---|
| 21 | xmin is minimum x |
|---|
| 22 | xmax is maximum x (absolute coord, ie, not size) |
|---|
| 23 | ymin is minimum y |
|---|
| 24 | ymax is maximum y (absolute coord, ie, not size) |
|---|
| 25 | """ |
|---|
| 26 | if not xmax: |
|---|
| 27 | # try treating first arg as a list of points |
|---|
| 28 | try: |
|---|
| 29 | xmin[0][0] |
|---|
| 30 | except: |
|---|
| 31 | raise Exception('Single parameter to AABB must be point list.') |
|---|
| 32 | |
|---|
| 33 | self.xmin, self.ymin = self.xmax, self.ymax = xmin[0] |
|---|
| 34 | self.include(xmin[1:]) |
|---|
| 35 | else: |
|---|
| 36 | self.xmin = xmin |
|---|
| 37 | self.xmax = xmax |
|---|
| 38 | self.ymin = ymin |
|---|
| 39 | self.ymax = ymax |
|---|
| 40 | |
|---|
| 41 | |
|---|
| 42 | def __repr__(self): |
|---|
| 43 | return 'AABB(xmin:%f, xmax:%f, ymin:%f, ymax:%f)' \ |
|---|
| 44 | % (round(self.xmin,1), round(self.xmax,1), \ |
|---|
| 45 | round(self.ymin,1), round(self.ymax, 1)) |
|---|
| 46 | |
|---|
| 47 | |
|---|
| 48 | def grow(self, amount): |
|---|
| 49 | """ Expand region by given amount. |
|---|
| 50 | amount is a multiplier, ie 1.1 will expand border by 10%. |
|---|
| 51 | """ |
|---|
| 52 | self.ymax += (self.ymax-self.ymin)*amount |
|---|
| 53 | self.xmax += (self.xmax-self.xmin)*amount |
|---|
| 54 | self.ymin -= (self.ymax-self.ymin)*amount |
|---|
| 55 | self.xmin -= (self.xmax-self.xmin)*amount |
|---|
| 56 | |
|---|
| 57 | |
|---|
| 58 | def size(self): |
|---|
| 59 | """return size as (w,h)""" |
|---|
| 60 | return self.xmax - self.xmin, self.ymax - self.ymin |
|---|
| 61 | |
|---|
| 62 | |
|---|
| 63 | def split(self, border=SPLIT_BORDER_RATIO): |
|---|
| 64 | """Split box along shorter axis. |
|---|
| 65 | return 2 subdivided AABBs. This is useful for recursive |
|---|
| 66 | algorithms. |
|---|
| 67 | |
|---|
| 68 | border is the overlap between the 2 regions - if set to 0.5 |
|---|
| 69 | it will subdivide them exactly, > 0.5 will create a |
|---|
| 70 | shared overlapping area. |
|---|
| 71 | """ |
|---|
| 72 | |
|---|
| 73 | width, height = self.size() |
|---|
| 74 | assert width >= 0 and height >= 0 |
|---|
| 75 | |
|---|
| 76 | if (width > height): |
|---|
| 77 | # split vertically |
|---|
| 78 | split1 = self.xmin+width*border |
|---|
| 79 | split2 = self.xmax-width*border |
|---|
| 80 | return AABB(self.xmin, split1, self.ymin, self.ymax), \ |
|---|
| 81 | AABB(split2, self.xmax, self.ymin, self.ymax) |
|---|
| 82 | else: |
|---|
| 83 | # split horizontally |
|---|
| 84 | split1 = self.ymin+height*border |
|---|
| 85 | split2 = self.ymax-height*border |
|---|
| 86 | return AABB(self.xmin, self.xmax, self.ymin, split1), \ |
|---|
| 87 | AABB(self.xmin, self.xmax, split2, self.ymax) |
|---|
| 88 | |
|---|
| 89 | |
|---|
| 90 | def is_trivial_in(self, test): |
|---|
| 91 | """ Is trivial in. |
|---|
| 92 | test a box to test against the bounding box |
|---|
| 93 | return True if the test box falls fully within the |
|---|
| 94 | bounding box without intersecting it. |
|---|
| 95 | """ |
|---|
| 96 | if (test.xmin < self.xmin) or (test.xmax > self.xmax): |
|---|
| 97 | return False |
|---|
| 98 | if (test.ymin < self.ymin) or (test.ymax > self.ymax): |
|---|
| 99 | return False |
|---|
| 100 | return True |
|---|
| 101 | |
|---|
| 102 | def contains(self, point): |
|---|
| 103 | """ is point within box |
|---|
| 104 | point is a test point |
|---|
| 105 | return True if the point is contained within the box. |
|---|
| 106 | """ |
|---|
| 107 | return (self.xmin <= point[0] <= self.xmax) \ |
|---|
| 108 | and (self.ymin <= point[1] <= self.ymax) |
|---|
| 109 | |
|---|
| 110 | def include(self, point_list): |
|---|
| 111 | """ Include points in AABB. |
|---|
| 112 | Bounding box will be expanded to include passed points |
|---|
| 113 | |
|---|
| 114 | point_list is a list of points. |
|---|
| 115 | """ |
|---|
| 116 | for point in point_list: |
|---|
| 117 | pt_x, pt_y = point |
|---|
| 118 | if pt_x < self.xmin: |
|---|
| 119 | self.xmin = pt_x |
|---|
| 120 | if pt_x > self.xmax: |
|---|
| 121 | self.xmax = pt_x |
|---|
| 122 | if pt_y < self.ymin: |
|---|
| 123 | self.ymin = pt_y |
|---|
| 124 | if pt_y > self.ymax: |
|---|
| 125 | self.ymax = pt_y |
|---|
