Java 类com.vividsolutions.jts.geom.LineSegment 实例源码

private static LinearRing ringFromSegments(List<LineSegment> segments) {
    GeometryFactory factory = new GeometryFactory();
    int nSegs = segments.size();
    if (nSegs < 3) {
        return null;
    }
    int len = segments.size() + 1;
    CoordinateSequence seq = factory.getCoordinateSequenceFactory().create(
            len, 2);
    int i = 0;
    for (LineSegment line : segments) {
        seq.setOrdinate(i, 0, line.p0.x);
        seq.setOrdinate(i, 1, line.p0.y);
        i++;
    }
    seq.setOrdinate(i, 0, segments.get(0).p0.x);
    seq.setOrdinate(i, 1, segments.get(0).p0.y);
    return factory.createLinearRing(seq);
}

private void computeMinDistance(LineString line, Point pt,
                                GeometryLocation[] locGeom) {
    if (line.getEnvelopeInternal().distance(pt.getEnvelopeInternal())
            > this.minDistance) {
        return;
    }
    Coordinate[] coord0 = line.getCoordinates();
    Coordinate coord = pt.getCoordinate();
    // brute force approach!
    for (int i = 0; i < coord0.length - 1; i++) {
        double dist = CGAlgorithms.distancePointLine(
                coord, coord0[i], coord0[i + 1]);
        if (dist < this.minDistance) {
            this.minDistance = dist;
            LineSegment seg = new LineSegment(coord0[i], coord0[i + 1]);
            Coordinate segClosestPoint = seg.closestPoint(coord);
            locGeom[0] = new GeometryLocation(line, i, segClosestPoint);
            locGeom[1] = new GeometryLocation(pt, 0, coord);
        }
        if (this.minDistance <= this.terminateDistance) {
            return;
        }
    }
}

private void computeMinDistanceLinePoint(LineString line, Point point,
                                         boolean flip) {
    Coordinate[] lineCoord = line.getCoordinates();
    Coordinate coord = point.getCoordinate();
    // brute force approach!
    for (int i = 0; i < lineCoord.length - 1; i++) {
        double dist = CGAlgorithms3D.distancePointSegment(coord, lineCoord[i],
                lineCoord[i + 1]);
        if (dist < this.minDistance) {
            LineSegment seg = new LineSegment(lineCoord[i], lineCoord[i + 1]);
            Coordinate segClosestPoint = seg.closestPoint(coord);
            this.updateDistance(dist,
                    new GeometryLocation(line, i, segClosestPoint),
                    new GeometryLocation(point, 0, coord),
                    flip);
        }
        if (this.isDone) {
            return;
        }
    }
}

private int findFurthestPoint(Coordinate[] pts, int i, int j, double[] maxDistance) {
    LineSegment seg = new LineSegment();
    seg.p0 = pts[i];
    seg.p1 = pts[j];
    double maxDist = -1.0;
    int maxIndex = i;
    for (int k = i + 1; k < j; k++) {
        Coordinate midPt = pts[k];
        double distance = seg.distance(midPt);
        if (distance > maxDist) {
            maxDist = distance;
            maxIndex = k;
        }
    }
    maxDistance[0] = maxDist;
    return maxIndex;
}

/**
 * Densifies a coordinate sequence.
 *
 * @param pts
 * @param distanceTolerance
 * @return the densified coordinate sequence
 */
private static Coordinate[] densifyPoints(Coordinate[] pts,
                                          double distanceTolerance, PrecisionModel precModel) {
    LineSegment seg = new LineSegment();
    CoordinateList coordList = new CoordinateList();
    for (int i = 0; i < pts.length - 1; i++) {
        seg.p0 = pts[i];
        seg.p1 = pts[i + 1];
        coordList.add(seg.p0, false);
        double len = seg.getLength();
        int densifiedSegCount = (int) (len / distanceTolerance) + 1;
        if (densifiedSegCount > 1) {
            double densifiedSegLen = len / densifiedSegCount;
            for (int j = 1; j < densifiedSegCount; j++) {
                double segFract = (j * densifiedSegLen) / len;
                Coordinate p = seg.pointAlong(segFract);
                precModel.makePrecise(p);
                coordList.add(p, false);
            }
        }
    }
    coordList.add(pts[pts.length - 1], false);
    return coordList.toCoordinateArray();
}

/**
 * A basic strategy for finding split points when nothing extra is known about the geometry of
 * the situation.
 *
 * @param seg the encroached segment
 * @param encroachPt the encroaching point
 * @return the point at which to split the encroached segment
 */
