No rating

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

Atle Borsholm

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()

;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] - y

b = yRef[seg] gt y

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

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

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

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

endfor

w = where(intern, complement=v)

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

seg = lines[*,i]

endfor

end