An efficient implementation of 2-D classification to a convex hull reference
Anonym
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)
endfor
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)
endfor
end