Flattener3d.java
package org.djutils.draw.curve;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.NavigableMap;
import java.util.Set;
import java.util.TreeMap;
import org.djutils.draw.Direction3d;
import org.djutils.draw.line.PolyLine3d;
import org.djutils.draw.point.Point3d;
import org.djutils.exceptions.Throw;
/**
* Flattens a Curve3d in to a PolyLine3d.
* <p>
* Copyright (c) 2023-2025 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
* BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
* </p>
* @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
* @author <a href="https://github.com/peter-knoppers">Peter Knoppers</a>
* @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
*/
public interface Flattener3d extends Flattener<Flattener3d, Curve3d, PolyLine3d, Point3d, Direction3d>
{
/**
* Flatten a Curve3d into a PolyLine3d.
* @param curve the curve
* @return flattened line
* @throws NullPointerException when <code>curve</code> is <code>null</code>
*/
PolyLine3d flatten(Curve3d curve);
@Override
default boolean checkInflectionPoint(final FlattableCurve<Point3d, Direction3d> curve, final double prevT,
final double medianT, final double nextT, final Point3d prevPoint, final Point3d nextPoint)
{
Point3d oneQuarter = curve.getPoint((prevT + medianT) / 2);
Direction3d oneQDir = oneQuarter.directionTo(oneQuarter.closestPointOnSegment(prevPoint, nextPoint));
Point3d threeQuarter = curve.getPoint((nextT + medianT) / 2);
Direction3d threeQDir = threeQuarter.directionTo(threeQuarter.closestPointOnSegment(prevPoint, nextPoint));
Double angle = oneQDir.directionDifference(threeQDir);
return angle > Math.PI / 2; // Direction varies by more than 90 degrees
}
@Override
default boolean checkLoopBack(final Direction3d prevDirection, final Direction3d nextDirection)
{
return prevDirection.directionDifference(nextDirection) > Math.PI / 2;
}
@Override
default boolean checkDirectionError(final Direction3d segmentDirection, final Direction3d curveDirectionAtStart,
final Direction3d curveDirectionAtEnd, final double maxDirectionDeviation)
{
return (segmentDirection.directionDifference(curveDirectionAtStart) > maxDirectionDeviation
|| segmentDirection.directionDifference(curveDirectionAtEnd) > maxDirectionDeviation);
}
/**
* Flattener that approximates the <code>Curve3d</code> with a specified number of segments.
*/
class NumSegments implements Flattener3d
{
/** Number of segments. */
private final int numSegments;
/**
* Construct a flattener that approximates the <code>Curve3d</code> with a specified number of segments.
* @param numSegments number of segments to use in the construction of the PolyLine3d.
* @throws IllegalArgumentException when <code>numSegments < 1</code>
*/
public NumSegments(final int numSegments)
{
Throw.when(numSegments < 1, IllegalArgumentException.class, "Number of segments must be at least 1");
this.numSegments = numSegments;
}
@Override
public PolyLine3d flatten(final Curve3d curve) throws NullPointerException
{
Throw.whenNull(curve, "curve");
List<Point3d> points = new ArrayList<>(this.numSegments + 1);
for (int i = 0; i <= this.numSegments; i++)
{
double fraction = ((double) i) / this.numSegments;
points.add(curve.getPoint(fraction));
}
return new PolyLine3d(points);
}
}
/**
* Flattener that limits the distance between the <code>Curve3d</code> and the <code>PolyLine3d</code>.
*/
class MaxDeviation implements Flattener3d
{
/** Maximum deviation. */
private final double maxDeviation;
/**
* Construct a flattener that limits the distance between the <code>Curve3d</code> and the <code>PolyLine3d</code>.
* @param maxDeviation maximum deviation, must be above 0.0.
* @throws ArithmeticException when <code>maxDeviation</code> is <code>NaN</code>
* @throws IllegalArgumentException when <code>maxDeviation ≤ 0.0</code>
*/
public MaxDeviation(final double maxDeviation)
{
Throw.whenNaN(maxDeviation, "maxDeviation");
Throw.when(maxDeviation <= 0.0, IllegalArgumentException.class, "Maximum deviation must be above 0.0 and finite");
this.maxDeviation = maxDeviation;
}
@Override
public PolyLine3d flatten(final Curve3d curve)
{
Throw.whenNull(curve, "curve");
NavigableMap<Double, Point3d> result = new TreeMap<>();
loadKnots(result, curve);
// Walk along all point pairs and see if additional points need to be inserted
double prevT = result.firstKey();
Point3d prevPoint = result.get(prevT);
Map.Entry<Double, Point3d> entry;
while ((entry = result.higherEntry(prevT)) != null)
{
double nextT = entry.getKey();
Point3d nextPoint = entry.getValue();
double medianT = (prevT + nextT) / 2;
Point3d medianPoint = curve.getPoint(medianT);
// Check max deviation
if (checkPositionError(medianPoint, prevPoint, nextPoint, this.maxDeviation))
{
// We need to insert another point
result.put(medianT, medianPoint);
continue;
}
if (prevPoint.distance(nextPoint) > this.maxDeviation
&& checkInflectionPoint(curve, prevT, medianT, nextT, prevPoint, nextPoint))
{
// There is an inflection point, inserting the halfway point should take care of this
result.put(medianT, medianPoint);
continue;
}
if (checkLoopBack(curve.getDirection(prevT), curve.getDirection(nextT)))
{
// The curve loops back onto itself. Inserting the halfway point should prevent missing out a major detour
// This check is NOT needed in the MaxDeviationAndAngle flattener.
result.put(medianT, medianPoint);
continue;
}
prevT = nextT;
prevPoint = nextPoint;
}
return new PolyLine3d(result.values().iterator());
}
}
/**
* Flattener that limits the distance <b>and</b> angle difference between the <code>Curve3d</code> and the
* <code>PolyLine3d</code>.
*/
class MaxDeviationAndAngle implements Flattener3d
{
/** Maximum deviation. */
private final double maxDeviation;
/** Maximum angle. */
private final double maxAngle;
/**
* Construct a flattener that limits the distance <b>and</b> angle difference between the <code>curve3d</code> and the
* <code>PolyLine3d</code>.
* @param maxDeviation maximum deviation, must be above 0.0
* @param maxAngle maximum angle, must be above 0.0
* @throws ArithmeticException when <code>maxDeviation</code>, or <code>maxAngle</code> is <code>NaN</code>
* @throws IllegalArgumentException when <code>maxDeviation ≤ 0.0</code>, or <code>maxAngle ≤ 0.0</code>
*/
public MaxDeviationAndAngle(final double maxDeviation, final double maxAngle)
{
Throw.whenNaN(maxDeviation, "maxDeviation");
Throw.whenNaN(maxAngle, "maxAngle");
Throw.when(maxDeviation <= 0.0, IllegalArgumentException.class, "Maximum deviation must be above 0.0 and finite");
Throw.when(maxAngle <= 0.0, IllegalArgumentException.class, "Maximum angle must be above 0.0");
this.maxDeviation = maxDeviation;
this.maxAngle = maxAngle;
}
@Override
public PolyLine3d flatten(final Curve3d curve) throws NullPointerException
{
NavigableMap<Double, Point3d> result = new TreeMap<>();
loadKnots(result, curve);
Map<Double, Direction3d> directions = new LinkedHashMap<>();
Set<Double> knots = new HashSet<>();
for (double fraction : result.keySet())
{
directions.put(fraction, curve.getDirection(fraction));
knots.add(fraction);
}
// Walk along all point pairs and see if additional points need to be inserted
double prevT = result.firstKey();
Point3d prevPoint = result.get(prevT);
Map.Entry<Double, Point3d> entry;
int iterationsAtSinglePoint = 0;
while ((entry = result.higherEntry(prevT)) != null)
{
double nextT = entry.getKey();
Point3d nextPoint = entry.getValue();
double medianT = (prevT + nextT) / 2;
Point3d medianPoint = curve.getPoint(medianT);
// Check max deviation
if (checkPositionError(medianPoint, prevPoint, nextPoint, this.maxDeviation))
{
// We need to insert another point
result.put(medianT, medianPoint);
directions.put(medianT, curve.getDirection(medianT));
continue;
}
// Check max angle
if (checkDirectionError(prevPoint.directionTo(nextPoint), directions.get(prevT), directions.get(nextT),
this.maxAngle))
{
// We need to insert another point
result.put(medianT, medianPoint);
directions.put(medianT, curve.getDirection(medianT));
iterationsAtSinglePoint++;
Throw.when(iterationsAtSinglePoint == 50, IllegalArgumentException.class,
"Required a new point 50 times "
+ "around the same point (t=%f). Likely there is an (unreported) knot in the Curve3d.",
medianT);
continue;
}
iterationsAtSinglePoint = 0;
if (prevPoint.distance(nextPoint) > this.maxDeviation
&& checkInflectionPoint(curve, prevT, medianT, nextT, prevPoint, nextPoint))
{
// There is an inflection point, inserting the halfway point should take care of this
result.put(medianT, medianPoint);
directions.put(medianT, curve.getDirection(medianT));
continue;
}
prevT = nextT;
prevPoint = nextPoint;
if (knots.contains(prevT))
{
directions.put(prevT, curve.getDirection(prevT + Math.ulp(prevT)));
}
}
return new PolyLine3d(result.values().iterator());
}
}
/**
* Flattener that limits the angle difference between the <code>Curve3d</code> and the <code>PolyLine3d</code>.
*/
class MaxAngle implements Flattener3d
{
/** Maximum angle. */
private final double maxAngle;
/**
* Flattener that limits the angle difference between the <code>Curve3d</code> and the <code>PolyLine3d</code>.
* @param maxAngle maximum angle
* @throws ArithmeticException when <code>maxAngle</code> is <code>NaN</code>
* @throws IllegalArgumentException when <code>maxAngle ≤ 0.0</code>
*/
public MaxAngle(final double maxAngle)
{
Throw.whenNaN(maxAngle, "maxAngle");
Throw.when(maxAngle <= 0.0, IllegalArgumentException.class, "Maximum angle must be above 0.0");
this.maxAngle = maxAngle;
}
@Override
public PolyLine3d flatten(final Curve3d curve)
{
NavigableMap<Double, Point3d> result = new TreeMap<>();
loadKnots(result, curve);
Map<Double, Direction3d> directions = new LinkedHashMap<>();
directions.put(0.0, curve.getDirection(0.0)); // directions can't do ULP before 0.0
Set<Double> knots = new HashSet<>();
for (double knot : result.keySet())
{
if (knot > 0)
{
directions.put(knot, curve.getDirection(knot - Math.ulp(knot)));
}
if (knot != 0.0 && knot != 1.0)
{
knots.add(knot);
}
}
// Walk along all point pairs and see if additional points need to be inserted
double prevT = result.firstKey();
Point3d prevPoint = result.get(prevT);
Map.Entry<Double, Point3d> entry;
int iterationsAtSinglePoint = 0;
while ((entry = result.higherEntry(prevT)) != null)
{
double nextT = entry.getKey();
Point3d nextPoint = entry.getValue();
double medianT = (prevT + nextT) / 2;
// Check max angle
if (checkDirectionError(prevPoint.directionTo(nextPoint), directions.get(prevT), directions.get(nextT),
this.maxAngle))
{
// We need to insert another point
Point3d medianPoint = curve.getPoint(medianT);
result.put(medianT, medianPoint);
directions.put(medianT, curve.getDirection(medianT));
iterationsAtSinglePoint++;
Throw.when(iterationsAtSinglePoint == 50, IllegalArgumentException.class,
"Required a new point 50 times "
+ "around the same point (t=%f). Likely there is an (unreported) knot in the Curve3d.",
medianT);
continue;
}
iterationsAtSinglePoint = 0;
if (checkInflectionPoint(curve, prevT, medianT, nextT, prevPoint, nextPoint))
{
// There is an inflection point, inserting the halfway point should take care of this
Point3d medianPoint = curve.getPoint(medianT);
result.put(medianT, medianPoint);
directions.put(medianT, curve.getDirection(medianT));
continue;
}
prevT = nextT;
prevPoint = nextPoint;
if (knots.contains(prevT))
{
directions.put(prevT, curve.getDirection(prevT + Math.ulp(prevT)));
}
}
return new PolyLine3d(result.values().iterator());
}
}
}