http://robowiki.net/w/index.php?title=Thread:User_talk:Rednaxela/kD-Tree/Unit_tests_for_KdTree/reply_(4)&feed=atom&action=historyThread:User talk:Rednaxela/kD-Tree/Unit tests for KdTree/reply (4) - Revision history2024-03-29T14:19:24ZRevision history for this page on the wikiMediaWiki 1.34.1http://robowiki.net/w/index.php?title=Thread:User_talk:Rednaxela/kD-Tree/Unit_tests_for_KdTree/reply_(4)&diff=24535&oldid=prevArie: Reply to Unit tests for KdTree2012-05-27T21:21:06Z<p>Reply to <a href="/wiki/Thread:User_talk:Rednaxela/kD-Tree/Unit_tests_for_KdTree" title="Thread:User talk:Rednaxela/kD-Tree/Unit tests for KdTree">Unit tests for KdTree</a></p>
<p><b>New page</b></p><div>Hi Rednaxela & Ojd,<br />
<br />
I'd like to have remove functionality and added the method below to KdNode. It is based on Ojd's C# variant and adjusts. KdNode needs and extra field: parent. It seems to do what I want, but feel not confident about some points:<br />
* do the bounds of parent nodes to be adjusted as well?<br />
* how to add it nicely to the NearestNeighborIterator?<br />
* what if you want to re-weight after n removals? (remove remainder and add again?)<br />
<br />
Thanks, Arie<br />
<pre><br />
public boolean remove(double[] point, T value)<br />
{<br />
KdNode<T> cursor = this;<br />
while (!cursor.isLeaf()) {<br />
if (point[cursor.splitDimension] > cursor.splitValue) {<br />
cursor = cursor.left;<br />
} else {<br />
cursor = cursor.right;<br />
}<br />
}<br />
for (int i = 0; i < cursor.size; i++) {<br />
if (cursor.data[i].equals(value)) {<br />
double[] cursorPoint = cursor.points[i];<br />
// remove this points<br />
cursor.data = ArrayUtil.remove(cursor.data, i);<br />
cursor.points = ArrayUtil.remove(cursor.points, i);<br />
<br />
// fix tree size all the way up to the root<br />
KdNode<T> parent = cursor.parent;<br />
do {<br />
parent.size--;<br />
parent = cursor.parent;<br />
} while (parent != null);<br />
<br />
<br />
// adjust _minBound and _maxBound after removing an item.<br />
if(cursor.points.length > 0){<br />
for (int j = 0; j < dimensions; j++) {<br />
if (Double.isNaN(cursorPoint[j])) {<br />
if (!Double.isNaN(minBound[j]) || !Double.isNaN(maxBound[j])) {<br />
singlePoint = false;<br />
}<br />
minBound[j] = Double.NaN;<br />
maxBound[j] = Double.NaN;<br />
}<br />
else if (minBound[j] > cursorPoint[j]) {<br />
minBound[j] = cursorPoint[i];<br />
singlePoint = false;<br />
}<br />
else if (maxBound[j] < cursorPoint[i]) {<br />
maxBound[j] = cursorPoint[i];<br />
singlePoint = false;<br />
}<br />
}<br />
}<br />
else{<br />
// last point at this cursor was removed.<br />
minBound = null;<br />
maxBound = null;<br />
}<br />
return true;<br />
}<br />
}<br />
return false;<br />
}<br />
</pre></div>Arie