Machine vision methods and articles of manufacture for determination of convex hull and convex hull angle

摘要

A machine vision method for identifying a convex hull (i.e., a perimeter) around a set of points (e.g., such as may be found in an image of a ball grid array, or BGA, device) involves finding several "extreme" points on the convex hull. Points in the set that are outside a closed polygon defined by those extreme points are ordered to form a hull by, sorting them, identifying a line defined certain minimum and maximum coordinate values, and re-ordering the sorted points according to their position with respect to that line. The method further calls for testing successive points on the hull and removing those that do not define a convex hull using aspects of a Graham scan technique. The invention also provides a method for finding the angular orientation of a convex hull. The methods of the invention can be beneficially applied to the inspection of images of ball grid array devices, as well as other machine vision applications.