BoundaryProjector.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
*
* https://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.
*/
/*
* This is not the original file distributed by the Apache Software Foundation
* It has been modified by the Hipparchus project
*/
package org.hipparchus.geometry.partitioning;
import java.util.ArrayList;
import java.util.List;
import org.hipparchus.geometry.Point;
import org.hipparchus.geometry.Space;
import org.hipparchus.geometry.partitioning.Region.Location;
import org.hipparchus.util.FastMath;
/** Local tree visitor to compute projection on boundary.
* @param <S> Type of the space.
* @param <P> Type of the points in space.
* @param <H> Type of the hyperplane.
* @param <I> Type of the sub-hyperplane.
* @param <T> Type of the sub-space.
* @param <Q> Type of the points in sub-space.
* @param <F> Type of the hyperplane in the destination sub-space.
* @param <J> Type of the sub-hyperplane in the destination sub-space.
*/
class BoundaryProjector<S extends Space,
P extends Point<S, P>,
H extends Hyperplane<S, P, H, I>,
I extends SubHyperplane<S, P, H, I>,
T extends Space,
Q extends Point<T, Q>,
F extends Hyperplane<T, Q, F, J>,
J extends SubHyperplane<T, Q, F, J>>
implements BSPTreeVisitor<S, P, H, I> {
/** Original point. */
private final P original;
/** Current best projected point. */
private P projected;
/** Leaf node closest to the test point. */
private BSPTree<S, P, H, I> leaf;
/** Current offset. */
private double offset;
/** Simple constructor.
* @param original original point
*/
BoundaryProjector(final P original) {
this.original = original;
this.projected = null;
this.leaf = null;
this.offset = Double.POSITIVE_INFINITY;
}
/** {@inheritDoc} */
@Override
public Order visitOrder(final BSPTree<S, P, H, I> node) {
// we want to visit the tree so that the first encountered
// leaf is the one closest to the test point
if (node.getCut().getHyperplane().getOffset(original) <= 0) {
return Order.MINUS_SUB_PLUS;
} else {
return Order.PLUS_SUB_MINUS;
}
}
/** {@inheritDoc} */
@Override
public void visitInternalNode(final BSPTree<S, P, H, I> node) {
// project the point on the cut sub-hyperplane
final H hyperplane = node.getCut().getHyperplane();
final double signedOffset = hyperplane.getOffset(original);
if (FastMath.abs(signedOffset) < offset) {
// project point
final P regular = hyperplane.project(original);
// get boundary parts
final List<Region<T, Q, F, J>> boundaryParts = boundaryRegions(node);
// check if regular projection really belongs to the boundary
boolean regularFound = false;
for (final Region<T, Q, F, J> part : boundaryParts) {
if (!regularFound && belongsToPart(regular, hyperplane, part)) {
// the projected point lies in the boundary
projected = regular;
offset = FastMath.abs(signedOffset);
regularFound = true;
}
}
if (!regularFound) {
// the regular projected point is not on boundary,
// so we have to check further if a singular point
// (i.e. a vertex in 2D case) is a possible projection
for (final Region<T, Q, F, J> part : boundaryParts) {
final P spI = singularProjection(regular, hyperplane, part);
if (spI != null) {
final double distance = original.distance(spI);
if (distance < offset) {
projected = spI;
offset = distance;
}
}
}
}
}
}
/** {@inheritDoc} */
@Override
public void visitLeafNode(final BSPTree<S, P, H, I> node) {
if (leaf == null) {
// this is the first leaf we visit,
// it is the closest one to the original point
leaf = node;
}
}
/** Get the projection.
* @return projection
*/
public BoundaryProjection<S, P> getProjection() {
// fix offset sign
offset = FastMath.copySign(offset, (Boolean) leaf.getAttribute() ? -1 : +1);
return new BoundaryProjection<>(original, projected, offset);
}
/** Extract the regions of the boundary on an internal node.
* @param node internal node
* @return regions in the node sub-hyperplane
*/
private List<Region<T, Q, F, J>> boundaryRegions(final BSPTree<S, P, H, I> node) {
final List<Region<T, Q, F, J>> regions = new ArrayList<>(2);
@SuppressWarnings("unchecked")
final BoundaryAttribute<S, P, H, I> ba = (BoundaryAttribute<S, P, H, I>) node.getAttribute();
addRegion(ba.getPlusInside(), regions);
addRegion(ba.getPlusOutside(), regions);
return regions;
}
/** Add a boundary region to a list.
* @param sub sub-hyperplane defining the region
* @param list to fill up
*/
private void addRegion(final SubHyperplane<S, P, H, I> sub, final List<Region<T, Q, F, J>> list) {
if (sub != null) {
final Region<T, Q, F, J> region = ((AbstractSubHyperplane<S, P, H, I, T, Q, F, J>) sub).getRemainingRegion();
if (region != null) {
list.add(region);
}
}
}
/** Check if a projected point lies on a boundary part.
* @param point projected point to check
* @param hyperplane hyperplane into which the point was projected
* @param part boundary part
* @return true if point lies on the boundary part
*/
private boolean belongsToPart(final P point, final Hyperplane<S, P, H, I> hyperplane,
final Region<T, Q, F, J> part) {
// there is a non-null sub-space, we can dive into smaller dimensions
@SuppressWarnings("unchecked")
final Embedding<S, P, T, Q> embedding = (Embedding<S, P, T, Q>) hyperplane;
return part.checkPoint(embedding.toSubSpace(point)) != Location.OUTSIDE;
}
/** Get the projection to the closest boundary singular point.
* @param point projected point to check
* @param hyperplane hyperplane into which the point was projected
* @param part boundary part
* @return projection to a singular point of boundary part (may be null)
*/
private P singularProjection(final P point, final Hyperplane<S, P, H, I> hyperplane,
final Region<T, Q, F, J> part) {
// there is a non-null sub-space, we can dive into smaller dimensions
@SuppressWarnings("unchecked")
final Embedding<S, P, T, Q> embedding = (Embedding<S, P, T, Q>) hyperplane;
final BoundaryProjection<T, Q> bp = part.projectToBoundary(embedding.toSubSpace(point));
// back to initial dimension
return (bp.getProjected() == null) ? null : embedding.toSpace(bp.getProjected());
}
}