@Test public void testSimpleLineEndpoints() throws Exception { float s = 10; Polygon p = new Polygon(new float[] { 0, 0, s, 0, s, s, 0, s }); PathFinder pf = new PathFinder(p, null); Vector2 tgt = new Vector2(s - 1, s - 1); assertArrayEquals("direct clear path in square", new Vector2[] { tgt }, pf.lineEndpoints(new Vector2(1, 1), tgt, true)); assertArrayEquals( "direct path in square, starting from opposite corner", new Vector2[] { tgt }, pf.lineEndpoints(new Vector2(0, 0), tgt, true)); assertArrayEquals("impossible path in square", new Vector2[] { new Vector2(s, 0), new Vector2(s, s) }, pf.lineEndpoints(tgt, new Vector2(s + s, s / 2), true)); }
Vector2[] lineEndpoints(Vector2 source, Vector2 target, boolean recursive) { Vector2 moreThanEpsilon = new Vector2(target).sub(source).nor() .scl(MINIMAL_DISPLACEMENT); Vector2 justAfterSource = new Vector2(source).add(moreThanEpsilon); boolean startsByGoingOutside = !pathBoundary.contains( justAfterSource.x, justAfterSource.y); if (!startsByGoingOutside) { Vector2 justBeforeTarget = new Vector2(target).sub(moreThanEpsilon) .sub(moreThanEpsilon); if (!PathUtils.intersectSegmentPolygon(justAfterSource, justBeforeTarget, pathBoundary, new Vector2())) { return new Vector2[] { target }; } else { } } else { for (int i = 0; i < boundaryPoints.length - 1; i++) { if (Intersector.distanceSegmentPoint(boundaryPoints[i], boundaryPoints[i + 1], source) < MINIMAL_DISPLACEMENT) { return new Vector2[] { boundaryPoints[i], boundaryPoints[i + 1] }; } } throw new IllegalStateException( "Expected to find a very close segment"); } Vector2 crossOverPoint = new Vector2(); float closest = Float.POSITIVE_INFINITY; Vector2 best = null; int firstSegment = -1; for (int i = 0; i < boundaryPoints.length - 1; i++) { int relative = Intersector.pointLineSide(justAfterSource, boundaryPoints[i], boundaryPoints[i + 1]); if (relative > 0) { if (Intersector.intersectSegments(justAfterSource, target, boundaryPoints[i], boundaryPoints[i + 1], crossOverPoint)) { float dst2 = crossOverPoint.dst2(source); if (dst2 < closest) { closest = dst2; best = crossOverPoint; firstSegment = i; } } } } if (firstSegment == -1) { throw new IllegalStateException( "Expected to intersect something, since there was no direct path."); } Vector2[] result; if (!recursive) { result = new Vector2[] { best }; } else { Vector2[] r1 = lineEndpoints(source, boundaryPoints[firstSegment], false); Vector2[] r2 = lineEndpoints(source, boundaryPoints[firstSegment + 1], false); result = new Vector2[r1.length + r2.length]; System.arraycopy(r1, 0, result, 0, r1.length); System.arraycopy(r2, 0, result, r1.length, r2.length); } return result; }
PathFinder { Vector2[] lineEndpoints(Vector2 source, Vector2 target, boolean recursive) { Vector2 moreThanEpsilon = new Vector2(target).sub(source).nor() .scl(MINIMAL_DISPLACEMENT); Vector2 justAfterSource = new Vector2(source).add(moreThanEpsilon); boolean startsByGoingOutside = !pathBoundary.contains( justAfterSource.x, justAfterSource.y); if (!startsByGoingOutside) { Vector2 justBeforeTarget = new Vector2(target).sub(moreThanEpsilon) .sub(moreThanEpsilon); if (!PathUtils.intersectSegmentPolygon(justAfterSource, justBeforeTarget, pathBoundary, new Vector2())) { return new Vector2[] { target }; } else { } } else { for (int i = 0; i < boundaryPoints.length - 1; i++) { if (Intersector.distanceSegmentPoint(boundaryPoints[i], boundaryPoints[i + 1], source) < MINIMAL_DISPLACEMENT) { return new Vector2[] { boundaryPoints[i], boundaryPoints[i + 1] }; } } throw new IllegalStateException( "Expected to find a very close segment"); } Vector2 crossOverPoint = new Vector2(); float closest = Float.POSITIVE_INFINITY; Vector2 best = null; int firstSegment = -1; for (int i = 0; i < boundaryPoints.length - 1; i++) { int relative = Intersector.pointLineSide(justAfterSource, boundaryPoints[i], boundaryPoints[i + 1]); if (relative > 0) { if (Intersector.intersectSegments(justAfterSource, target, boundaryPoints[i], boundaryPoints[i + 1], crossOverPoint)) { float dst2 = crossOverPoint.dst2(source); if (dst2 < closest) { closest = dst2; best = crossOverPoint; firstSegment = i; } } } } if (firstSegment == -1) { throw new IllegalStateException( "Expected to intersect something, since there was no direct path."); } Vector2[] result; if (!recursive) { result = new Vector2[] { best }; } else { Vector2[] r1 = lineEndpoints(source, boundaryPoints[firstSegment], false); Vector2[] r2 = lineEndpoints(source, boundaryPoints[firstSegment + 1], false); result = new Vector2[r1.length + r2.length]; System.arraycopy(r1, 0, result, 0, r1.length); System.arraycopy(r2, 0, result, r1.length, r2.length); } return result; } }
PathFinder { Vector2[] lineEndpoints(Vector2 source, Vector2 target, boolean recursive) { Vector2 moreThanEpsilon = new Vector2(target).sub(source).nor() .scl(MINIMAL_DISPLACEMENT); Vector2 justAfterSource = new Vector2(source).add(moreThanEpsilon); boolean startsByGoingOutside = !pathBoundary.contains( justAfterSource.x, justAfterSource.y); if (!startsByGoingOutside) { Vector2 justBeforeTarget = new Vector2(target).sub(moreThanEpsilon) .sub(moreThanEpsilon); if (!PathUtils.intersectSegmentPolygon(justAfterSource, justBeforeTarget, pathBoundary, new Vector2())) { return new Vector2[] { target }; } else { } } else { for (int i = 0; i < boundaryPoints.length - 1; i++) { if (Intersector.distanceSegmentPoint(boundaryPoints[i], boundaryPoints[i + 1], source) < MINIMAL_DISPLACEMENT) { return new Vector2[] { boundaryPoints[i], boundaryPoints[i + 1] }; } } throw new IllegalStateException( "Expected to find a very close segment"); } Vector2 crossOverPoint = new Vector2(); float closest = Float.POSITIVE_INFINITY; Vector2 best = null; int firstSegment = -1; for (int i = 0; i < boundaryPoints.length - 1; i++) { int relative = Intersector.pointLineSide(justAfterSource, boundaryPoints[i], boundaryPoints[i + 1]); if (relative > 0) { if (Intersector.intersectSegments(justAfterSource, target, boundaryPoints[i], boundaryPoints[i + 1], crossOverPoint)) { float dst2 = crossOverPoint.dst2(source); if (dst2 < closest) { closest = dst2; best = crossOverPoint; firstSegment = i; } } } } if (firstSegment == -1) { throw new IllegalStateException( "Expected to intersect something, since there was no direct path."); } Vector2[] result; if (!recursive) { result = new Vector2[] { best }; } else { Vector2[] r1 = lineEndpoints(source, boundaryPoints[firstSegment], false); Vector2[] r2 = lineEndpoints(source, boundaryPoints[firstSegment + 1], false); result = new Vector2[r1.length + r2.length]; System.arraycopy(r1, 0, result, 0, r1.length); System.arraycopy(r2, 0, result, r1.length, r2.length); } return result; } PathFinder(Polygon pathBoundary, Matrix3 viewToWorld); }
PathFinder { Vector2[] lineEndpoints(Vector2 source, Vector2 target, boolean recursive) { Vector2 moreThanEpsilon = new Vector2(target).sub(source).nor() .scl(MINIMAL_DISPLACEMENT); Vector2 justAfterSource = new Vector2(source).add(moreThanEpsilon); boolean startsByGoingOutside = !pathBoundary.contains( justAfterSource.x, justAfterSource.y); if (!startsByGoingOutside) { Vector2 justBeforeTarget = new Vector2(target).sub(moreThanEpsilon) .sub(moreThanEpsilon); if (!PathUtils.intersectSegmentPolygon(justAfterSource, justBeforeTarget, pathBoundary, new Vector2())) { return new Vector2[] { target }; } else { } } else { for (int i = 0; i < boundaryPoints.length - 1; i++) { if (Intersector.distanceSegmentPoint(boundaryPoints[i], boundaryPoints[i + 1], source) < MINIMAL_DISPLACEMENT) { return new Vector2[] { boundaryPoints[i], boundaryPoints[i + 1] }; } } throw new IllegalStateException( "Expected to find a very close segment"); } Vector2 crossOverPoint = new Vector2(); float closest = Float.POSITIVE_INFINITY; Vector2 best = null; int firstSegment = -1; for (int i = 0; i < boundaryPoints.length - 1; i++) { int relative = Intersector.pointLineSide(justAfterSource, boundaryPoints[i], boundaryPoints[i + 1]); if (relative > 0) { if (Intersector.intersectSegments(justAfterSource, target, boundaryPoints[i], boundaryPoints[i + 1], crossOverPoint)) { float dst2 = crossOverPoint.dst2(source); if (dst2 < closest) { closest = dst2; best = crossOverPoint; firstSegment = i; } } } } if (firstSegment == -1) { throw new IllegalStateException( "Expected to intersect something, since there was no direct path."); } Vector2[] result; if (!recursive) { result = new Vector2[] { best }; } else { Vector2[] r1 = lineEndpoints(source, boundaryPoints[firstSegment], false); Vector2[] r2 = lineEndpoints(source, boundaryPoints[firstSegment + 1], false); result = new Vector2[r1.length + r2.length]; System.arraycopy(r1, 0, result, 0, r1.length); System.arraycopy(r2, 0, result, r1.length, r2.length); } return result; } PathFinder(Polygon pathBoundary, Matrix3 viewToWorld); Matrix3 getViewToWorld(); Matrix3 getWorldToView(); PathIterator findPath(Vector2 start, Vector2 finish, float step); float scaleAt(Vector2 point); }
PathFinder { Vector2[] lineEndpoints(Vector2 source, Vector2 target, boolean recursive) { Vector2 moreThanEpsilon = new Vector2(target).sub(source).nor() .scl(MINIMAL_DISPLACEMENT); Vector2 justAfterSource = new Vector2(source).add(moreThanEpsilon); boolean startsByGoingOutside = !pathBoundary.contains( justAfterSource.x, justAfterSource.y); if (!startsByGoingOutside) { Vector2 justBeforeTarget = new Vector2(target).sub(moreThanEpsilon) .sub(moreThanEpsilon); if (!PathUtils.intersectSegmentPolygon(justAfterSource, justBeforeTarget, pathBoundary, new Vector2())) { return new Vector2[] { target }; } else { } } else { for (int i = 0; i < boundaryPoints.length - 1; i++) { if (Intersector.distanceSegmentPoint(boundaryPoints[i], boundaryPoints[i + 1], source) < MINIMAL_DISPLACEMENT) { return new Vector2[] { boundaryPoints[i], boundaryPoints[i + 1] }; } } throw new IllegalStateException( "Expected to find a very close segment"); } Vector2 crossOverPoint = new Vector2(); float closest = Float.POSITIVE_INFINITY; Vector2 best = null; int firstSegment = -1; for (int i = 0; i < boundaryPoints.length - 1; i++) { int relative = Intersector.pointLineSide(justAfterSource, boundaryPoints[i], boundaryPoints[i + 1]); if (relative > 0) { if (Intersector.intersectSegments(justAfterSource, target, boundaryPoints[i], boundaryPoints[i + 1], crossOverPoint)) { float dst2 = crossOverPoint.dst2(source); if (dst2 < closest) { closest = dst2; best = crossOverPoint; firstSegment = i; } } } } if (firstSegment == -1) { throw new IllegalStateException( "Expected to intersect something, since there was no direct path."); } Vector2[] result; if (!recursive) { result = new Vector2[] { best }; } else { Vector2[] r1 = lineEndpoints(source, boundaryPoints[firstSegment], false); Vector2[] r2 = lineEndpoints(source, boundaryPoints[firstSegment + 1], false); result = new Vector2[r1.length + r2.length]; System.arraycopy(r1, 0, result, 0, r1.length); System.arraycopy(r2, 0, result, r1.length, r2.length); } return result; } PathFinder(Polygon pathBoundary, Matrix3 viewToWorld); Matrix3 getViewToWorld(); Matrix3 getWorldToView(); PathIterator findPath(Vector2 start, Vector2 finish, float step); float scaleAt(Vector2 point);  }