4531 Rate this article:
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()

 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

 

MOST RECENT

A Technical Dive into Creating Accurate Digital Terrain Models

6/27/2018

Live Webinar | July 25 Creating accurate digital terrain models (DTMs) is essential for modeling areas of... more »

The Science, and Art, of Hyperspectral Image Analysis

6/7/2018

Harris Geospatial Solutions – June 7, 2018 Automation is being touted as the wave of the future for... more »

SIGN UP & STAY INFORMED

Sign up to receive the latest news, events, technologies and special offers.

SIGN ME UP