12963 Rate this article:
No rating

An efficient implementation of 2-D classification to a convex hull reference


A supervised classification technique consists of having a set of known reference samples defining a class, and comparing another set of unknown samples to the reference samples to determine which are similar enough to belong to the known class. One possible approach is to test the unknown samples for containment in the convex hull of the reference samples, and samples that are contained in the convex hull are said to belong to the class. This approach can be used in a sample space of any number of dimensions. Here is an example implementation for a 2-D sampling space.

; An efficient algorithm for finding2-D points within

; the convex hull of a set ofreference points.

; This approach can be used forclassifying new point samples

; against a set of knownrepresentative reference points.

; The code is optimized to run fastin the case where nPts

; gets very large (provided that thePLOT calls are removed

; first).

pro PointOverlap

 compile_opt idl2,logical_predicate

 ;reference points

 nRef = 300

 xRef = randomn(seed, nRef) * 20 + 40

 yRef = randomn(seed, nRef) * 55 + 25


 p = list()

 p->Add, plot(xRef, yRef, 'r+')


 ;points to be tested

 nPts = 800

 x = randomn(seed, nPts) * 50 + 50

 y = randomn(seed, nPts) * 50 + 50


 ;find the extent of the refernce points using the convex hull

 qhull, xRef, yRef, lines


 ;test each of the other points for containment in the convex hull

 intern = bytarr(nPts)

 for i=0, n_elements(lines)/2-1 do begin

   seg = lines[*,i]

   a = yRef[seg[0]] - y

   b = yRef[seg[1]] gt y

   w0 = a/(yRef[seg[0]] - yRef[seg[1]])

   xval = xRef[seg[0]]*(1.0-w0) + xRef[seg[1]]*w0

   ;points are contained when there is an odd number of crossings

   intern xor= ((a gt 0) xor b) and (xval gt x)



 w = where(intern, complement=v)

 p->Add, plot(x[w], y[w], 'go', /over)

 p->Add, plot(x[v], y[v], 'bX', /over)

 for i=0, n_elements(lines)/2-1 do begin

   seg = lines[*,i]

   p->Add, plot(xRef[seg], yRef[seg], 'r', /over)