/** * Isolated nodes are nodes whose labels are incomplete * (e.g. the location for one Geometry is null). * This is the case because nodes in one graph which don't intersect * nodes in the other are not completely labelled by the initial process * of adding nodes to the nodeList. * To complete the labelling we need to check for nodes that lie in the * interior of edges, and in the interior of areas. */ private void labelIsolatedNodes() { for (Iterator ni = this.nodes.iterator(); ni.hasNext(); ) { Node n = (Node) ni.next(); Label label = n.getLabel(); // isolated nodes should always have at least one geometry in their label Assert.isTrue(label.getGeometryCount() > 0, "node with empty label found"); if (n.isIsolated()) { if (label.isNull(0)) { this.labelIsolatedNode(n, 0); } else { this.labelIsolatedNode(n, 1); } } } }
/** * Create a StubEdge for the edge after the intersection eiCurr. * The next intersection is provided * in case it is the endpoint for the stub edge. * Otherwise, the next point from the parent edge will be the endpoint. * <br> * eiCurr will always be an EdgeIntersection, but eiNext may be null. */ void createEdgeEndForNext( Edge edge, List l, EdgeIntersection eiCurr, EdgeIntersection eiNext) { int iNext = eiCurr.segmentIndex + 1; // if there is no next edge there is nothing to do if (iNext >= edge.getNumPoints() && eiNext == null) { return; } Coordinate pNext = edge.getCoordinate(iNext); // if the next intersection is in the same segment as the current, use it as the endpoint if (eiNext != null && eiNext.segmentIndex == eiCurr.segmentIndex) { pNext = eiNext.coord; } EdgeEnd e = new EdgeEnd(edge, eiCurr.coord, pNext, new Label(edge.getLabel())); //Debug.println(e); l.add(e); }
/** * This computes the overall edge label for the set of * edges in this EdgeStubBundle. It essentially merges * the ON and side labels for each edge. These labels must be compatible */ @Override public void computeLabel(BoundaryNodeRule boundaryNodeRule) { // create the label. If any of the edges belong to areas, // the label must be an area label boolean isArea = false; for (Iterator it = this.iterator(); it.hasNext(); ) { EdgeEnd e = (EdgeEnd) it.next(); if (e.getLabel().isArea()) { isArea = true; } } if (isArea) { this.label = new Label(Location.NONE, Location.NONE, Location.NONE); } else { this.label = new Label(Location.NONE); } // compute the On label, and the side labels if present for (int i = 0; i < 2; i++) { this.computeLabelOn(i, boundaryNodeRule); if (isArea) { this.computeLabelSides(i); } } }
/** * Collect edges from Area inputs which should be in the result but * which have not been included in a result area. * This happens ONLY: * <ul> * <li>during an intersection when the boundaries of two * areas touch in a line segment * <li> OR as a result of a dimensional collapse. * </ul> */ private void collectBoundaryTouchEdge(DirectedEdge de, int opCode, List edges) { Label label = de.getLabel(); if (de.isLineEdge()) { return; // only interested in area edges } if (de.isVisited()) { return; // already processed } if (de.isInteriorAreaEdge()) { return; // added to handle dimensional collapses } if (de.getEdge().isInResult()) { return; // if the edge linework is already included, don't include it again } // sanity check for labelling of result edgerings Assert.isTrue(!(de.isInResult() || de.getSym().isInResult()) || !de.getEdge().isInResult()); // include the linework if it's in the result of the operation if (OverlayOp.isResultOfOp(label, opCode) && opCode == OverlayOp.INTERSECTION) { edges.add(de.getEdge()); de.setVisitedEdge(true); } }
/** * Incomplete nodes are nodes whose labels are incomplete. * (e.g. the location for one Geometry is null). * These are either isolated nodes, * or nodes which have edges from only a single Geometry incident on them. * <p> * Isolated nodes are found because nodes in one graph which don't intersect * nodes in the other are not completely labelled by the initial process * of adding nodes to the nodeList. * To complete the labelling we need to check for nodes that lie in the * interior of edges, and in the interior of areas. * <p> * When each node labelling is completed, the labelling of the incident * edges is updated, to complete their labelling as well. */ private void labelIncompleteNodes() { int nodeCount = 0; for (Object o : graph.getNodes()) { Node n = (Node) o; Label label = n.getLabel(); if (n.isIsolated()) { nodeCount++; if (label.isNull(0)) { this.labelIncompleteNode(n, 0); } else { this.labelIncompleteNode(n, 1); } } // now update the labelling for the DirectedEdges incident on this node ((DirectedEdgeStar) n.getEdges()).updateLabelling(label); //n.print(System.out); } /* int nPoly0 = arg[0].getGeometry().getNumGeometries(); int nPoly1 = arg[1].getGeometry().getNumGeometries(); System.out.println("# isolated nodes= " + nodeCount + " # poly[0] = " + nPoly0 + " # poly[1] = " + nPoly1); */ }
/** * Find all edges whose label indicates that they are in the result area(s), * according to the operation being performed. Since we want polygon shells to be * oriented CW, choose dirEdges with the interior of the result on the RHS. * Mark them as being in the result. * Interior Area edges are the result of dimensional collapses. * They do not form part of the result area boundary. */ private void findResultAreaEdges(int opCode) { for (Object o : graph.getEdgeEnds()) { DirectedEdge de = (DirectedEdge) o; // mark all dirEdges with the appropriate label Label label = de.getLabel(); if (label.isArea() && !de.isInteriorAreaEdge() && isResultOfOp( label.getLocation(0, Position.RIGHT), label.getLocation(1, Position.RIGHT), opCode)) { de.setInResult(true); //Debug.print("in result "); Debug.println(de); } } }
private void computeNodedEdges(List bufferSegStrList, PrecisionModel precisionModel) { Noder noder = this.getNoder(precisionModel); noder.computeNodes(bufferSegStrList); Collection nodedSegStrings = noder.getNodedSubstrings(); // DEBUGGING ONLY //BufferDebug.saveEdges(nodedEdges, "run" + BufferDebug.runCount + "_nodedEdges"); for (Object nodedSegString : nodedSegStrings) { SegmentString segStr = (SegmentString) nodedSegString; /** * Discard edges which have zero length, * since they carry no information and cause problems with topology building */ Coordinate[] pts = segStr.getCoordinates(); if (pts.length == 2 && pts[0].equals2D(pts[1])) { continue; } Label oldLabel = (Label) segStr.getData(); Edge edge = new Edge(segStr.getCoordinates(), new Label(oldLabel)); this.insertUniqueEdge(edge); } //saveEdges(edgeList.getEdges(), "run" + runCount + "_collapsedEdges"); }
/** * Create a EdgeStub for the edge before the intersection eiCurr. * The previous intersection is provided * in case it is the endpoint for the stub edge. * Otherwise, the previous point from the parent edge will be the endpoint. * <br> * eiCurr will always be an EdgeIntersection, but eiPrev may be null. */ void createEdgeEndForPrev( Edge edge, List l, EdgeIntersection eiCurr, EdgeIntersection eiPrev) { int iPrev = eiCurr.segmentIndex; if (eiCurr.dist == 0.0) { // if at the start of the edge there is no previous edge if (iPrev == 0) { return; } iPrev--; } Coordinate pPrev = edge.getCoordinate(iPrev); // if prev intersection is past the previous vertex, use it instead if (eiPrev != null && eiPrev.segmentIndex >= iPrev) { pPrev = eiPrev.coord; } Label label = new Label(edge.getLabel()); // since edgeStub is oriented opposite to it's parent edge, have to flip sides for edge label label.flip(); EdgeEnd e = new EdgeEnd(edge, eiCurr.coord, pPrev, label); //e.print(System.out); System.out.println(); l.add(e); }
public EdgeEndBundle(BoundaryNodeRule boundaryNodeRule, EdgeEnd e) { super(e.getEdge(), e.getCoordinate(), e.getDirectedCoordinate(), new Label(e.getLabel())); this.insert(e); /* if (boundaryNodeRule != null) this.boundaryNodeRule = boundaryNodeRule; else boundaryNodeRule = BoundaryNodeRule.OGC_SFS_BOUNDARY_RULE; */ }
/** * Collect line edges which are in the result. * Line edges are in the result if they are not part of * an area boundary, if they are in the result of the overlay operation, * and if they are not covered by a result area. * * @param de the directed edge to test * @param opCode the overlap operation * @param edges the list of included line edges */ private void collectLineEdge(DirectedEdge de, int opCode, List edges) { Label label = de.getLabel(); Edge e = de.getEdge(); // include L edges which are in the result if (de.isLineEdge()) { if (!de.isVisited() && OverlayOp.isResultOfOp(label, opCode) && !e.isCovered()) { //Debug.println("de: " + de.getLabel()); //Debug.println("edge: " + e.getLabel()); edges.add(e); de.setVisitedEdge(true); } } }
private void buildLines(int opCode) { for (Object aLineEdgesList : lineEdgesList) { Edge e = (Edge) aLineEdgesList; Label label = e.getLabel(); LineString line = this.geometryFactory.createLineString(e.getCoordinates()); this.resultLineList.add(line); e.setInResult(true); } }
private void labelIsolatedLines(List edgesList) { for (Object anEdgesList : edgesList) { Edge e = (Edge) anEdgesList; Label label = e.getLabel(); //n.print(System.out); if (e.isIsolated()) { if (label.isNull(0)) { this.labelIsolatedLine(e, 0); } else { this.labelIsolatedLine(e, 1); } } } }
private boolean isPotentialResultAreaEdge(DirectedEdge de, int opCode) { // mark all dirEdges with the appropriate label Label label = de.getLabel(); return label.isArea() && !de.isInteriorAreaEdge() && OverlayOp.isResultOfOp( label.getLocation(0, Position.RIGHT), label.getLocation(1, Position.RIGHT), opCode); }
/** * Determines nodes which are in the result, and creates {@link Point}s for them. * <p> * This method determines nodes which are candidates for the result via their * labelling and their graph topology. * * @param opCode the overlay operation */ private void extractNonCoveredResultNodes(int opCode) { // testing only //if (true) return resultNodeList; for (Object o : op.getGraph().getNodes()) { Node n = (Node) o; // filter out nodes which are known to be in the result if (n.isInResult()) { continue; } // if an incident edge is in the result, then the node coordinate is included already if (n.isIncidentEdgeInResult()) { continue; } if (n.getEdges().getDegree() == 0 || opCode == OverlayOp.INTERSECTION) { /** * For nodes on edges, only INTERSECTION can result in edge nodes being included even * if none of their incident edges are included */ Label label = n.getLabel(); if (OverlayOp.isResultOfOp(label, opCode)) { this.filterCoveredNodeToPoint(n); } } } //System.out.println("connectedResultNodes collected = " + connectedResultNodes.size()); }
/** * Update the labels for edges according to their depths. * For each edge, the depths are first normalized. * Then, if the depths for the edge are equal, * this edge must have collapsed into a line edge. * If the depths are not equal, update the label * with the locations corresponding to the depths * (i.e. a depth of 0 corresponds to a Location of EXTERIOR, * a depth of 1 corresponds to INTERIOR) */ private void computeLabelsFromDepths() { for (Iterator it = this.edgeList.iterator(); it.hasNext(); ) { Edge e = (Edge) it.next(); Label lbl = e.getLabel(); Depth depth = e.getDepth(); /** * Only check edges for which there were duplicates, * since these are the only ones which might * be the result of dimensional collapses. */ if (!depth.isNull()) { depth.normalize(); for (int i = 0; i < 2; i++) { if (!lbl.isNull(i) && lbl.isArea() && !depth.isNull(i)) { /** * if the depths are equal, this edge is the result of * the dimensional collapse of two or more edges. * It has the same location on both sides of the edge, * so it has collapsed to a line. */ if (depth.getDelta(i) == 0) { lbl.toLine(i); } else { /** * This edge may be the result of a dimensional collapse, * but it still has different locations on both sides. The * label of the edge must be updated to reflect the resultant * side locations indicated by the depth values. */ Assert.isTrue(!depth.isNull(i, Position.LEFT), "depth of LEFT side has not been initialized"); lbl.setLocation(i, Position.LEFT, depth.getLocation(i, Position.LEFT)); Assert.isTrue(!depth.isNull(i, Position.RIGHT), "depth of RIGHT side has not been initialized"); lbl.setLocation(i, Position.RIGHT, depth.getLocation(i, Position.RIGHT)); } } } } } }
private void updateNodeLabelling() { // update the labels for nodes // The label for a node is updated from the edges incident on it // (Note that a node may have already been labelled // because it is a point in one of the input geometries) for (Object o : graph.getNodes()) { Node node = (Node) o; Label lbl = ((DirectedEdgeStar) node.getEdges()).getLabel(); node.getLabel().merge(lbl); } }
/** * Compute the change in depth as an edge is crossed from R to L */ private static int depthDelta(Label label) { int lLoc = label.getLocation(0, Position.LEFT); int rLoc = label.getLocation(0, Position.RIGHT); if (lLoc == Location.INTERIOR && rLoc == Location.EXTERIOR) { return 1; } else if (lLoc == Location.EXTERIOR && rLoc == Location.INTERIOR) { return -1; } return 0; }
/** * Creates a {@link SegmentString} for a coordinate list which is a raw offset curve, * and adds it to the list of buffer curves. * The SegmentString is tagged with a Label giving the topology of the curve. * The curve may be oriented in either direction. * If the curve is oriented CW, the locations will be: * <br>Left: Location.EXTERIOR * <br>Right: Location.INTERIOR */ private void addCurve(Coordinate[] coord, int leftLoc, int rightLoc) { // don't add null or trivial curves if (coord == null || coord.length < 2) { return; } // add the edge for a coordinate list which is a raw offset curve SegmentString e = new NodedSegmentString(coord, new Label(0, Location.BOUNDARY, leftLoc, rightLoc)); this.curveList.add(e); }
public void computeDepth(int outsideDepth) { this.clearVisitedEdges(); // find an outside edge to assign depth to DirectedEdge de = this.finder.getEdge(); Node n = de.getNode(); Label label = de.getLabel(); // right side of line returned by finder is on the outside de.setEdgeDepths(Position.RIGHT, outsideDepth); this.copySymDepths(de); //computeNodeDepth(n, de); this.computeDepths(de); }
/** * Determines nodes which are in the result, and creates {@link Point}s for them. * <p/> * This method determines nodes which are candidates for the result via their * labelling and their graph topology. * * @param opCode the overlay operation */ private void extractNonCoveredResultNodes(int opCode) { // testing only //if (true) return resultNodeList; for (Iterator nodeit = op.getGraph().getNodes().iterator(); nodeit.hasNext(); ) { Node n = (Node) nodeit.next(); // filter out nodes which are known to be in the result if (n.isInResult()) continue; // if an incident edge is in the result, then the node coordinate is included already if (n.isIncidentEdgeInResult()) continue; if (n.getEdges().getDegree() == 0 || opCode == OverlayOp.INTERSECTION) { /** * For nodes on edges, only INTERSECTION can result in edge nodes being included even * if none of their incident edges are included */ Label label = n.getLabel(); if (OverlayOp.isResultOfOp(label, opCode)) { filterCoveredNodeToPoint(n); } } } //System.out.println("connectedResultNodes collected = " + connectedResultNodes.size()); }
/** * To merge labels for two nodes, * the merged location for each LabelElement is computed. * The location for the corresponding node LabelElement is set to the result, * as long as the location is non-null. */ public void mergeLabel(Label label2) { for (int i = 0; i < 2; i++) { int loc = computeMergedLocation(label2, i); int thisLoc = label.getLocation(i); if (thisLoc == Location.NONE) label.setLocation(i, loc); } }
/** * The location for a given eltIndex for a node will be one * of { null, INTERIOR, BOUNDARY }. * A node may be on both the boundary and the interior of a geometry; * in this case, the rule is that the node is considered to be in the boundary. * The merged location is the maximum of the two input values. */ int computeMergedLocation(Label label2, int eltIndex) { int loc = Location.NONE; loc = label.getLocation(eltIndex); if (! label2.isNull(eltIndex)) { int nLoc = label2.getLocation(eltIndex); if (loc != Location.BOUNDARY) loc = nLoc; } return loc; }
@Override public Label getLabel() { return this.label; }
public static boolean isResultOfOp(Label label, int opCode) { int loc0 = label.getLocation(0); int loc1 = label.getLocation(1); return isResultOfOp(loc0, loc1, opCode); }
public GraphComponent(Label label) { this.label = label; }
public EdgeEnd(Edge edge, Coordinate p0, Coordinate p1, Label label) { this(edge); init(p0, p1); this.label = label; }
public Node(Coordinate coord, EdgeEndStar edges) { this.coord = coord; this.edges = edges; label = new Label(0, Location.NONE); }
/** * Creates a {@link SegmentString} for a coordinate list which is a raw offset curve, * and adds it to the list of buffer curves. * The SegmentString is tagged with a Label giving the topology of the curve. * The curve may be oriented in either direction. * If the curve is oriented CW, the locations will be: * <br>Left: Location.EXTERIOR * <br>Right: Location.INTERIOR */ private void addCurve(Coordinate[] coord, int leftLoc, int rightLoc) { // don't add null or trivial curves if (coord == null || coord.length < 2) return; // add the edge for a coordinate list which is a raw offset curve SegmentString e = new NodedSegmentString(coord, new Label(0, Location.BOUNDARY, leftLoc, rightLoc)); curveList.add(e); }
public Label getLabel() { return label; }
public void setLabel(Label label) { this.label = label; }