@Override
public Coordinate findSplitPoint(Segment seg, Coordinate encroachPt) {
    LineSegment lineSeg = seg.getLineSegment();
    double segLen = lineSeg.getLength();
    double midPtLen = segLen / 2;
    SplitSegment splitSeg = new SplitSegment(lineSeg);

    Coordinate projPt = projectedSplitPoint(seg, encroachPt);
    /**
     * Compute the largest diameter (length) that will produce a split segment which is not
     * still encroached upon by the encroaching point (The length is reduced slightly by a
     * safety factor)
     */
    double nonEncroachDiam = projPt.distance(encroachPt) * 2 * 0.8; // .99;
    double maxSplitLen = nonEncroachDiam;
    if (maxSplitLen > midPtLen) {
        maxSplitLen = midPtLen;
    }
    splitSeg.setMinimumLength(maxSplitLen);

    splitSeg.splitAt(projPt);

    return splitSeg.getSplitPoint();
}

private int findMaxPerpDistance(Coordinate[] pts, LineSegment seg, int startIndex) {
        double maxPerpDistance = seg.distancePerpendicular(pts[startIndex]);
        double nextPerpDistance = maxPerpDistance;
        int maxIndex = startIndex;
        int nextIndex = maxIndex;
        while (nextPerpDistance >= maxPerpDistance) {
            maxPerpDistance = nextPerpDistance;
            maxIndex = nextIndex;

            nextIndex = nextIndex(pts, maxIndex);
            nextPerpDistance = seg.distancePerpendicular(pts[nextIndex]);
        }
        // found maximum width for this segment - update global min dist if appropriate
        if (maxPerpDistance < this.minWidth) {
            this.minPtIndex = maxIndex;
            this.minWidth = maxPerpDistance;
            this.minWidthPt = pts[this.minPtIndex];
            this.minBaseSeg = new LineSegment(seg);
//      System.out.println(minBaseSeg);
//      System.out.println(minWidth);
        }
        return maxIndex;
    }

private static LineSegment computeSegmentForLine(double a, double b, double c) {
    Coordinate p0;
    Coordinate p1;
/*
* Line eqn is ax + by = c
* Slope is a/b.
* If slope is steep, use y values as the inputs
*/
    if (Math.abs(b) > Math.abs(a)) {
        p0 = new Coordinate(0.0, c / b);
        p1 = new Coordinate(1.0, c / b - a / b);
    } else {
        p0 = new Coordinate(c / a, 0.0);
        p1 = new Coordinate(c / a - b / a, 1.0);
    }
    return new LineSegment(p0, p1);
}

private double indexOfFromStart(Coordinate inputPt, double minIndex) {
    double minDistance = Double.MAX_VALUE;

    double ptMeasure = minIndex;
    double segmentStartMeasure = 0.0;
    LineSegment seg = new LineSegment();
    LinearIterator it = new LinearIterator(this.linearGeom);
    while (it.hasNext()) {
        if (!it.isEndOfLine()) {
            seg.p0 = it.getSegmentStart();
            seg.p1 = it.getSegmentEnd();
            double segDistance = seg.distance(inputPt);
            double segMeasureToPt = this.segmentNearestMeasure(seg, inputPt, segmentStartMeasure);
            if (segDistance < minDistance
                    && segMeasureToPt > minIndex) {
                ptMeasure = segMeasureToPt;
                minDistance = segDistance;
            }
            segmentStartMeasure += seg.getLength();
        }
        it.next();
    }
    return ptMeasure;
}

/**
 * Checks if the point is located on the given {@link LineSegment} (including endpoints).
 */
public static boolean isPointOnLineSegment(Coordinate point, LineSegment line) {
    double lengthOfLine = line.getLength();
    double distFromEnd1 = point.distance(line.p0);
    double distFromEnd2 = point.distance(line.p1);

    // this seems to handle robustness errors (due to rounding) better
    if (distFromEnd1 + distFromEnd2 == lengthOfLine) {
        return true;
    }

    // Fallback to what should probably be the robust implementation (TODO: investigate precision issues)
    LineIntersector lineIntersector = new RobustLineIntersector();
    lineIntersector.computeIntersection(point, line.p0, line.p1);
    return lineIntersector.hasIntersection();
}

public EdgePair(LineSegment edgeA, LineSegment edgeB) {
    // determine the point where the edges would intersect if they were infinite lines
    IntersectionCoordinate intersectionPoint = GeometryUtils.getIntersectionPoint(edgeA, edgeB);

    this.edgeA = edgeA;
    this.edgeB = edgeB;

    // there will be 2 projected points at most
    projected0 = getProjectedVertex(edgeA.p1, edgeB, intersectionPoint);
    if (projected0.isNotValid()) {
        projected0 = getProjectedVertex(edgeB.p0, edgeA, intersectionPoint);
    }
    projected1 = getProjectedVertex(edgeB.p1, edgeA, intersectionPoint);
    if (projected1.isNotValid()) {
        projected1 = getProjectedVertex(edgeA.p0, edgeB, intersectionPoint);
    }
}

