Difference between revisions of "Thread:User talk:Rednaxela/kD-Tree/Unit tests for KdTree/reply (6)"
Jump to navigation
Jump to search
(Reply to Unit tests for KdTree) |
(No difference)
|
Latest revision as of 18:20, 28 May 2012
Thanks for your quick reply!
Good to know that the bounds don't affect the correctness. I agree, then it is a performance trade-off to adjust them or not.
You only really need to perform "merge siblings" when ALL points from the node are removed, isn't it?
Indeed, the size of the node itself must be adjusted as well:
KdNode<T> parent = cursor.parent; do { parent.size--; parent = cursor.parent; } while (parent != null);
Also ArrayUtil.remove is my own method:
/** * Remove the element from the array at location i. * @param as original array. * @param i index indicating the element to be removed. * @return new array with length (as.length-1) if a is contained in as, or else a copy of the original array. */ public static int[] remove(int[] as, int i){ int n = as.length; if(i < 0 || i >= n) { return Arrays.copyOf(as, n); } int[] copy = new int[n-1]; System.arraycopy(as,0,copy,0,i); System.arraycopy(as,i+1,copy,i,n-1-i); return copy; } public static int[] remove(int[] as, int i){ int n = as.length; if(i < 0 || i >= n) { return copyOf(as, n); } int[] copy = new int[n-1]; System.arraycopy(as,0,copy,0,i); System.arraycopy(as,i+1,copy,i,n-1-i); return copy; }
Removal is O(n), but you cant do much better. There is also a variant for double[] and double[][].
The bounds indeed really need to determine the min and max by iterating over all points.
Back to the keyboard...