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    }