private EdgePairSubpolygons(LineSegment edgeA, LineSegment edgeB, ProjectedVertex projected0, ProjectedVertex projected1) {
    this.edgeA = Objects.requireNonNull(edgeA, "Edge A is required");
    this.edgeB = Objects.requireNonNull(edgeB, "Edge B is required");

    // build triangles if corresponding projected points are valid
    triangle1 = projected0.isValid() ? GeometryFactoryUtils.createTriangle(edgeA.p1, projected0, edgeB.p0) : null;
    triangle2 = projected1.isValid() ? GeometryFactoryUtils.createTriangle(edgeA.p0, projected1, edgeB.p1) : null;
    triangle1Area = triangle1 != null ? triangle1.getArea() : 0;
    triangle2Area = triangle2 != null ? triangle2.getArea() : 0;

    // build a trapezoid:
    // 1) if projected1 is on edgeA, add projected1, else add edgeA.p0
    // 2) if projected0 is on edgeA, add projected0, else add edgeA.p1
    // 3) if projected0 is on edgeB, add projected0, else add edgeB.p0
    // 4) if projected1 is on edgeB, add projected1, else add edgeB.p1
    // 5) close the polygon
    Coordinate coord1 = projected1.isOnEdge(edgeA) ? projected1 : edgeA.p0;
    Coordinate coord2 = projected0.isOnEdge(edgeA) ? projected0 : edgeA.p1;
    Coordinate coord3 = projected0.isOnEdge(edgeB) ? projected0 : edgeB.p0;
    Coordinate coord4 = projected1.isOnEdge(edgeB) ? projected1 : edgeB.p1;
    trapezoid = GeometryFactoryUtils.createPolygon(coord1, coord2, coord3, coord4);
    trapezoidArea = trapezoid.getArea();
}

@Test
public void projectionForEdgesFormingATrapezoid() throws Exception {
    LineSegment edgeA = new LineSegment(new Coordinate(0, 0), new Coordinate(10, 0));       // horizontal edge at y = 0, when x = [0; 10]
    LineSegment edgeB = new LineSegment(new Coordinate(5, 1), new Coordinate(15, 1));       // horizontal edge at y = 1, when x = [5; 15]

    Coordinate projectedPoint = GeometryUtils.getProjectedPoint(edgeB.p0, edgeA, null);     // project point (5; 1) onto y = 0
    assertEquals(5, projectedPoint.x, EXACT_PRECISION);
    assertEquals(0, projectedPoint.y, EXACT_PRECISION);
    projectedPoint = GeometryUtils.getProjectedPoint(edgeB.p1, edgeA, null);                // project point (15; 1) onto y = 0
    assertNull(projectedPoint);

    projectedPoint = GeometryUtils.getProjectedPoint(edgeA.p0, edgeB, null);                // project point (0; 0) onto y = 1
    assertNull(projectedPoint);
    projectedPoint = GeometryUtils.getProjectedPoint(edgeA.p1, edgeB, null);                // project point (10; 0) onto y = 1
    assertEquals(10, projectedPoint.x, EXACT_PRECISION);
    assertEquals(1, projectedPoint.y, EXACT_PRECISION);
}

@Test
public void projectionForPerpendicularEdges() throws Exception {
    LineSegment edgeA = new LineSegment(new Coordinate(0, 1), new Coordinate(0, 10));       // vertical   edge at x = 0, when y = [1; 10]
    LineSegment edgeB = new LineSegment(new Coordinate(2, 0), new Coordinate(7, 0));        // horizontal edge at y = 0, when x = [2; 7]

    IntersectionCoordinate intersection = new IntersectionCoordinate(0, 0, edgeA, edgeB);

    Coordinate projectedPoint = GeometryUtils.getProjectedPoint(edgeB.p0, edgeA, intersection);     // project point (2; 0) onto y axis
    assertEquals(0, projectedPoint.x, EXACT_PRECISION);
    assertEquals(2, projectedPoint.y, EXACT_PRECISION);
    projectedPoint = GeometryUtils.getProjectedPoint(edgeB.p1, edgeA, intersection);                // project point (7; 0) onto y axis
    assertEquals(0, projectedPoint.x, EXACT_PRECISION);
    assertEquals(7, projectedPoint.y, EXACT_PRECISION);

    projectedPoint = GeometryUtils.getProjectedPoint(edgeA.p0, edgeB, intersection);                // project point (0; 1) onto x axis
    assertNull(projectedPoint);
    projectedPoint = GeometryUtils.getProjectedPoint(edgeA.p1, edgeB, intersection);                // project point (0; 10) onto x axis
    assertNull(projectedPoint);
}

