/** * Finds the index of the last point in a monotone chain * starting at a given point. * Any repeated points (0-length segments) will be included * in the monotone chain returned. * * @return the index of the last point in the monotone chain * starting at <code>start</code>. */ private static int findChainEnd(Coordinate[] pts, int start) { int safeStart = start; // skip any zero-length segments at the start of the sequence // (since they cannot be used to establish a quadrant) while (safeStart < pts.length - 1 && pts[safeStart].equals2D(pts[safeStart + 1])) { safeStart++; } // check if there are NO non-zero-length segments if (safeStart >= pts.length - 1) { return pts.length - 1; } // determine overall quadrant for chain (which is the starting quadrant) int chainQuad = Quadrant.quadrant(pts[safeStart], pts[safeStart + 1]); int last = start + 1; while (last < pts.length) { // skip zero-length segments, but include them in the chain if (!pts[last - 1].equals2D(pts[last])) { // compute quadrant for next possible segment in chain int quad = Quadrant.quadrant(pts[last - 1], pts[last]); if (quad != chainQuad) break; } last++; } return last - 1; }
/** * Constructs a DirectedEdge connecting the <code>from</code> node to the * <code>to</code> node. * * @param directionPt specifies this DirectedEdge's direction vector * (determined by the vector from the <code>from</code> node * to <code>directionPt</code>) * @param edgeDirection whether this DirectedEdge's direction is the same as or * opposite to that of the parent Edge (if any) */ public DirectedEdge(Node from, Node to, Coordinate directionPt, boolean edgeDirection) { this.from = from; this.to = to; this.edgeDirection = edgeDirection; this.p0 = from.getCoordinate(); this.p1 = directionPt; double dx = this.p1.x - this.p0.x; double dy = this.p1.y - this.p0.y; this.quadrant = Quadrant.quadrant(dx, dy); this.angle = Math.atan2(dy, dx); //Assert.isTrue(! (dx == 0 && dy == 0), "EdgeEnd with identical endpoints found"); }
/** * @return the index of the last point in the monotone chain */ private int findChainEnd(Coordinate[] pts, int start) { // determine quadrant for chain int chainQuad = Quadrant.quadrant(pts[start], pts[start + 1]); int last = start + 1; while (last < pts.length) { // compute quadrant for next possible segment in chain int quad = Quadrant.quadrant(pts[last - 1], pts[last]); if (quad != chainQuad) { break; } last++; } return last - 1; }
/** * Finds the index of the last point in a monotone chain * starting at a given point. * Any repeated points (0-length segments) will be included * in the monotone chain returned. * * @return the index of the last point in the monotone chain * starting at <code>start</code>. */ private static int findChainEnd(Coordinate[] pts, int start) { int safeStart = start; // skip any zero-length segments at the start of the sequence // (since they cannot be used to establish a quadrant) while (safeStart < pts.length - 1 && pts[safeStart].equals2D(pts[safeStart + 1])) { safeStart++; } // check if there are NO non-zero-length segments if (safeStart >= pts.length - 1) { return pts.length - 1; } // determine overall quadrant for chain (which is the starting quadrant) int chainQuad = Quadrant.quadrant(pts[safeStart], pts[safeStart + 1]); int last = start + 1; while (last < pts.length) { // skip zero-length segments, but include them in the chain if (!pts[last - 1].equals2D(pts[last])) { // compute quadrant for next possible segment in chain int quad = Quadrant.quadrant(pts[last - 1], pts[last]); if (quad != chainQuad) { break; } } last++; } return last - 1; }
/** * Constructs a DirectedEdge connecting the <code>from</code> node to the * <code>to</code> node. * * @param directionPt specifies this DirectedEdge's direction vector * (determined by the vector from the <code>from</code> node * to <code>directionPt</code>) * @param edgeDirection whether this DirectedEdge's direction is the same as or * opposite to that of the parent Edge (if any) */ public DirectedEdge(Node from, Node to, Coordinate directionPt, boolean edgeDirection) { this.from = from; this.to = to; this.edgeDirection = edgeDirection; p0 = from.getCoordinate(); p1 = directionPt; double dx = p1.x - p0.x; double dy = p1.y - p0.y; quadrant = Quadrant.quadrant(dx, dy); angle = Math.atan2(dy, dx); //Assert.isTrue(! (dx == 0 && dy == 0), "EdgeEnd with identical endpoints found"); }
/** * @return the index of the last point in the monotone chain */ private int findChainEnd(Coordinate[] pts, int start) { // determine quadrant for chain int chainQuad = Quadrant.quadrant(pts[start], pts[start + 1]); int last = start + 1; while (last < pts.length) { // compute quadrant for next possible segment in chain int quad = Quadrant.quadrant(pts[last - 1], pts[last]); if (quad != chainQuad) break; last++; } return last - 1; }
/** * Constructs a DirectedEdge connecting the <code>from</code> node to the * <code>to</code> node. * * @param directionPt * specifies this DirectedEdge's direction vector * (determined by the vector from the <code>from</code> node * to <code>directionPt</code>) * @param edgeDirection * whether this DirectedEdge's direction is the same as or * opposite to that of the parent Edge (if any) */ public DirectedEdge(Node from, Node to, Coordinate directionPt, boolean edgeDirection) { this.from = from; this.to = to; this.edgeDirection = edgeDirection; p0 = from.getCoordinate(); p1 = directionPt; double dx = p1.x - p0.x; double dy = p1.y - p0.y; quadrant = Quadrant.quadrant(dx, dy); angle = Math.atan2(dy, dx); //Assert.isTrue(! (dx == 0 && dy == 0), "EdgeEnd with identical endpoints found"); }
/** * Finds the index of the last point in a monotone chain * starting at a given point. * Any repeated points (0-length segments) will be included * in the monotone chain returned. * * @return the index of the last point in the monotone chain * starting at <code>start</code>. */ private static int findChainEnd(Coordinate[] pts, int start) { int safeStart = start; // skip any zero-length segments at the start of the sequence // (since they cannot be used to establish a quadrant) while (safeStart < pts.length - 1 && pts[safeStart].equals2D(pts[safeStart + 1])) { safeStart++; } // check if there are NO non-zero-length segments if (safeStart >= pts.length - 1) { return pts.length - 1; } // determine overall quadrant for chain (which is the starting quadrant) int chainQuad = Quadrant.quadrant(pts[safeStart], pts[safeStart + 1]); int last = start + 1; while (last < pts.length) { // skip zero-length segments, but include them in the chain if (! pts[last - 1].equals2D(pts[last])) { // compute quadrant for next possible segment in chain int quad = Quadrant.quadrant(pts[last - 1], pts[last]); if (quad != chainQuad) break; } last++; } return last - 1; }
/** * Implements the total order relation: * <p/> * The angle of edge a is greater than the angle of edge b, * where the angle of an edge is the angle made by * the first segment of the edge with the positive x-axis * <p/> * When applied to a list of edges originating at the same point, * this produces a CCW ordering of the edges around the point. * <p/> * Using the obvious algorithm of computing the angle is not robust, * since the angle calculation is susceptible to roundoff error. * A robust algorithm is: * <ul> * <li>First, compare the quadrants the edge vectors lie in. * If the quadrants are different, * it is trivial to determine which edge has a greater angle. * <p/> * <li>if the vectors lie in the same quadrant, the * {@link CGAlgorithms#computeOrientation(Coordinate, Coordinate, Coordinate)} function * can be used to determine the relative orientation of the vectors. * </ul> */ public int compareAngularDirection(HalfEdge e) { double dx = deltaX(); double dy = deltaY(); double dx2 = e.deltaX(); double dy2 = e.deltaY(); // same vector if (dx == dx2 && dy == dy2) return 0; double quadrant = Quadrant.quadrant(dx, dy); double quadrant2 = Quadrant.quadrant(dx2, dy2); // if the vectors are in different quadrants, determining the ordering is trivial if (quadrant > quadrant2) return 1; if (quadrant < quadrant2) return -1; // vectors are in the same quadrant // Check relative orientation of direction vectors // this is > e if it is CCW of e return CGAlgorithms.computeOrientation(e.orig, e.dest(), dest()); }
