Convex Hull is one of the geometric entities used in GIS, Computer Vision, Artificial Intelligence, CAD and CAM applications.
The convex hull is a polygon with shortest perimeter that encloses a set of points. As a visual analogy, consider a set of points as nails in a board. The convex hull of the points would be like a rubber band stretched around the outermost nails.
A polygon is a flat shape consisting of straight lines that are joined to form a closed chain or circuit. A regular polygon is a polygon that is equiangular (all angles are equal in measure) and equilateral (all sides have the same length). An n-gon is a polygon with n sides.
A polygon can be defined by a set of points or a set of line segments. The order in which the set of points is listed is important. Different orders mean different polygons. The order of the points makes the polygons concave, convex or complex.
A polygon is said to be convex polygon if all the interior angles are less than 180 resulting all the vertices points outwards, away from the center. A 3-gon (triangle) is always a convex polygon. A line drawn through a convex polygon will intersect the polygon exactly twice. All the diagonals of a convex polygon lie entirely inside the polygon. The area of an irregular convex polygon can be found by dividing it into triangles and summing the triangle’s areas. Regular Polygons are always convex by definition.
Concave (Non-convex) polygon
A polygon that has one or more interior angles greater than 180° resulting some vertices point ‘inwards’, towards the center. It looks sort of like a vertex has been ‘pushed in’ towards the inside of the polygon. A triangle (3-gon) can never be concave. A line drawn through a concave polygon can intersect the polygon in more than two places. Some of the diagonals of a concave polygon will lie outside the polygon. Regular Polygons are never concave by definition.
A complex polygon is a polygon which is neither convex nor concave. This includes any polygon which Intersects itself. These include star polygons such as the pentagram and it has a boundary comprising discrete circuits, such as a polygon with a hole in it.
In the last blog (SpaTools: Construct Polylines / Polygons from Points in AutoCAD)
, I shared a tool to create a polygon from a set of points. The resulting polygon may not be convex because it was based on the rule that all the input points are vertices of the resulting polygon. The resulting polygon can be concave or convex depending upon the input set of points but cannot be complex polygon.
The SpaTools is updated with the addition of a command (CVH) to construct a Convex Hull from the set of the points. The following animation illustrates the difference of the output on the same set of input points.
Updated SpaTools DLL file can be downloaded from this link.