@Test
public void projectionForIntersectingEdges() throws Exception {
    LineSegment edgeA = new LineSegment(new Coordinate(0, 0), new Coordinate(0, 40));       // vertical edge at x = 0, when y = [0; 40]
    LineSegment edgeB = new LineSegment(new Coordinate(30, 10), new Coordinate(10, 20));    // sloping edge that would intersect edgeA if extended

    IntersectionCoordinate intersection = new IntersectionCoordinate(0, 25, edgeA, edgeB);

    Coordinate projectedPoint = GeometryUtils.getProjectedPoint(edgeB.p0, edgeA, intersection);     // project point (30; 10) onto vertical edge
    assertNull(projectedPoint);

    projectedPoint = GeometryUtils.getProjectedPoint(edgeB.p1, edgeA, intersection);                // project point (10; 20) onto vertical edge
    assertEquals(0, projectedPoint.x, EXACT_PRECISION);
    assertEquals(13.819660112501051, projectedPoint.y, EXACT_PRECISION);

    projectedPoint = GeometryUtils.getProjectedPoint(edgeA.p0, edgeB, intersection);                // project point (0; 0) onto sloping edge
    assertEquals(22.360679774997898, projectedPoint.x, EXACT_PRECISION);
    assertEquals(13.819660112501051, projectedPoint.y, EXACT_PRECISION);

    projectedPoint = GeometryUtils.getProjectedPoint(edgeA.p1, edgeB, intersection);                // project point (0; 20) onto sloping edge
    assertNull(projectedPoint);
}

@Test
public void projectionForPerpendicularIntersectingEdges() throws Exception {
    LineSegment edgeA = new LineSegment(new Coordinate(0, 0), new Coordinate(0, 20));               // vertical   edge at x = 0, when y = [0; 20]
    LineSegment edgeB = new LineSegment(new Coordinate(5, 10), new Coordinate(15, 10));             // horizontal edge at y = 10 when x = [5; 15]

    IntersectionCoordinate intersection = new IntersectionCoordinate(0, 10, edgeA, edgeB);

    Coordinate projectedPoint = GeometryUtils.getProjectedPoint(edgeB.p0, edgeA, intersection);     // project point (5; 10) onto vertical edge
    assertEquals(0, projectedPoint.x, EXACT_PRECISION);
    assertEquals(15, projectedPoint.y, EXACT_PRECISION);

    projectedPoint = GeometryUtils.getProjectedPoint(edgeB.p1, edgeA, intersection);                // project point (15; 10) onto vertical edge
    assertNull(projectedPoint);

    projectedPoint = GeometryUtils.getProjectedPoint(edgeA.p0, edgeB, intersection);                // project point (0; 0) onto horizontal edge
    assertNull(projectedPoint);

    // TODO: need to handle this better
    projectedPoint = GeometryUtils.getProjectedPoint(edgeA.p1, edgeB, intersection);                // project point (0; 20) onto horizontal edge
    assertEquals(10, projectedPoint.x, EXACT_PRECISION);
    assertEquals(10, projectedPoint.y, EXACT_PRECISION);
}

@Test
public void testGetLineSegment() throws Exception {
    LineString string = (LineString) new WKTReader().read("LINESTRING(0 1, 2 3, 4 5, 6 7)");

    LineSegment result = GeometryUtils.getLineSegment(string, 0);
    assertEquals(0, result.p0.x, EXACT_PRECISION);
    assertEquals(1, result.p0.y, EXACT_PRECISION);
    assertEquals(2, result.p1.x, EXACT_PRECISION);
    assertEquals(3, result.p1.y, EXACT_PRECISION);

    result = GeometryUtils.getLineSegment(string, 1);
    assertEquals(2, result.p0.x, EXACT_PRECISION);
    assertEquals(3, result.p0.y, EXACT_PRECISION);
    assertEquals(4, result.p1.x, EXACT_PRECISION);
    assertEquals(5, result.p1.y, EXACT_PRECISION);
}

@Test
public void includingEndpoints() throws Exception {
    Coordinate startPoint = new Coordinate(0, 0);
    Coordinate endPoint = new Coordinate(100, 200);
    LineSegment line = new LineSegment(startPoint, endPoint);

    Coordinate pointOnLine = new Coordinate(20, 40);
    Coordinate pointOnExtendedLine = new Coordinate(120, 140);
    Coordinate pointAdjacentToLine = new Coordinate(21, 40);

    assertTrue(GeometryUtils.isPointOnLineSegment(startPoint, line));
    assertTrue(GeometryUtils.isPointOnLineSegment(endPoint, line));
    assertTrue(GeometryUtils.isPointOnLineSegment(pointOnLine, line));

    assertFalse(GeometryUtils.isPointOnLineSegment(pointOnExtendedLine, line));
    assertFalse(GeometryUtils.isPointOnLineSegment(pointAdjacentToLine, line));
}

