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