Rotating caliper algorithm is used to find a rectangle that fits a convex hull. Below is a python implementation that finds all rotated rectangles for a given convex hull points. It is up to the user to select which rectangle to use since it returns all possible rotating caliper rectangles.

import numpy as np

def get_rotating_caliper_bbox_list(hull_points_2d):
"""

hull_points_2d: array of hull points. each element should have [x,y] format
"""

# Compute edges (x2-x1,y2-y1)
edges = np.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]

# Calculate edge angles   atan2(y/x)
edge_angles = np.zeros( (len(edges)) ) # empty 1 column array
for i in range( len(edge_angles) ):
edge_angles[i] = np.arctan2( edges[i,1], edges[i,0] )

# Check for angles in 1st quadrant
for i in range( len(edge_angles) ):
edge_angles[i] = np.abs( edge_angles[i] % (np.pi/2) ) # want strictly positive answers
#print "Edge angles in 1st Quadrant: \n", edge_angles

# Remove duplicate angles
edge_angles = np.unique(edge_angles)
#print "Unique edge angles: \n", edge_angles

bbox_list=[]
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 = np.array([ [ np.cos(edge_angles[i]), np.cos(edge_angles[i]-(np.pi/2)) ], [ np.cos(edge_angles[i]+(np.pi/2)), np.cos(edge_angles[i]) ] ])

# Apply this rotation to convex hull points
rot_points = np.dot(R, np.transpose(hull_points_2d) ) # 2x2 * 2xn

# Find min/max x,y points
min_x = np.nanmin(rot_points, axis=0)
max_x = np.nanmax(rot_points, axis=0)
min_y = np.nanmin(rot_points, axis=0)
max_y = np.nanmax(rot_points, axis=0)

# Calculate height/width/area of this bounding rectangle
width = max_x - min_x
height = max_y - min_y
area = width*height

# Calculate center point and restore to original coordinate system
center_x = (min_x + max_x)/2
center_y = (min_y + max_y)/2
center_point = np.dot( [ center_x, center_y ], R )

# Calculate corner points and restore to original coordinate system
corner_points = np.zeros( (4,2) ) # empty 2 column array
corner_points = np.dot( [ max_x, min_y ], R )
corner_points = np.dot( [ min_x, min_y ], R )
corner_points = np.dot( [ min_x, max_y ], R )
corner_points = np.dot( [ max_x, max_y ], R )

bbox_info = [edge_angles[i], area, width, height, min_x, max_x, min_y, max_y, corner_points, center_point]
bbox_list.append(bbox_info)

return bbox_list

this code was based on code from here. I only updated the code to return all possible rectangles instead of the one with minimum area since the user may be interested in other rectangles depending on their needs. Also I’ve updated it to use explicit functions from numpy.

Categories: algorithmpython