SpaTools: Construct Convex Hull in AutoCAD











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.

Convex polygon


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.

Complex polygon

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 Cadomation.

Comments

Post a Comment

Popular posts from this blog

SpaTools: Import Lidar Point Cloud (LAS/LAZ) files into AutoCAD

Image
Point clouds are large data sets composed of 3D point data. These geographic point data is collected mostly by Laser scanners and drones equipped with LIDAR (Light Detection And Ranging) sensors. In addition to these directly collected LIDAR point cloud data, the aerial RGB images collected by drones are processed using Image Processing & Computer Vision Algorithm based software such as Pix4D, Agisoft Photoscan or DroneDeploy to produce RGB Point Clouds in LAS file format. Besides that, the well known image processing software such as ERDAS Imagine Leica Photogrammetry Suite (LPS), ENVI and PCI Geomatica produce output in LAS file format when stereo/tri-stereo satellite images (WorldView-2, WorldView-3, SOPT 5/6/7 & Pleiades) are processed.     LAS is an industry standard file format defined by the American Society of Photogrammetry and Remote Sensing (ASPRS) that includes a system of point classification. A processed LAS file may have points classified as bare earth,
Read more

How to Clip objects in AutoCAD

Image
There is a tool named as CLIP in ArcGIS which cut out a piece of one feature class using one or more of the features in another feature class as a cookie cutter. This is particularly useful for creating a new feature class as study area or area of interest (AOI) that contains a geographic subset of the features in another, larger feature class. It is often needed to CLIP all the objects contained completely inside a polygon to a new drawing. The type of the objects may vary from simple objects like polylines, lines, circles, text to complex objects like splines, arcs, hatches, blocks etc. Since the release of AutoCAD 2008, a new command EXPORTLAYOUT was introduced to export all the objects in all the viewports of the layout to a separate drawing. I am writing this article because most of the CAD users are not aware about the power of this magical command of Autocad and use TRIM command to trim all the objects one by one which are outside of the desired polygon. It is h
Read more

SpaTools: Extract Topographic Profile From Contours In AutoCAD

Image
A topographic map is simply the two dimensional representation of a portion of three dimensional surface of earth. Topographic maps provide the detailed information about the natural and man-made aspects of the terrain, but are best known for their series of contour lines that show elevation changes, and colors signifying varying land types and bodies of water. Contour lines are used to determine elevations and are lines on a map that are produced from connecting points of equal elevation (elevation refers to height in feet, or meters, above sea level). By reading contour lines, one can measure the steepness of a hill, the height of a mountain, and even the depth of a lake or Ocean . The contours can be generated by a DEM (Digital Elevation Model), TIN (Triangular Irregular Network) or a surface using different software such as ArcGIS.  Read the blog about How to generate contours from DEM and create a topographic map in Autocad. Most of the topographic maps used for plann
Read more

Creating Contour Maps in ArcGIS and Conversion to AutoCAD drawing

Image
A topographic map is simply the two dimensional representation of a portion of three dimensional surface of earth. Topographic maps provide the detailed information about the natural and man-made aspects of the terrain, but are best known for their series of contour lines that show elevation changes, and colors signifying varying land types and bodies of water. Contour lines are used to determine elevations and are lines on a map that are produced from connecting points of equal elevation (elevation refers to height in feet, or meters, above sea level). By reading contour lines, one can measure the steepness of a hill, the height of a mountain, and even the depth of a lake or ocean . These lines are evenly spaced apart. This spacing is called the contour interval. For example, if your map uses a 10-foot contour interval, you will see contour lines for every 10 feet (3 meters) of elevation -- lines at 0, 10, 20, 30, 40, and so on. Different maps use different intervals, dependin
Read more

SpaTools: Toolbar with all tools

Image
Since January 2020, I started writing blogs about the custom tools developed for AutoCAD. All those blogs are entitled with the prefix of “SpaTools” . Currently, ten (10) different tools have been added to SpaTools.DLL . For each tool, I have published a blog with the explanation of its usability and some basic information. The readers not only appreciated it but also suggested to improve and extend it further by adding more tools such as Export CSV, KML, LAS, GPX, SHP etc and other cartographic tools. Besides that, it was suggested by some users to develop it as a Toolbar . In the response of that suggestion, I have developed it as a toolbar. The DLL file can be downloaded from the link  at the bottom of this page. Prior to loading in AutoCAD, unblock it. Right Click on the DLL file and check the unblock checkbox and apply. Load the DLL into AutoCAD using NETLOAD command.    The commands are categorized into three panels:  Import , Create Features and Cartography &
Read more

Gunter Chain / Surveyor's Chain

Image
“ What is the length of cricket pitch?”  “It is equal to 22 yards”. Cricket  is a bat-and-ball game played between two teams of eleven players on a field at the center of which is a 22 yard pitch with a wicket at each end, each comprising two bails balanced on three stumps.  Recalling the memories of childhood, we use to place the wickets by pacing out a distance of 22 paces by walking. At that time, we were not aware neither interested to know the exact length of cricket pitch. But this time, the question raised in my mind that why it is 22 yards!! ?? Why it is not like 22 meters or 25 yards or 20 yards? Cricket Pitch The standard length of cricket pitch is simply one Gunter chain (Surveyor’s chain) since the first known code of Laws in 1744 and it is believed this length had been in use since the introduction of Gunter's chain  in 1620 . Throughout recorded history surveyors have used many devices for measuring distances such as rope, poles, grape vines, paci
Read more