54
Using QHULL routine in IDL to build the largest convex polygon around a set of random points
QHULL is an IDL routine to apply Quick Hull algorithm for various applications.
Bibliography: “The Quickhull Algorithm for Convex Hulls,” ACM Transactions on Mathematical Software, Vol. 22, No 4, December 1996, Pages 469-483, Barber, Dobkin and Huhdanpaa
Documentation: https://www.nv5geospatialsoftware.com/docs/QHULL.html
One application consists in building the largest convex polygon around a set of random points. The IDL code example below is showing how to use QHULL in such context, and how to locate the centroid of the output polygon afterwards.
The QHULL routine will output the list of vertices to build the largest convex polygon around the set of input points. However those vertices are not necessarily in the right order
IDL> PRINT,t
2 7
5 0
7 5
0 3
3 2
The above output should be interpreted as follows:
Line 1: a line should be set between point 2 and point 7 of the input dataset
Line 2: a line should be set between point 5 and point 0 of the input dataset
Line 3: a line should be set between point 7 and point 5 of the input dataset
Line 4: a line should be set between point 0 and point 3 of the input dataset
Line 5: a line should be set between point 3 and point 2 of the input dataset
In order to plot this polygon, the vertices must be ordered in a way that creates a continuous line i.e.
2 >> 7 >> 5 >> 0 >> 3 >> 2
The reordering of the vertices is done by a FOR loop going through each individual points of the second column of the t variable, and sorting them in the appropriate way to create the continuous line. Output verts variable includes the order of vertices :
IDL > PRINT," Polygon vertices order: ", verts
Polygon vertices order: 2 7 5 0 3 2



Code example:
PRO test_qhull
; input the x and y coordinates of the point cloud
x1=double([6.712645 , 6.712720 , 6.712706 , 6.712648, 6.712660 , 6.712706 , 6.71270, 6.7127685])
y1=double([49.406416, 49.406440, 49.406377 , 49.406376, 49.406420, 49.406456 , 49.406390, 49.406416])
; display the input points
p=PLOT(x1, y1,LINESTYLE=6,SYM_SIZE=0.5,SYMBOL='o',SYM_FILLED=0,title='QHULL Test', COLOR='red',DIMENSIONS=[1000,400 ])
; run QHULL routine and display the output t variable including the vertices of the largest convex POLYGON of this point cloud
QHULL,x1, y1, t
PRINT," Output list of vertices (t variable) from QHULL: "
PRINT, t
; determine the vertices order from the t output variable from QHULL, and print the vertices order
verts=INTARR(N_ELEMENTS(t[0,*])+1)
verts[0]=t[0,0]
verts[1]=t[1,0]
FOR i=1,N_ELEMENTS(t[0,*])-1 DO BEGIN
id=WHERE(t[0,*] EQ verts[i])
verts[i+1]=t[1,id]
ENDFOR
PRINT," Polygon vertices order: ", verts
; order the points in x1 and y1 vectors based on vertices order
x2=x1[verts]
y2=y1[verts]
; determine the centroid of the polygon using the IDLanROI object
roi=IDLanROI()
roi.SetProperty,Data=TRANSPOSE([[x2],[y2]])
a=roi.ComputeGeometry(CENTROID=center1)
; display the POLYGON and its centroid on the original graphic
p=PLOT(x2, y2,LINESTYLE=0, COLOR='blue',/OVERPLOT)
p=PLOT([center1[0],center1[0]], [center1[1],center1[1]],LINESTYLE=6,SYM_SIZE=2,SYMBOL='s',COLOR='green',/OVERPLOT)
END
A graphic similar to the following will be generated:

---------------------------
created by BC on 2/19/2025
reviewed by BC (US) on 2/27/2025