PointMap3DImpl.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.commons.geometry.euclidean;
import java.util.List;
import org.apache.commons.geometry.core.collection.PointMap;
import org.apache.commons.geometry.core.internal.AbstractBucketPointMap;
import org.apache.commons.geometry.euclidean.internal.Vectors;
import org.apache.commons.geometry.euclidean.threed.Vector3D;
import org.apache.commons.numbers.core.Precision;
/** Internal {@link PointMap} implementation for Euclidean 3D space.
* @param <V> Map value type
*/
final class PointMap3DImpl<V>
extends AbstractBucketPointMap<Vector3D, V>
implements PointMap<Vector3D, V> {
/** Number of children per node. */
private static final int NODE_CHILD_COUNT = 8;
/** Max entries per node. This value was determined empirically and was chosen to
* provide a balance between having a small number of entries in each node when
* searching and having a large number of samples to provide a good split point
* during insertion. See the {@code org.apache.commons.geometry.examples.jmh.euclidean.PointMap3DPerformance}
* class in the {@code examples-jmh} module for details on the performance tests used.
*/
private static final int MAX_ENTRIES_PER_NODE = 32;
/** X negative octant flag. */
private static final int XNEG = 1 << 5;
/** X postive octant flag. */
private static final int XPOS = 1 << 4;
/** Y negative octant flag. */
private static final int YNEG = 1 << 3;
/** Y positive octant flag. */
private static final int YPOS = 1 << 2;
/** Z negative octant flag. */
private static final int ZNEG = 1 << 1;
/** Z positive octant flag. */
private static final int ZPOS = 1;
/** Bit mask for x location. */
private static final int XMASK = XNEG | XPOS;
/** Bit mask for y location. */
private static final int YMASK = YNEG | YPOS;
/** Bit mask for z location. */
private static final int ZMASK = ZNEG | ZPOS;
/** Octant location flags for child nodes. */
private static final int[] CHILD_LOCATIONS = {
XNEG | YNEG | ZNEG,
XNEG | YNEG | ZPOS,
XNEG | YPOS | ZNEG,
XNEG | YPOS | ZPOS,
XPOS | YNEG | ZNEG,
XPOS | YNEG | ZPOS,
XPOS | YPOS | ZNEG,
XPOS | YPOS | ZPOS
};
/** Construct a new instance using the given precision context to determine
* floating point equality.
* @param precision precision context
*/
PointMap3DImpl(final Precision.DoubleEquivalence precision) {
super(MapNode3D::new,
MAX_ENTRIES_PER_NODE,
NODE_CHILD_COUNT,
precision);
}
/** {@inheritDoc} */
@Override
protected boolean pointsEq(final Vector3D a, final Vector3D b) {
return a.eq(b, getPrecision());
}
/** {@inheritDoc} */
@Override
protected int disambiguatePointComparison(final Vector3D a, final Vector3D b) {
return Vector3D.COORDINATE_ASCENDING_ORDER.compare(a, b);
}
/** Tree node class for {@link PointMap3DImpl}.
* @param <V> Map value type
*/
private static final class MapNode3D<V> extends BucketNode<Vector3D, V> {
/** Point to split child spaces; will be null for leaf nodes. */
private Vector3D split;
/** Construct a new instance.
* @param map owning map
* @param parent parent node; set to null for the root node
* @param childIndex index of this node in its parent's child list;
* set to {@code -1} for the root node
*/
MapNode3D(final AbstractBucketPointMap<Vector3D, V> map,
final BucketNode<Vector3D, V> parent,
final int childIndex) {
super(map, parent, childIndex);
}
/** {@inheritDoc} */
@Override
protected void computeSplit() {
final Vector3D.Sum sum = Vector3D.Sum.create();
for (final Entry<Vector3D, V> entry : this) {
sum.add(entry.getKey());
}
split = sum.get().multiply(1.0 / MAX_ENTRIES_PER_NODE);
}
/** {@inheritDoc} */
@Override
protected int getSearchLocation(final Vector3D pt) {
final Precision.DoubleEquivalence precision = getPrecision();
int loc = getSearchLocationValue(
precision.compare(pt.getX(), split.getX()),
XNEG,
XPOS);
loc |= getSearchLocationValue(
precision.compare(pt.getY(), split.getY()),
YNEG,
YPOS);
loc |= getSearchLocationValue(
precision.compare(pt.getZ(), split.getZ()),
ZNEG,
ZPOS);
return loc;
}
/** {@inheritDoc} */
@Override
protected int getInsertLocation(final Vector3D pt) {
int loc = getInsertLocationValue(
Double.compare(pt.getX(), split.getX()),
XNEG,
XPOS);
loc |= getInsertLocationValue(
Double.compare(pt.getY(), split.getY()),
YNEG,
YPOS);
loc |= getInsertLocationValue(
Double.compare(pt.getZ(), split.getZ()),
ZNEG,
ZPOS);
return loc;
}
/** {@inheritDoc} */
@Override
protected boolean testChildLocation(final int childIdx, final int loc) {
final int childLoc = CHILD_LOCATIONS[childIdx];
return (childLoc & loc) == childLoc;
}
/** {@inheritDoc} */
@Override
protected void makeLeaf(final List<Entry<Vector3D, V>> leafEntries) {
super.makeLeaf(leafEntries);
split = null;
}
/** {@inheritDoc} */
@Override
protected double getMinChildDistance(final int childIdx, final Vector3D pt, final int ptLoc) {
final int childLoc = CHILD_LOCATIONS[childIdx];
final boolean sameX = (ptLoc & XMASK) == (childLoc & XMASK);
final boolean sameY = (ptLoc & YMASK) == (childLoc & YMASK);
final boolean sameZ = (ptLoc & ZMASK) == (childLoc & ZMASK);
final Vector3D diff = pt.subtract(split);
if (sameX) {
if (sameY) {
return sameZ ?
0d :
Math.abs(diff.getZ());
}
return sameZ ?
Math.abs(diff.getY()) :
Vectors.norm(diff.getY(), diff.getZ());
} else if (sameY) {
return sameZ ?
Math.abs(diff.getX()) :
Vectors.norm(diff.getX(), diff.getZ());
} else if (sameZ) {
return Vectors.norm(diff.getX(), diff.getY());
}
return diff.norm();
}
/** {@inheritDoc} */
@Override
protected double getMaxChildDistance(final int childIdx, final Vector3D pt, final int ptLoc) {
final MapNode3D<V> grandParent = (MapNode3D<V>) getParent();
if (grandParent != null) {
final int nodeLoc = CHILD_LOCATIONS[getChildIndex()];
final int childLoc = CHILD_LOCATIONS[childIdx];
final boolean oppositeX = (nodeLoc & XMASK) != (childLoc & XMASK);
final boolean oppositeY = (nodeLoc & YMASK) != (childLoc & YMASK);
final boolean oppositeZ = (nodeLoc & ZMASK) != (childLoc & ZMASK);
if (oppositeX && oppositeY && oppositeZ) {
// the grandparent and parent splits form a completely enclosed region,
// meaning that we can determine a max distance
final Vector3D diff = Vector3D.of(
getMaxDistance(pt.getX(), grandParent.split.getX(), split.getX()),
getMaxDistance(pt.getY(), grandParent.split.getY(), split.getY()),
getMaxDistance(pt.getZ(), grandParent.split.getZ(), split.getZ())
);
return diff.norm();
}
}
return Double.POSITIVE_INFINITY;
}
}
}