d = ‖p - q‖ ≥ ‖p - q"'‖ = ‖ ( d1 , d2 ) ‖ = δ (p, q)
x' := xs + <x - xs , v> v
kx := ‖x' - xs‖
hx := x' - x
d1 := |kp - kq| = ‖p' - q'‖
d2 := | ‖hp‖ - ‖hq‖ |
p
xs = xs'
q
xe
d
d1
d2
kp
kq
p'
q'
xs" = xs + hp
hq
q" = xs" + kq ∙ v
q"'
d"'
hp
q"' is in the layer through p, created by the vectors v and hp , on the line q'q" with the distance ‖hq‖ from the line xsxe.
x0
xs
x
x
x
x
x
x
x
xe
u
u := xe - xs
v := u / ‖u‖
‖x‖ := sqrt( <x , x> )
<x , y> := x1 y1 + x2 y2 + x3 y3 + ...
data = {x0, x1, x2, ...}
for i in {0, 1, 2, 3, ...}:
for k in {0,1,2, ..., n}:
if |Ni| < nebSize:
Sort { π0, π1, ... πn } = { 0, 1,2, ..., n } so that Δ(i, πj ) ≤ Δ(i, πj+1) for all j in {0, 1, ... , n-1}
Ni ← ∅
Ni ← (Ni / {a}) ∪ {πk}
Ni ← Ni ∪ {πk}
else:
a ← a in Ni with Δ(i, a) ≥ Δ(i, b) for all b in Ni
if ‖xa - x‖ > ‖xπk - x‖:
break loop for k; next x
if ‖xa - x‖ < Δ(πk , i):
return (N0, N1, N2, ..., Nn )
xs ← x in data so that d(x, x0) ≥ d(y, x0) for all y in data
xe ← x in data so that d(x, xs) ≥ d(y, xs) for all y in data
v ← (xe - xs) / d(xe - xs)
H ← ( ‖x'0 - x‖, ‖x'1 - x‖, ‖x'2 - x‖, ..., ‖x'n - x‖ )
K ← ( ‖x'0 - x0‖, ‖x'1 - x1‖, ‖x'2 - x2‖, ..., ‖x'n - xn‖ )
Δ(i, j) = sqrt( (Ki - Kj)2 + (Hi - Hj)2 )