-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmin_bounding_box.py
98 lines (78 loc) · 4.16 KB
/
min_bounding_box.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
from numpy import *
import sys # maxint
def minBoundingRect(hull_points_2d):
#print "Input convex hull points: "
#print hull_points_2d
# Compute edges (x2-x1,y2-y1)
edges = zeros( (len(hull_points_2d)-1,2) ) # empty 2 column array
for i in range( len(edges) ):
edge_x = hull_points_2d[i+1][0] - hull_points_2d[i][0]
edge_y = hull_points_2d[i+1][1] - hull_points_2d[i][1]
edges[i] = [edge_x,edge_y]
#print "Edges: \n", edges
# Calculate edge angles atan2(y/x)
edge_angles = zeros( (len(edges)) ) # empty 1 column array
for i in range( len(edge_angles) ):
edge_angles[i] = math.atan2( edges[i,1], edges[i,0] )
#print "Edge angles: \n", edge_angles
# Check for angles in 1st quadrant
for i in range( len(edge_angles) ):
edge_angles[i] = abs( edge_angles[i] % (math.pi/2) ) # want strictly positive answers
#print "Edge angles in 1st Quadrant: \n", edge_angles
# Remove duplicate angles
edge_angles = unique(edge_angles)
#print "Unique edge angles: \n", edge_angles
# Test each angle to find bounding box with smallest area
min_bbox = (0, sys.maxint, 0, 0, 0, 0, 0, 0) # rot_angle, area, width, height, min_x, max_x, min_y, max_y
for i in range( len(edge_angles) ):
# Create rotation matrix to shift points to baseline
# R = [ cos(theta) , cos(theta-PI/2)
# cos(theta+PI/2) , cos(theta) ]
R = array([ [ math.cos(edge_angles[i]), math.cos(edge_angles[i]-(math.pi/2)) ], [ math.cos(edge_angles[i]+(math.pi/2)), math.cos(edge_angles[i]) ] ])
#print "Rotation matrix for ", edge_angles[i], " is \n", R
# Apply this rotation to convex hull points
rot_points = dot(R, transpose(hull_points_2d) ) # 2x2 * 2xn
#print "Rotated hull points are \n", rot_points
# Find min/max x,y points
min_x = nanmin(rot_points[0], axis=0)
max_x = nanmax(rot_points[0], axis=0)
min_y = nanmin(rot_points[1], axis=0)
max_y = nanmax(rot_points[1], axis=0)
#print "Min x:", min_x, " Max x: ", max_x, " Min y:", min_y, " Max y: ", max_y
# Calculate height/width/area of this bounding rectangle
width = max_x - min_x
height = max_y - min_y
area = width*height
#print "Potential bounding box ", i, ": width: ", width, " height: ", height, " area: ", area
# Store the smallest rect found first (a simple convex hull might have 2 answers with same area)
if (area < min_bbox[1]):
min_bbox = ( edge_angles[i], area, width, height, min_x, max_x, min_y, max_y )
# Bypass, return the last found rect
#min_bbox = ( edge_angles[i], area, width, height, min_x, max_x, min_y, max_y )
# Re-create rotation matrix for smallest rect
angle = min_bbox[0]
R = array([ [ math.cos(angle), math.cos(angle-(math.pi/2)) ], [ math.cos(angle+(math.pi/2)), math.cos(angle) ] ])
#print "Projection matrix: \n", R
# Project convex hull points onto rotated frame
proj_points = dot(R, transpose(hull_points_2d) ) # 2x2 * 2xn
#print "Project hull points are \n", proj_points
# min/max x,y points are against baseline
min_x = min_bbox[4]
max_x = min_bbox[5]
min_y = min_bbox[6]
max_y = min_bbox[7]
#print "Min x:", min_x, " Max x: ", max_x, " Min y:", min_y, " Max y: ", max_y
# Calculate center point and project onto rotated frame
center_x = (min_x + max_x)/2
center_y = (min_y + max_y)/2
center_point = dot( [ center_x, center_y ], R )
#print "Bounding box center point: \n", center_point
# Calculate corner points and project onto rotated frame
corner_points = zeros( (4,2) ) # empty 2 column array
corner_points[0] = dot( [ max_x, min_y ], R )
corner_points[1] = dot( [ min_x, min_y ], R )
corner_points[2] = dot( [ min_x, max_y ], R )
corner_points[3] = dot( [ max_x, max_y ], R )
#print "Bounding box corner points: \n", corner_points
#print "Angle of rotation: ", angle, "rad ", angle * (180/math.pi), "deg"
return (angle, min_bbox[1], min_bbox[2], min_bbox[3], center_point, corner_points) # rot_angle, area, width, height, center_point, corner_points