@Test
public void excludingEndpoints() throws Exception {
    Coordinate startPoint = new Coordinate(0, 0);
    Coordinate endPoint = new Coordinate(100, 200);
    LineSegment line = new LineSegment(startPoint, endPoint);

    Coordinate pointOnLine = new Coordinate(20, 40);
    Coordinate pointOnExtendedLine = new Coordinate(120, 140);
    Coordinate pointAdjacentToLine = new Coordinate(21, 40);

    assertFalse(GeometryUtils.isPointOnLineSegmentExcludingEndpoints(startPoint, line));
    assertFalse(GeometryUtils.isPointOnLineSegmentExcludingEndpoints(endPoint, line));
    assertTrue(GeometryUtils.isPointOnLineSegmentExcludingEndpoints(pointOnLine, line));

    assertFalse(GeometryUtils.isPointOnLineSegmentExcludingEndpoints(pointOnExtendedLine, line));
    assertFalse(GeometryUtils.isPointOnLineSegmentExcludingEndpoints(pointAdjacentToLine, line));
}

@Test
public void rectangleCase() throws Exception {
    // Rectangle: (0; 0), (10; 5)
    LineSegment edgeA = new LineSegment(10, 5, 0, 5);      // horizontal line at y = 5, when x = [0; 10]
    LineSegment edgeB = new LineSegment(0, 0, 10, 0);      // horizontal line at y = 0, when x = [0; 10]

    EdgePair edgePair = new EdgePair(edgeA, edgeB);
    EdgePairSubpolygons subpolygons = edgePair.getSubpolygons();

    assertNull(subpolygons.getTriangle1());
    assertNull(subpolygons.getTriangle2());

    // check total area
    Polygon expectedPolygon = GeometryFactoryUtils.createPolygon(new Coordinate(0, 5), new Coordinate(10, 5), new Coordinate(10, 0), new Coordinate(0, 0));
    assertEquals(expectedPolygon.getArea(), subpolygons.getTotalArea(), EXACT_PRECISION);
    assertTrue(subpolygons.getTrapezoid().isRectangle());
}

@Test
public void testFreakishCase() throws Exception {
    // This case is based on a polygon discovered while debugging
    // "POLYGON ((63.8888370007869 -7.22223259984262, 50 -10, 0 0, 10 50, 50 60, 90 50, 65.39686394227257 56.15078401443185, 63.8888370007869 -7.22223259984262))"
    // Simplified version:
    // "POLYGON ((65.39686394227257 45, 10 45, 10 50, 50 60, 90 50, 65.39686394227257 56.15078401443185, 65.39686394227257 45))"

    LineSegment edgeA = new LineSegment(new Coordinate(10, 50), new Coordinate(50, 60));
    LineSegment edgeB = new LineSegment(new Coordinate(90, 50), new Coordinate(65.39686394227257, 56.15078401443185));

    EdgePair edgePair = new EdgePair(edgeA, edgeB);
    EdgePairSubpolygons subpolygons = edgePair.getSubpolygons();

    // TOOD:
    assertNotNull(subpolygons.getTriangle1());
    assertNotNull(subpolygons.getTriangle2());
    assertNotNull(subpolygons.getTrapezoid());
}

private int findFurthestPoint(Coordinate[] pts, int i, int j, double[] maxDistance) {
    LineSegment seg = new LineSegment();
    seg.p0 = pts[i];
    seg.p1 = pts[j];
    double maxDist = -1.0;
    int maxIndex = i;
    for (int k = i + 1; k < j; k++) {
        Coordinate midPt = pts[k];
        double distance = seg.distance(midPt);
        if (distance > maxDist) {
            maxDist = distance;
            maxIndex = k;
        }
    }
    maxDistance[0] = maxDist;
    return maxIndex;
}

/**
 * A basic strategy for finding split points when nothing extra is known about the geometry of
 * the situation.
 *
 * @param seg        the encroached segment
 * @param encroachPt the encroaching point
 * @return the point at which to split the encroached segment
 */
