//package edu.wlu.cs.levy.CG;
|
|
import java.util.List;
|
|
// K-D Tree node class
|
class KDNode<T>
|
{
|
|
// these are seen by KDTree
|
protected HPoint k;
|
T v;
|
protected KDNode<T> left, right;
|
protected boolean deleted;
|
|
// Method ins translated from 352.ins.c of Gonnet & Baeza-Yates
|
protected static <T> int edit(HPoint key, Editor<T> editor, KDNode<T> t, int lev, int K)
|
throws KeyDuplicateException
|
{
|
KDNode<T> next_node = null;
|
int next_lev = (lev + 1) % K;
|
synchronized (t)
|
{
|
if (key.equals(t.k))
|
{
|
boolean was_deleted = t.deleted;
|
t.v = editor.edit(t.deleted ? null : t.v);
|
t.deleted = (t.v == null);
|
|
if (t.deleted == was_deleted)
|
{
|
return 0;
|
} else if (was_deleted)
|
{
|
return -1;
|
}
|
return 1;
|
} else if (key.coord[lev] > t.k.coord[lev])
|
{
|
next_node = t.right;
|
if (next_node == null)
|
{
|
t.right = create(key, editor);
|
return t.right.deleted ? 0 : 1;
|
}
|
} else
|
{
|
next_node = t.left;
|
if (next_node == null)
|
{
|
t.left = create(key, editor);
|
return t.left.deleted ? 0 : 1;
|
}
|
}
|
}
|
|
return edit(key, editor, next_node, next_lev, K);
|
}
|
|
protected static <T> KDNode<T> create(HPoint key, Editor<T> editor)
|
throws KeyDuplicateException
|
{
|
KDNode<T> t = new KDNode<T>(key, editor.edit(null));
|
if (t.v == null)
|
{
|
t.deleted = true;
|
}
|
return t;
|
}
|
|
protected static <T> boolean del(KDNode<T> t)
|
{
|
synchronized (t)
|
{
|
if (!t.deleted)
|
{
|
t.deleted = true;
|
return true;
|
}
|
}
|
return false;
|
}
|
|
// Method srch translated from 352.srch.c of Gonnet & Baeza-Yates
|
protected static <T> KDNode<T> srch(HPoint key, KDNode<T> t, int K)
|
{
|
|
for (int lev = 0; t != null; lev = (lev + 1) % K)
|
{
|
|
if (!t.deleted && key.equals(t.k))
|
{
|
return t;
|
} else if (key.coord[lev] > t.k.coord[lev])
|
{
|
t = t.right;
|
} else
|
{
|
t = t.left;
|
}
|
}
|
|
return null;
|
}
|
|
// Method rsearch translated from 352.range.c of Gonnet & Baeza-Yates
|
protected static <T> void rsearch(HPoint lowk, HPoint uppk, KDNode<T> t, int lev,
|
int K, List<KDNode<T>> v)
|
{
|
|
if (t == null)
|
{
|
return;
|
}
|
if (lowk.coord[lev] <= t.k.coord[lev])
|
{
|
rsearch(lowk, uppk, t.left, (lev + 1) % K, K, v);
|
}
|
if (!t.deleted)
|
{
|
int j = 0;
|
while (j < K && lowk.coord[j] <= t.k.coord[j]
|
&& uppk.coord[j] >= t.k.coord[j])
|
{
|
j++;
|
}
|
if (j == K)
|
{
|
v.add(t);
|
}
|
}
|
if (uppk.coord[lev] > t.k.coord[lev])
|
{
|
rsearch(lowk, uppk, t.right, (lev + 1) % K, K, v);
|
}
|
}
|
|
// Method Nearest Neighbor from Andrew Moore's thesis. Numbered
|
// comments are direct quotes from there. NearestNeighborList solution
|
// courtesy of Bjoern Heckel.
|
protected static <T> void nnbr(KDNode<T> kd, HPoint target, HRect hr,
|
double max_dist_sqd, int lev, int K,
|
NearestNeighborList<KDNode<T>> nnl,
|
CheckerInterface<T> checker,
|
long timeout)
|
{
|
|
// 1. if kd is empty then set dist-sqd to infinity and exit.
|
if (kd == null)
|
{
|
return;
|
}
|
|
if ((timeout > 0) && (timeout < System.currentTimeMillis()))
|
{
|
return;
|
}
|
// 2. s := split field of kd
|
int s = lev % K;
|
|
// 3. pivot := dom-elt field of kd
|
HPoint pivot = kd.k;
|
double pivot_to_target = HPoint.sqrdist(pivot, target);
|
|
// 4. Cut hr into to sub-hyperrectangles left-hr and right-hr.
|
// The cut plane is through pivot and perpendicular to the s
|
// dimension.
|
HRect left_hr = hr; // optimize by not cloning
|
HRect right_hr = (HRect) hr.clone();
|
left_hr.max.coord[s] = pivot.coord[s];
|
right_hr.min.coord[s] = pivot.coord[s];
|
|
// 5. target-in-left := target_s <= pivot_s
|
boolean target_in_left = target.coord[s] < pivot.coord[s];
|
|
KDNode<T> nearer_kd;
|
HRect nearer_hr;
|
KDNode<T> further_kd;
|
HRect further_hr;
|
|
// 6. if target-in-left then
|
// 6.1. nearer-kd := left field of kd and nearer-hr := left-hr
|
// 6.2. further-kd := right field of kd and further-hr := right-hr
|
if (target_in_left)
|
{
|
nearer_kd = kd.left;
|
nearer_hr = left_hr;
|
further_kd = kd.right;
|
further_hr = right_hr;
|
} //
|
// 7. if not target-in-left then
|
// 7.1. nearer-kd := right field of kd and nearer-hr := right-hr
|
// 7.2. further-kd := left field of kd and further-hr := left-hr
|
else
|
{
|
nearer_kd = kd.right;
|
nearer_hr = right_hr;
|
further_kd = kd.left;
|
further_hr = left_hr;
|
}
|
|
// 8. Recursively call Nearest Neighbor with paramters
|
// (nearer-kd, target, nearer-hr, max-dist-sqd), storing the
|
// results in nearest and dist-sqd
|
nnbr(nearer_kd, target, nearer_hr, max_dist_sqd, lev + 1, K, nnl, checker, timeout);
|
|
KDNode<T> nearest = nnl.getHighest();
|
double dist_sqd;
|
|
if (!nnl.isCapacityReached())
|
{
|
dist_sqd = Double.MAX_VALUE;
|
} else
|
{
|
dist_sqd = nnl.getMaxPriority();
|
}
|
|
// 9. max-dist-sqd := minimum of max-dist-sqd and dist-sqd
|
max_dist_sqd = Math.min(max_dist_sqd, dist_sqd);
|
|
// 10. A nearer point could only lie in further-kd if there were some
|
// part of further-hr within distance max-dist-sqd of
|
// target.
|
HPoint closest = further_hr.closest(target);
|
if (HPoint.sqrdist(closest, target) < max_dist_sqd)
|
{
|
|
// 10.1 if (pivot-target)^2 < dist-sqd then
|
if (pivot_to_target < dist_sqd)
|
{
|
|
// 10.1.1 nearest := (pivot, range-elt field of kd)
|
nearest = kd;
|
|
// 10.1.2 dist-sqd = (pivot-target)^2
|
dist_sqd = pivot_to_target;
|
|
// add to nnl
|
if (!kd.deleted && ((checker == null) || checker.usable(kd.v)))
|
{
|
nnl.insert(kd, dist_sqd);
|
}
|
|
// 10.1.3 max-dist-sqd = dist-sqd
|
// max_dist_sqd = dist_sqd;
|
if (nnl.isCapacityReached())
|
{
|
max_dist_sqd = nnl.getMaxPriority();
|
} else
|
{
|
max_dist_sqd = Double.MAX_VALUE;
|
}
|
}
|
|
// 10.2 Recursively call Nearest Neighbor with parameters
|
// (further-kd, target, further-hr, max-dist_sqd),
|
// storing results in temp-nearest and temp-dist-sqd
|
nnbr(further_kd, target, further_hr, max_dist_sqd, lev + 1, K, nnl, checker, timeout);
|
}
|
}
|
|
// constructor is used only by class; other methods are static
|
private KDNode(HPoint key, T val)
|
{
|
|
k = key;
|
v = val;
|
left = null;
|
right = null;
|
deleted = false;
|
}
|
|
protected String toString(int depth)
|
{
|
String s = k + " " + v + (deleted ? "*" : "");
|
if (left != null)
|
{
|
s = s + "\n" + pad(depth) + "L " + left.toString(depth + 1);
|
}
|
if (right != null)
|
{
|
s = s + "\n" + pad(depth) + "R " + right.toString(depth + 1);
|
}
|
return s;
|
}
|
|
private static String pad(int n)
|
{
|
String s = "";
|
for (int i = 0; i < n; ++i)
|
{
|
s += " ";
|
}
|
return s;
|
}
|
|
private static void hrcopy(HRect hr_src, HRect hr_dst)
|
{
|
hpcopy(hr_src.min, hr_dst.min);
|
hpcopy(hr_src.max, hr_dst.max);
|
}
|
|
private static void hpcopy(HPoint hp_src, HPoint hp_dst)
|
{
|
for (int i = 0; i < hp_dst.coord.length; ++i)
|
{
|
hp_dst.coord[i] = hp_src.coord[i];
|
}
|
}
|
}
|
