/** * Add a {@link LineString} forming an edge of the polygon graph. * * @param line the line to add */ public void addEdge(LineString line) { if (line.isEmpty()) { return; } Coordinate[] linePts = CoordinateArrays.removeRepeatedPoints(line.getCoordinates()); if (linePts.length < 2) { return; } Coordinate startPt = linePts[0]; Coordinate endPt = linePts[linePts.length - 1]; Node nStart = this.getNode(startPt); Node nEnd = this.getNode(endPt); DirectedEdge de0 = new PolygonizeDirectedEdge(nStart, nEnd, linePts[1], true); DirectedEdge de1 = new PolygonizeDirectedEdge(nEnd, nStart, linePts[linePts.length - 2], false); Edge edge = new PolygonizeEdge(line); edge.setDirectedEdges(de0, de1); this.add(edge); }
private Coordinate[] getCoordinates() { if (this.coordinates == null) { int forwardDirectedEdges = 0; int reverseDirectedEdges = 0; CoordinateList coordinateList = new CoordinateList(); for (Object directedEdge1 : directedEdges) { LineMergeDirectedEdge directedEdge = (LineMergeDirectedEdge) directedEdge1; if (directedEdge.getEdgeDirection()) { forwardDirectedEdges++; } else { reverseDirectedEdges++; } coordinateList.add(((LineMergeEdge) directedEdge.getEdge()).getLine() .getCoordinates(), false, directedEdge.getEdgeDirection()); } this.coordinates = coordinateList.toCoordinateArray(); if (reverseDirectedEdges > forwardDirectedEdges) { CoordinateArrays.reverse(this.coordinates); } } return this.coordinates; }
/** * Adds an Edge, DirectedEdges, and Nodes for the given LineString representation * of an edge. * Empty lines or lines with all coordinates equal are not added. * * @param lineString the linestring to add to the graph */ public void addEdge(LineString lineString) { if (lineString.isEmpty()) { return; } Coordinate[] coordinates = CoordinateArrays.removeRepeatedPoints(lineString.getCoordinates()); // don't add lines with all coordinates equal if (coordinates.length <= 1) { return; } Coordinate startCoordinate = coordinates[0]; Coordinate endCoordinate = coordinates[coordinates.length - 1]; Node startNode = this.getNode(startCoordinate); Node endNode = this.getNode(endCoordinate); DirectedEdge directedEdge0 = new LineMergeDirectedEdge(startNode, endNode, coordinates[1], true); DirectedEdge directedEdge1 = new LineMergeDirectedEdge(endNode, startNode, coordinates[coordinates.length - 2], false); Edge edge = new LineMergeEdge(lineString); edge.setDirectedEdges(directedEdge0, directedEdge1); this.add(edge); }
public Coordinate[] getOffsetCurve(Coordinate[] inputPts, double distance) { this.distance = distance; // a zero width offset curve is empty if (distance == 0.0) { return null; } boolean isRightSide = distance < 0.0; double posDistance = Math.abs(distance); OffsetSegmentGenerator segGen = this.getSegGen(posDistance); if (inputPts.length <= 1) { this.computePointCurve(inputPts[0], segGen); } else { this.computeOffsetCurve(inputPts, isRightSide, segGen); } Coordinate[] curvePts = segGen.getCoordinates(); // for right side line is traversed in reverse direction, so have to reverse generated line if (isRightSide) { CoordinateArrays.reverse(curvePts); } return curvePts; }
private Coordinate[] computeBoundaryCoordinates(MultiLineString mLine) { List bdyPts = new ArrayList(); this.endpointMap = new TreeMap(); for (int i = 0; i < mLine.getNumGeometries(); i++) { LineString line = (LineString) mLine.getGeometryN(i); if (line.getNumPoints() == 0) { continue; } this.addEndpoint(line.getCoordinateN(0)); this.addEndpoint(line.getCoordinateN(line.getNumPoints() - 1)); } for (Object o : endpointMap.entrySet()) { Map.Entry entry = (Map.Entry) o; Counter counter = (Counter) entry.getValue(); int valence = counter.count; if (this.bnRule.isInBoundary(valence)) { bdyPts.add(entry.getKey()); } } return CoordinateArrays.toCoordinateArray(bdyPts); }
private void addLineString(LineString line) { Coordinate[] coord = CoordinateArrays.removeRepeatedPoints(line.getCoordinates()); if (coord.length < 2) { this.hasTooFewPoints = true; this.invalidPoint = coord[0]; return; } // add the edge for the LineString // line edges do not have locations for their left and right sides Edge e = new Edge(coord, new Label(this.argIndex, Location.INTERIOR)); this.lineEdgeMap.put(line, e); this.insertEdge(e); /** * Add the boundary points of the LineString, if any. * Even if the LineString is closed, add both points as if they were endpoints. * This allows for the case that the node already exists and is a boundary point. */ Assert.isTrue(coord.length >= 2, "found LineString with single point"); this.insertBoundaryPoint(this.argIndex, coord[0]); this.insertBoundaryPoint(this.argIndex, coord[coord.length - 1]); }
/** * Add a {@link LineString} forming an edge of the polygon graph. * * @param line the line to add */ public void addEdge(LineString line) { if (line.isEmpty()) { return; } Coordinate[] linePts = CoordinateArrays.removeRepeatedPoints(line.getCoordinates()); if (linePts.length < 2) { return; } Coordinate startPt = linePts[0]; Coordinate endPt = linePts[linePts.length - 1]; Node nStart = getNode(startPt); Node nEnd = getNode(endPt); DirectedEdge de0 = new PolygonizeDirectedEdge(nStart, nEnd, linePts[1], true); DirectedEdge de1 = new PolygonizeDirectedEdge(nEnd, nStart, linePts[linePts.length - 2], false); Edge edge = new PolygonizeEdge(line); edge.setDirectedEdges(de0, de1); add(edge); }
/** * Adds an Edge, DirectedEdges, and Nodes for the given LineString representation * of an edge. * Empty lines or lines with all coordinates equal are not added. * * @param lineString the linestring to add to the graph */ public void addEdge(LineString lineString) { if (lineString.isEmpty()) { return; } Coordinate[] coordinates = CoordinateArrays.removeRepeatedPoints(lineString.getCoordinates()); // don't add lines with all coordinates equal if (coordinates.length <= 1) return; Coordinate startCoordinate = coordinates[0]; Coordinate endCoordinate = coordinates[coordinates.length - 1]; Node startNode = getNode(startCoordinate); Node endNode = getNode(endCoordinate); DirectedEdge directedEdge0 = new LineMergeDirectedEdge(startNode, endNode, coordinates[1], true); DirectedEdge directedEdge1 = new LineMergeDirectedEdge(endNode, startNode, coordinates[coordinates.length - 2], false); Edge edge = new LineMergeEdge(lineString); edge.setDirectedEdges(directedEdge0, directedEdge1); add(edge); }
public Coordinate[] getOffsetCurve(Coordinate[] inputPts, double distance) { this.distance = distance; // a zero width offset curve is empty if (distance == 0.0) return null; boolean isRightSide = distance < 0.0; double posDistance = Math.abs(distance); OffsetSegmentGenerator segGen = getSegGen(posDistance); if (inputPts.length <= 1) { computePointCurve(inputPts[0], segGen); } else { computeOffsetCurve(inputPts, isRightSide, segGen); } Coordinate[] curvePts = segGen.getCoordinates(); // for right side line is traversed in reverse direction, so have to reverse generated line if (isRightSide) CoordinateArrays.reverse(curvePts); return curvePts; }
public Geometry union() { PointLocator locater = new PointLocator(); // use a set to eliminate duplicates, as required for union Set exteriorCoords = new TreeSet(); for (int i = 0; i < this.pointGeom.getNumGeometries(); i++) { Point point = (Point) this.pointGeom.getGeometryN(i); Coordinate coord = point.getCoordinate(); int loc = locater.locate(coord, this.otherGeom); if (loc == Location.EXTERIOR) { exteriorCoords.add(coord); } } // if no points are in exterior, return the other geom if (exteriorCoords.size() == 0) { return this.otherGeom; } // make a puntal geometry of appropriate size Geometry ptComp = null; Coordinate[] coords = CoordinateArrays.toCoordinateArray(exteriorCoords); if (coords.length == 1) { ptComp = this.geomFact.createPoint(coords[0]); } else { ptComp = this.geomFact.createMultiPoint(coords); } // add point component to the other geometry return GeometryCombiner.combine(ptComp, this.otherGeom); }
/** * Find the innermost enclosing shell EdgeRing containing the argument EdgeRing, if any. * The innermost enclosing ring is the <i>smallest</i> enclosing ring. * The algorithm used depends on the fact that: * <br> * ring A contains ring B iff envelope(ring A) contains envelope(ring B) * <br> * This routine is only safe to use if the chosen point of the hole * is known to be properly contained in a shell * (which is guaranteed to be the case if the hole does not touch its shell) * * @return containing EdgeRing, if there is one * or null if no containing EdgeRing is found */ public static EdgeRing findEdgeRingContaining(EdgeRing testEr, List shellList) { LinearRing testRing = testEr.getRing(); Envelope testEnv = testRing.getEnvelopeInternal(); Coordinate testPt = testRing.getCoordinateN(0); EdgeRing minShell = null; Envelope minShellEnv = null; for (Object aShellList : shellList) { EdgeRing tryShell = (EdgeRing) aShellList; LinearRing tryShellRing = tryShell.getRing(); Envelope tryShellEnv = tryShellRing.getEnvelopeInternal(); // the hole envelope cannot equal the shell envelope // (also guards against testing rings against themselves) if (tryShellEnv.equals(testEnv)) { continue; } // hole must be contained in shell if (!tryShellEnv.contains(testEnv)) { continue; } testPt = CoordinateArrays.ptNotInList(testRing.getCoordinates(), tryShellRing.getCoordinates()); boolean isContained = false; if (CGAlgorithms.isPointInRing(testPt, tryShellRing.getCoordinates())) { isContained = true; } // check if this new containing ring is smaller than the current minimum ring if (isContained) { if (minShell == null || minShellEnv.contains(tryShellEnv)) { minShell = tryShell; minShellEnv = minShell.getRing().getEnvelopeInternal(); } } } return minShell; }
private void addLineString(LineString line) { // a zero or negative width buffer of a line/point is empty if (this.distance <= 0.0 && !this.curveBuilder.getBufferParameters().isSingleSided()) { return; } Coordinate[] coord = CoordinateArrays.removeRepeatedPoints(line.getCoordinates()); Coordinate[] curve = this.curveBuilder.getLineCurve(coord, this.distance); this.addCurve(curve, Location.EXTERIOR, Location.INTERIOR); // TESTING //Coordinate[] curveTrim = BufferCurveLoopPruner.prune(curve); //addCurve(curveTrim, Location.EXTERIOR, Location.INTERIOR); }
private void buildIndex() { //Envelope env = ring.getEnvelopeInternal(); this.tree = new Bintree(); Coordinate[] pts = CoordinateArrays.removeRepeatedPoints(this.ring.getCoordinates()); List mcList = MonotoneChainBuilder.getChains(pts); for (Object aMcList : mcList) { MonotoneChain mc = (MonotoneChain) aMcList; Envelope mcEnv = mc.getEnvelope(); this.interval.min = mcEnv.getMinY(); this.interval.max = mcEnv.getMaxY(); this.tree.insert(this.interval, mc); } }
/** * Uses a heuristic to reduce the number of points scanned * to compute the hull. * The heuristic is to find a polygon guaranteed to * be in (or on) the hull, and eliminate all points inside it. * A quadrilateral defined by the extremal points * in the four orthogonal directions * can be used, but even more inclusive is * to use an octilateral defined by the points in the 8 cardinal directions. * <p> * Note that even if the method used to determine the polygon vertices * is not 100% robust, this does not affect the robustness of the convex hull. * <p> * To satisfy the requirements of the Graham Scan algorithm, * the returned array has at least 3 entries. * * @param pts the points to reduce * @return the reduced list of points (at least 3) */ private Coordinate[] reduce(Coordinate[] inputPts) { //Coordinate[] polyPts = computeQuad(inputPts); Coordinate[] polyPts = this.computeOctRing(inputPts); //Coordinate[] polyPts = null; // unable to compute interior polygon for some reason if (polyPts == null) { return inputPts; } // LinearRing ring = geomFactory.createLinearRing(polyPts); // System.out.println(ring); // add points defining polygon TreeSet reducedSet = new TreeSet(); Collections.addAll(reducedSet, polyPts); /** * Add all unique points not in the interior poly. * CGAlgorithms.isPointInRing is not defined for points actually on the ring, * but this doesn't matter since the points of the interior polygon * are forced to be in the reduced set. */ for (Coordinate inputPt : inputPts) { if (!CGAlgorithms.isPointInRing(inputPt, polyPts)) { reducedSet.add(inputPt); } } Coordinate[] reducedPts = CoordinateArrays.toCoordinateArray(reducedSet); // ensure that computed array has at least 3 points (not necessarily unique) if (reducedPts.length < 3) { return this.padArray3(reducedPts); } return reducedPts; }
/** * Dissolve the given {@link SegmentString}. * * @param segString the string to dissolve */ public void dissolve(SegmentString segString) { OrientedCoordinateArray oca = new OrientedCoordinateArray(segString.getCoordinates()); SegmentString existing = this.findMatching(oca, segString); if (existing == null) { this.add(oca, segString); } else { if (this.merger != null) { boolean isSameOrientation = CoordinateArrays.equals(existing.getCoordinates(), segString.getCoordinates()); this.merger.merge(existing, segString, isSameOrientation); } } }
private Coordinate[] scale(Coordinate[] pts) { Coordinate[] roundPts = new Coordinate[pts.length]; for (int i = 0; i < pts.length; i++) { roundPts[i] = new Coordinate( Math.round((pts[i].x - this.offsetX) * this.scaleFactor), Math.round((pts[i].y - this.offsetY) * this.scaleFactor), pts[i].z ); } Coordinate[] roundPtsNoDup = CoordinateArrays.removeRepeatedPoints(roundPts); return roundPtsNoDup; }
/** * Adds a polygon ring to the graph. * Empty rings are ignored. * <p> * The left and right topological location arguments assume that the ring is oriented CW. * If the ring is in the opposite orientation, * the left and right locations must be interchanged. */ private void addPolygonRing(LinearRing lr, int cwLeft, int cwRight) { // don't bother adding empty holes if (lr.isEmpty()) { return; } Coordinate[] coord = CoordinateArrays.removeRepeatedPoints(lr.getCoordinates()); if (coord.length < 4) { this.hasTooFewPoints = true; this.invalidPoint = coord[0]; return; } int left = cwLeft; int right = cwRight; if (CGAlgorithms.isCCW(coord)) { left = cwRight; right = cwLeft; } Edge e = new Edge(coord, new Label(this.argIndex, Location.BOUNDARY, left, right)); this.lineEdgeMap.put(lr, e); this.insertEdge(e); // insert the endpoint as a node, to mark that it is on the boundary this.insertPoint(this.argIndex, coord[0], Location.BOUNDARY); }
/** * Dissolve the given {@link SegmentString}. * * @param segString the string to dissolve */ public void dissolve(SegmentString segString) { OrientedCoordinateArray oca = new OrientedCoordinateArray(segString.getCoordinates()); SegmentString existing = findMatching(oca, segString); if (existing == null) { add(oca, segString); } else { if (merger != null) { boolean isSameOrientation = CoordinateArrays.equals(existing.getCoordinates(), segString.getCoordinates()); merger.merge(existing, segString, isSameOrientation); } } }
private Coordinate[] scale(Coordinate[] pts) { Coordinate[] roundPts = new Coordinate[pts.length]; for (int i = 0; i < pts.length; i++) { roundPts[i] = new Coordinate( Math.round((pts[i].x - offsetX) * scaleFactor), Math.round((pts[i].y - offsetY) * scaleFactor), pts[i].z ); } Coordinate[] roundPtsNoDup = CoordinateArrays.removeRepeatedPoints(roundPts); return roundPtsNoDup; }
public Object getResult() { if (fact == null) fact = GeomFunction.geomFactory; Coordinate[] coords = CoordinateArrays.toCoordinateArray(pts); ConvexHull convexHull = new ConvexHull(coords, fact); return convexHull.getConvexHull(); }
public Object getResult() { if (fact == null) fact = GeomFunction.geomFactory; return fact.createLineString( CoordinateArrays.toCoordinateArray(pts)); }
public static Geometry lineConnect(Geometry geom) { CoordinateList pts = new CoordinateList(); pts.add(geom.getCoordinates(), true); return geom.getFactory().createLineString( CoordinateArrays.toCoordinateArray(pts)); }
static Coordinate[] connectPts(Geometry geom, boolean close) { CoordinateList pts = new CoordinateList(); pts.add(geom.getCoordinates(), true); if (close) pts.closeRing(); return CoordinateArrays.toCoordinateArray(pts); }
public static Geometry lineConnectNoRepeated(Geometry geom) { CoordinateList pts = new CoordinateList(); pts.add(geom.getCoordinates(), false); return geom.getFactory().createLineString( CoordinateArrays.toCoordinateArray(pts)); }
private void addPolygon(Polygon p) { double offsetDistance = this.distance; int offsetSide = Position.LEFT; if (this.distance < 0.0) { offsetDistance = -this.distance; offsetSide = Position.RIGHT; } LinearRing shell = (LinearRing) p.getExteriorRing(); Coordinate[] shellCoord = CoordinateArrays.removeRepeatedPoints(shell.getCoordinates()); // optimization - don't bother computing buffer // if the polygon would be completely eroded if (this.distance < 0.0 && this.isErodedCompletely(shell, this.distance)) { return; } // don't attemtp to buffer a polygon with too few distinct vertices if (this.distance <= 0.0 && shellCoord.length < 3) { return; } this.addPolygonRing( shellCoord, offsetDistance, offsetSide, Location.EXTERIOR, Location.INTERIOR); for (int i = 0; i < p.getNumInteriorRing(); i++) { LinearRing hole = (LinearRing) p.getInteriorRingN(i); Coordinate[] holeCoord = CoordinateArrays.removeRepeatedPoints(hole.getCoordinates()); // optimization - don't bother computing buffer for this hole // if the hole would be completely covered if (this.distance > 0.0 && this.isErodedCompletely(hole, -this.distance)) { continue; } // Holes are topologically labelled opposite to the shell, since // the interior of the polygon lies on their opposite side // (on the left, if the hole is oriented CCW) this.addPolygonRing( holeCoord, offsetDistance, Position.opposite(offsetSide), Location.INTERIOR, Location.EXTERIOR); } }
public static CoordinateList unique(Coordinate[] coords) { Coordinate[] coordsCopy = CoordinateArrays.copyDeep(coords); Arrays.sort(coordsCopy); CoordinateList coordList = new CoordinateList(coordsCopy, false); return coordList; }
/** * Sets the sites (point or vertices) which will be diagrammed * from a collection of {@link Coordinate}s. * * @param coords a collection of Coordinates. */ public void setSites(Collection coords) { // remove any duplicate points (they will cause the triangulation to fail) this.siteCoords = DelaunayTriangulationBuilder.unique(CoordinateArrays.toCoordinateArray(coords)); }
/** * Sets the sites (vertices) which will be triangulated * from a collection of {@link Coordinate}s. * * @param coords a collection of Coordinates. */ public void setSites(Collection coords) { // remove any duplicate points (they will cause the triangulation to fail) this.siteCoords = unique(CoordinateArrays.toCoordinateArray(coords)); }
/** * Computes the canonical orientation for a coordinate array. * * @param pts the array to test * @return <code>true</code> if the points are oriented forwards * or <code>false</code if the points are oriented in reverse */ private static boolean orientation(Coordinate[] pts) { return CoordinateArrays.increasingDirection(pts) == 1; }