public Coordinate findSplitPoint(Segment seg, Coordinate encroachPt) {
    LineSegment lineSeg = seg.getLineSegment();
    double segLen = lineSeg.getLength();
    double midPtLen = segLen / 2;
    SplitSegment splitSeg = new SplitSegment(lineSeg);

    Coordinate projPt = projectedSplitPoint(seg, encroachPt);
    /**
     * Compute the largest diameter (length) that will produce a split segment which is not
     * still encroached upon by the encroaching point (The length is reduced slightly by a
     * safety factor)
     */
    double nonEncroachDiam = projPt.distance(encroachPt) * 2 * 0.8; // .99;
    double maxSplitLen = nonEncroachDiam;
    if (maxSplitLen > midPtLen) {
        maxSplitLen = midPtLen;
    }
    splitSeg.setMinimumLength(maxSplitLen);

    splitSeg.splitAt(projPt);

    return splitSeg.getSplitPoint();
}

private double indexOfFromStart(Coordinate inputPt, double minIndex) {
    double minDistance = Double.MAX_VALUE;

    double ptMeasure = minIndex;
    double segmentStartMeasure = 0.0;
    LineSegment seg = new LineSegment();
    LinearIterator it = new LinearIterator(linearGeom);
    while (it.hasNext()) {
        if (!it.isEndOfLine()) {
            seg.p0 = it.getSegmentStart();
            seg.p1 = it.getSegmentEnd();
            double segDistance = seg.distance(inputPt);
            double segMeasureToPt = segmentNearestMeasure(seg, inputPt, segmentStartMeasure);
            if (segDistance < minDistance
                    && segMeasureToPt > minIndex) {
                ptMeasure = segMeasureToPt;
                minDistance = segDistance;
            }
            segmentStartMeasure += seg.getLength();
        }
        it.next();
    }
    return ptMeasure;
}

private void checkSegment(double x, double y)
{
  Coordinate seg0 = new Coordinate(0, 0);
  Coordinate seg1 = new Coordinate(x, y);
  LineSegment seg = new LineSegment(seg0, seg1);

  for (int i = 0; i < 4; i++) {
    double dist = i;

    double gridSize = 1 / pm.getScale();

    checkPointsAtDistance(seg, dist, dist + 1.0 * gridSize);
    checkPointsAtDistance(seg, dist, dist + 2.0 * gridSize);
    checkPointsAtDistance(seg, dist, dist + 3.0 * gridSize);
    checkPointsAtDistance(seg, dist, dist + 4.0 * gridSize);
  }
}

/**
 * A basic strategy for finding split points when nothing extra is known about the geometry of
 * the situation.
 * 
 * @param seg the encroached segment
 * @param encroachPt the encroaching point
 * @return the point at which to split the encroached segment
 */
public Coordinate findSplitPoint(Segment seg, Coordinate encroachPt) {
    LineSegment lineSeg = seg.getLineSegment();
    double segLen = lineSeg.getLength();
    double midPtLen = segLen / 2;
    SplitSegment splitSeg = new SplitSegment(lineSeg);

    Coordinate projPt = projectedSplitPoint(seg, encroachPt);
    /**
     * Compute the largest diameter (length) that will produce a split segment which is not
     * still encroached upon by the encroaching point (The length is reduced slightly by a
     * safety factor)
     */
    double nonEncroachDiam = projPt.distance(encroachPt) * 2 * 0.8; // .99;
    double maxSplitLen = nonEncroachDiam;
    if (maxSplitLen > midPtLen) {
        maxSplitLen = midPtLen;
    }
    splitSeg.setMinimumLength(maxSplitLen);

    splitSeg.splitAt(projPt);

    return splitSeg.getSplitPoint();
}

private void computeMinDistanceLineLine(LineString line0, LineString line1,
        boolean flip) {
    Coordinate[] coord0 = line0.getCoordinates();
    Coordinate[] coord1 = line1.getCoordinates();
    // brute force approach!
    for (int i = 0; i < coord0.length - 1; i++) {
        for (int j = 0; j < coord1.length - 1; j++) {
            double dist = CGAlgorithms3D.distanceSegmentSegment(coord0[i],
                    coord0[i + 1], coord1[j], coord1[j + 1]);
            if (dist < minDistance) {
                minDistance = dist;
                // TODO: compute closest pts in 3D
                LineSegment seg0 = new LineSegment(coord0[i], coord0[i + 1]);
                LineSegment seg1 = new LineSegment(coord1[j], coord1[j + 1]);
                Coordinate[] closestPt = seg0.closestPoints(seg1);
                updateDistance(dist,
                        new GeometryLocation(line0, i, closestPt[0]),
                        new GeometryLocation(line1, j, closestPt[1]),
                        flip
                );
            }
            if (isDone) return;
        }
    }
}

