    001    /*
    002     * Licensed to the Apache Software Foundation (ASF) under one or more
    003     * contributor license agreements.  See the NOTICE file distributed with
    004     * this work for additional information regarding copyright ownership.
    005     * The ASF licenses this file to You under the Apache License, Version 2.0
    006     * (the "License"); you may not use this file except in compliance with
    007     * the License.  You may obtain a copy of the License at
    008     *
    009     *      http://www.apache.org/licenses/LICENSE-2.0
    010     *
    011     * Unless required by applicable law or agreed to in writing, software
    012     * distributed under the License is distributed on an "AS IS" BASIS,
    013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014     * See the License for the specific language governing permissions and
    015     * limitations under the License.
    016     */
    017    package org.apache.commons.math3.geometry.euclidean.twod;
    018
    019    import java.util.ArrayList;
    020    import java.util.List;
    021
    022    import org.apache.commons.math3.geometry.euclidean.oned.Euclidean1D;
    023    import org.apache.commons.math3.geometry.euclidean.oned.Interval;
    024    import org.apache.commons.math3.geometry.euclidean.oned.IntervalsSet;
    025    import org.apache.commons.math3.geometry.euclidean.oned.OrientedPoint;
    026    import org.apache.commons.math3.geometry.euclidean.oned.Vector1D;
    027    import org.apache.commons.math3.geometry.partitioning.AbstractSubHyperplane;
    028    import org.apache.commons.math3.geometry.partitioning.BSPTree;
    029    import org.apache.commons.math3.geometry.partitioning.Hyperplane;
    030    import org.apache.commons.math3.geometry.partitioning.Region;
    031    import org.apache.commons.math3.geometry.partitioning.Region.Location;
    032    import org.apache.commons.math3.geometry.partitioning.Side;
    033    import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
    034    import org.apache.commons.math3.util.FastMath;
    035
    036    /** This class represents a sub-hyperplane for {@link Line}.
    037     * @version $Id: SubLine.java 1416643 2012-12-03 19:37:14Z tn $
    038     * @since 3.0
    039     */
    040    public class SubLine extends AbstractSubHyperplane<Euclidean2D, Euclidean1D> {
    041
    042        /** Simple constructor.
    043         * @param hyperplane underlying hyperplane
    044         * @param remainingRegion remaining region of the hyperplane
    045         */
    046        public SubLine(final Hyperplane<Euclidean2D> hyperplane,
    047                       final Region<Euclidean1D> remainingRegion) {
    048            super(hyperplane, remainingRegion);
    049        }
    050
    051        /** Create a sub-line from two endpoints.
    052         * @param start start point
    053         * @param end end point
    054         */
    055        public SubLine(final Vector2D start, final Vector2D end) {
    056            super(new Line(start, end), buildIntervalSet(start, end));
    057        }
    058
    059        /** Create a sub-line from a segment.
    060         * @param segment single segment forming the sub-line
    061         */
    062        public SubLine(final Segment segment) {
    063            super(segment.getLine(), buildIntervalSet(segment.getStart(), segment.getEnd()));
    064        }
    065
    066        /** Get the endpoints of the sub-line.
    067         * <p>
    068         * A subline may be any arbitrary number of disjoints segments, so the endpoints
    069         * are provided as a list of endpoint pairs. Each element of the list represents
    070         * one segment, and each segment contains a start point at index 0 and an end point
    071         * at index 1. If the sub-line is unbounded in the negative infinity direction,
    072         * the start point of the first segment will have infinite coordinates. If the
    073         * sub-line is unbounded in the positive infinity direction, the end point of the
    074         * last segment will have infinite coordinates. So a sub-line covering the whole
    075         * line will contain just one row and both elements of this row will have infinite
    076         * coordinates. If the sub-line is empty, the returned list will contain 0 segments.
    077         * </p>
    078         * @return list of segments endpoints
    079         */
    080        public List<Segment> getSegments() {
    081
    082            final Line line = (Line) getHyperplane();
    083            final List<Interval> list = ((IntervalsSet) getRemainingRegion()).asList();
    084            final List<Segment> segments = new ArrayList<Segment>();
    085
    086            for (final Interval interval : list) {
    087                final Vector2D start = line.toSpace(new Vector1D(interval.getInf()));
    088                final Vector2D end   = line.toSpace(new Vector1D(interval.getSup()));
    089                segments.add(new Segment(start, end, line));
    090            }
    091
    092            return segments;
    093
    094        }
    095
    096        /** Get the intersection of the instance and another sub-line.
    097         * <p>
    098         * This method is related to the {@link Line#intersection(Line)
    099         * intersection} method in the {@link Line Line} class, but in addition
    100         * to compute the point along infinite lines, it also checks the point
    101         * lies on both sub-line ranges.
    102         * </p>
    103         * @param subLine other sub-line which may intersect instance
    104         * @param includeEndPoints if true, endpoints are considered to belong to
    105         * instance (i.e. they are closed sets) and may be returned, otherwise endpoints
    106         * are considered to not belong to instance (i.e. they are open sets) and intersection
    107         * occurring on endpoints lead to null being returned
    108         * @return the intersection point if there is one, null if the sub-lines don't intersect
    109         */
    110        public Vector2D intersection(final SubLine subLine, final boolean includeEndPoints) {
    111
    112            // retrieve the underlying lines
    113            Line line1 = (Line) getHyperplane();
    114            Line line2 = (Line) subLine.getHyperplane();
    115
    116            // compute the intersection on infinite line
    117            Vector2D v2D = line1.intersection(line2);
    118
    119            // check location of point with respect to first sub-line
    120            Location loc1 = getRemainingRegion().checkPoint(line1.toSubSpace(v2D));
    121
    122            // check location of point with respect to second sub-line
    123            Location loc2 = subLine.getRemainingRegion().checkPoint(line2.toSubSpace(v2D));
    124
    125            if (includeEndPoints) {
    126                return ((loc1 != Location.OUTSIDE) && (loc2 != Location.OUTSIDE)) ? v2D : null;
    127            } else {
    128                return ((loc1 == Location.INSIDE) && (loc2 == Location.INSIDE)) ? v2D : null;
    129            }
    130
    131        }
    132
    133        /** Build an interval set from two points.
    134         * @param start start point
    135         * @param end end point
    136         * @return an interval set
    137         */
    138        private static IntervalsSet buildIntervalSet(final Vector2D start, final Vector2D end) {
    139            final Line line = new Line(start, end);
    140            return new IntervalsSet(line.toSubSpace(start).getX(),
    141                                    line.toSubSpace(end).getX());
    142        }
    143
    144        /** {@inheritDoc} */
    145        @Override
    146        protected AbstractSubHyperplane<Euclidean2D, Euclidean1D> buildNew(final Hyperplane<Euclidean2D> hyperplane,
    147                                                                           final Region<Euclidean1D> remainingRegion) {
    148            return new SubLine(hyperplane, remainingRegion);
    149        }
    150
    151        /** {@inheritDoc} */
    152        @Override
    153        public Side side(final Hyperplane<Euclidean2D> hyperplane) {
    154
    155            final Line    thisLine  = (Line) getHyperplane();
    156            final Line    otherLine = (Line) hyperplane;
    157            final Vector2D crossing  = thisLine.intersection(otherLine);
    158
    159            if (crossing == null) {
    160                // the lines are parallel,
    161                final double global = otherLine.getOffset(thisLine);
    162                return (global < -1.0e-10) ? Side.MINUS : ((global > 1.0e-10) ? Side.PLUS : Side.HYPER);
    163            }
    164
    165            // the lines do intersect
    166            final boolean direct = FastMath.sin(thisLine.getAngle() - otherLine.getAngle()) < 0;
    167            final Vector1D x = thisLine.toSubSpace(crossing);
    168            return getRemainingRegion().side(new OrientedPoint(x, direct));
    169
    170        }
    171
    172        /** {@inheritDoc} */
    173        @Override
    174        public SplitSubHyperplane<Euclidean2D> split(final Hyperplane<Euclidean2D> hyperplane) {
    175
    176            final Line    thisLine  = (Line) getHyperplane();
    177            final Line    otherLine = (Line) hyperplane;
    178            final Vector2D crossing  = thisLine.intersection(otherLine);
    179
    180            if (crossing == null) {
    181                // the lines are parallel
    182                final double global = otherLine.getOffset(thisLine);
    183                return (global < -1.0e-10) ?
    184                       new SplitSubHyperplane<Euclidean2D>(null, this) :
    185                       new SplitSubHyperplane<Euclidean2D>(this, null);
    186            }
    187
    188            // the lines do intersect
    189            final boolean direct = FastMath.sin(thisLine.getAngle() - otherLine.getAngle()) < 0;
    190            final Vector1D x      = thisLine.toSubSpace(crossing);
    191            final SubHyperplane<Euclidean1D> subPlus  = new OrientedPoint(x, !direct).wholeHyperplane();
    192            final SubHyperplane<Euclidean1D> subMinus = new OrientedPoint(x,  direct).wholeHyperplane();
    193
    194            final BSPTree<Euclidean1D> splitTree = getRemainingRegion().getTree(false).split(subMinus);
    195            final BSPTree<Euclidean1D> plusTree  = getRemainingRegion().isEmpty(splitTree.getPlus()) ?
    196                                                   new BSPTree<Euclidean1D>(Boolean.FALSE) :
    197                                                   new BSPTree<Euclidean1D>(subPlus, new BSPTree<Euclidean1D>(Boolean.FALSE),
    198                                                                            splitTree.getPlus(), null);
    199            final BSPTree<Euclidean1D> minusTree = getRemainingRegion().isEmpty(splitTree.getMinus()) ?
    200                                                   new BSPTree<Euclidean1D>(Boolean.FALSE) :
    201                                                   new BSPTree<Euclidean1D>(subMinus, new BSPTree<Euclidean1D>(Boolean.FALSE),
    202                                                                            splitTree.getMinus(), null);
    203
    204            return new SplitSubHyperplane<Euclidean2D>(new SubLine(thisLine.copySelf(), new IntervalsSet(plusTree)),
    205                                                       new SubLine(thisLine.copySelf(), new IntervalsSet(minusTree)));
    206
    207        }
    208
    209    }