private void computeMinDistanceLinePoint(LineString line,Point point, 
        boolean flip) {
    Coordinate[] lineCoord = line.getCoordinates();
    Coordinate coord = point.getCoordinate();
    // brute force approach!
    for (int i = 0; i < lineCoord.length - 1; i++) {
        double dist = CGAlgorithms3D.distancePointSegment(coord, lineCoord[i],
                lineCoord[i + 1]);
        if (dist < minDistance) {
            LineSegment seg = new LineSegment(lineCoord[i], lineCoord[i + 1]);
            Coordinate segClosestPoint = seg.closestPoint(coord);
            updateDistance(dist,
                    new GeometryLocation(line, i, segClosestPoint),
                    new GeometryLocation(point, 0, coord),
                    flip);
        }
        if (isDone) return;
    }
}

/**
 * A basic strategy for finding split points when nothing extra is known about the geometry of
 * the situation.
 * 
 * @param seg the encroached segment
 * @param encroachPt the encroaching point
 * @return the point at which to split the encroached segment
 */
public Coordinate findSplitPoint(Segment seg, Coordinate encroachPt) {
    LineSegment lineSeg = seg.getLineSegment();
    double segLen = lineSeg.getLength();
    double midPtLen = segLen / 2;
    SplitSegment splitSeg = new SplitSegment(lineSeg);

    Coordinate projPt = projectedSplitPoint(seg, encroachPt);
    /**
     * Compute the largest diameter (length) that will produce a split segment which is not
     * still encroached upon by the encroaching point (The length is reduced slightly by a
     * safety factor)
     */
    double nonEncroachDiam = projPt.distance(encroachPt) * 2 * 0.8; // .99;
    double maxSplitLen = nonEncroachDiam;
    if (maxSplitLen > midPtLen) {
        maxSplitLen = midPtLen;
    }
    splitSeg.setMinimumLength(maxSplitLen);

    splitSeg.splitAt(projPt);

    return splitSeg.getSplitPoint();
}

public static Rectangle bbox(LineSegment segment) {
    Coordinate p = segment.p0;
    Coordinate q = segment.p1;
    double minX = p.x < q.x ? p.x : q.x;
    double maxX = p.x > q.x ? p.x : q.x;
    double minY = p.y < q.y ? p.y : q.y;
    double maxY = p.y > q.y ? p.y : q.y;
    return new Rectangle((float) minX, (float) minY, (float) maxX,
            (float) maxY);
}

/**
 * Compute an offset segment for an input segment on a given side and at a given distance.
 * The offset points are computed in full double precision, for accuracy.
 *
 * @param seg the segment to offset
 * @param side the side of the segment ({@link Position}) the offset lies on
 * @param distance the offset distance
 * @param offset the points computed for the offset segment
 */
private void computeOffsetSegment(LineSegment seg, int side, double distance, LineSegment offset) {
    int sideSign = side == Position.LEFT ? 1 : -1;
    double dx = seg.p1.x - seg.p0.x;
    double dy = seg.p1.y - seg.p0.y;
    double len = Math.sqrt(dx * dx + dy * dy);
    // u is the vector that is the length of the offset, in the direction of the segment
    double ux = sideSign * distance * dx / len;
    double uy = sideSign * distance * dy / len;
    offset.p0.x = seg.p0.x - uy;
    offset.p0.y = seg.p0.y + ux;
    offset.p1.x = seg.p1.x - uy;
    offset.p1.y = seg.p1.y + ux;
}

/**
     * Adds a mitre join connecting the two reflex offset segments.
     * The mitre will be beveled if it exceeds the mitre ratio limit.
     *
     * @param offset0 the first offset segment
     * @param offset1 the second offset segment
     * @param distance the offset distance
     */
    private void addMitreJoin(Coordinate p,
                              LineSegment offset0,
                              LineSegment offset1,
                              double distance) {
        boolean isMitreWithinLimit = true;
        Coordinate intPt = null;

        /**
         * This computation is unstable if the offset segments are nearly collinear.
         * Howver, this situation should have been eliminated earlier by the check for
         * whether the offset segment endpoints are almost coincident
         */
        try {
            intPt = HCoordinate.intersection(offset0.p0,
                    offset0.p1, offset1.p0, offset1.p1);

            double mitreRatio = distance <= 0.0 ? 1.0
                    : intPt.distance(p) / Math.abs(distance);

            if (mitreRatio > this.bufParams.getMitreLimit()) {
                isMitreWithinLimit = false;
            }
        } catch (NotRepresentableException ex) {
            intPt = new Coordinate(0, 0);
            isMitreWithinLimit = false;
        }

        if (isMitreWithinLimit) {
            this.segList.addPt(intPt);
        } else {
            this.addLimitedMitreJoin(offset0, offset1, distance, this.bufParams.getMitreLimit());
//      addBevelJoin(offset0, offset1);
        }
    }

private void computeMinDistance(LineString line0, LineString line1,
                                GeometryLocation[] locGeom) {
    if (line0.getEnvelopeInternal().distance(line1.getEnvelopeInternal())
            > this.minDistance) {
        return;
    }
    Coordinate[] coord0 = line0.getCoordinates();
    Coordinate[] coord1 = line1.getCoordinates();
    // brute force approach!
    for (int i = 0; i < coord0.length - 1; i++) {
        for (int j = 0; j < coord1.length - 1; j++) {
            double dist = CGAlgorithms.distanceLineLine(
                    coord0[i], coord0[i + 1],
                    coord1[j], coord1[j + 1]);
            if (dist < this.minDistance) {
                this.minDistance = dist;
                LineSegment seg0 = new LineSegment(coord0[i], coord0[i + 1]);
                LineSegment seg1 = new LineSegment(coord1[j], coord1[j + 1]);
                Coordinate[] closestPt = seg0.closestPoints(seg1);
                locGeom[0] = new GeometryLocation(line0, i, closestPt[0]);
                locGeom[1] = new GeometryLocation(line1, j, closestPt[1]);
            }
            if (this.minDistance <= this.terminateDistance) {
                return;
            }
        }
    }
}

private void computeMinDistanceLineLine(LineString line0, LineString line1,
                                        boolean flip) {
    Coordinate[] coord0 = line0.getCoordinates();
    Coordinate[] coord1 = line1.getCoordinates();
    // brute force approach!
    for (int i = 0; i < coord0.length - 1; i++) {
        for (int j = 0; j < coord1.length - 1; j++) {
            double dist = CGAlgorithms3D.distanceSegmentSegment(coord0[i],
                    coord0[i + 1], coord1[j], coord1[j + 1]);
            if (dist < this.minDistance) {
                this.minDistance = dist;
                // TODO: compute closest pts in 3D
                LineSegment seg0 = new LineSegment(coord0[i], coord0[i + 1]);
                LineSegment seg1 = new LineSegment(coord1[j], coord1[j + 1]);
                Coordinate[] closestPt = seg0.closestPoints(seg1);
                this.updateDistance(dist,
                        new GeometryLocation(line0, i, closestPt[0]),
                        new GeometryLocation(line1, j, closestPt[1]),
                        flip
                );
            }
            if (this.isDone) {
                return;
            }
        }
    }
}

private LineSegment flatten(int start, int end) {
        // make a new segment for the simplified geometry
        Coordinate p0 = this.linePts[start];
        Coordinate p1 = this.linePts[end];
        LineSegment newSeg = new LineSegment(p0, p1);
// update the indexes
        this.remove(this.line, start, end);
        this.outputIndex.add(newSeg);
        return newSeg;
    }

private boolean hasBadIntersection(TaggedLineString parentLine,
                                   int[] sectionIndex,
                                   LineSegment candidateSeg) {
    if (this.hasBadOutputIntersection(candidateSeg)) {
        return true;
    }
    return hasBadInputIntersection(parentLine, sectionIndex, candidateSeg);
}

private boolean hasBadOutputIntersection(LineSegment candidateSeg) {
    List querySegs = this.outputIndex.query(candidateSeg);
    for (Object querySeg1 : querySegs) {
        LineSegment querySeg = (LineSegment) querySeg1;
        if (this.hasInteriorIntersection(querySeg, candidateSeg)) {
            return true;
        }
    }
    return false;
}

private boolean hasBadInputIntersection(TaggedLineString parentLine,
                                        int[] sectionIndex,
                                        LineSegment candidateSeg) {
    List querySegs = this.inputIndex.query(candidateSeg);
    for (Object querySeg1 : querySegs) {
        TaggedLineSegment querySeg = (TaggedLineSegment) querySeg1;
        if (this.hasInteriorIntersection(querySeg, candidateSeg)) {
            if (isInLineSection(parentLine, sectionIndex, querySeg)) {
                continue;
            }
            return true;
        }
    }
    return false;
}

public List query(LineSegment querySeg) {
        Envelope env = new Envelope(querySeg.p0, querySeg.p1);

        LineSegmentVisitor visitor = new LineSegmentVisitor(querySeg);
        this.index.query(env, visitor);
        List itemsFound = visitor.getItems();

//    List listQueryItems = index.query(env);
//    System.out.println("visitor size = " + itemsFound.size()
//                       + "  query size = " + listQueryItems.size());
//    List itemsFound = index.query(env);

        return itemsFound;
    }

@Override
public void visitItem(Object item) {
    LineSegment seg = (LineSegment) item;
    if (Envelope.intersects(seg.p0, seg.p1, this.querySeg.p0, this.querySeg.p1)) {
        this.items.add(item);
    }
}