| [Arakhnę-Dev] [409] * Replace the segment-segment intersection test by two functions: one which assumes that the ends of the segments may cause intersection matching , and the other which assumes that these ends may not cause any intersection . |
[ Thread Index |
Date Index
| More arakhne.org/dev Archives
]
- To: dev@xxxxxxxxxxx
- Subject: [Arakhnę-Dev] [409] * Replace the segment-segment intersection test by two functions: one which assumes that the ends of the segments may cause intersection matching , and the other which assumes that these ends may not cause any intersection .
- From: subversion@xxxxxxxxxxxxx
- Date: Fri, 05 Apr 2013 12:06:40 +0200
Revision: 409
Author: galland
Date: 2013-04-05 12:06:40 +0200 (Fri, 05 Apr 2013)
Log Message:
-----------
* Replace the segment-segment intersection test by two functions: one which assumes that the ends of the segments may cause intersection matching, and the other which assumes that these ends may not cause any intersection.
Modified Paths:
--------------
trunk/math/src/main/java/org/arakhne/afc/math/continous/object2d/Segment2f.java
trunk/math/src/test/java/org/arakhne/afc/math/continous/object2d/Segment2fTest.java
Modified: trunk/math/src/main/java/org/arakhne/afc/math/continous/object2d/Segment2f.java
===================================================================
--- trunk/math/src/main/java/org/arakhne/afc/math/continous/object2d/Segment2f.java 2013-04-05 10:04:20 UTC (rev 408)
+++ trunk/math/src/main/java/org/arakhne/afc/math/continous/object2d/Segment2f.java 2013-04-05 10:06:40 UTC (rev 409)
@@ -113,7 +113,7 @@
if (y0>=ymax) --numCrosses;
}
}
- else if (intersectsSegmentSegment(x0, y0, x1, y1, sx1, sy1, sx2, sy2)) {
+ else if (intersectsSegmentSegmentWithoutEnds(x0, y0, x1, y1, sx1, sy1, sx2, sy2)) {
return MathConstants.SHAPE_INTERSECTS;
}
else {
@@ -376,7 +376,148 @@
MathUtil.sidePointLine(x3, y3, x4, y4, x2, y2, true)) <= 0;
}
+ private static boolean intersectsSSWE(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
+ float vx1, vy1, vx2a, vy2a, vx2b, vy2b, f1, f2, sign;
+
+ vx1 = x2 - x1;
+ vy1 = y2 - y1;
+
+ // Based on CCW. It is different than MathUtil.ccw(); because
+ // this small algorithm is computing a ccw of 0 for colinear points.
+ vx2a = x3 - x1;
+ vy2a = y3 - y1;
+ f1 = vx2a * vy1 - vy2a * vx1;
+
+ vx2b = x4 - x1;
+ vy2b = y4 - y1;
+ f2 = vx2b * vy1 - vy2b * vx1;
+
+ // s = f1 * f2
+ //
+ // f1 f2 s intersect
+ // -1 -1 1 F
+ // -1 0 0 ON SEGMENT?
+ // -1 1 -1 T
+ // 0 -1 0 ON SEGMENT?
+ // 0 0 0 SEGMENT INTERSECTION?
+ // 0 1 1 ON SEGMENT?
+ // 1 -1 -1 T
+ // 1 0 0 ON SEGMENT?
+ // 1 1 1 F
+ sign = f1 * f2;
+
+ if (sign<0f) return true;
+ if (sign>0f) return false;
+
+ float squaredLength = vx1*vx1 + vy1*vy1;
+
+ if (f1==0f && f2==0f) {
+ // Projection of the point on the segment line:
+ // <0 -> means before first point
+ // >1 -> means after second point
+ // otherwhise on the segment.
+
+ f1 = (vx2a * vx1 + vy2a * vy1) / squaredLength;
+ f2 = (vx2b * vx1 + vy2b * vy1) / squaredLength;
+
+ // No intersection when:
+ // f1<0 && f2<0 or
+ // f1>1 && f2>1
+
+ return (f1>=0f || f2>=0) && (f1<=1f || f2<=1f);
+ }
+
+ if (f1==0f) {
+ // Projection of the point on the segment line:
+ // <0 -> means before first point
+ // >1 -> means after second point
+ // otherwhise on the segment.
+
+ f1 = (vx2a * vx1 + vy2a * vy1) / squaredLength;
+
+ // No intersection when:
+ // f1<=0 && f2<=0 or
+ // f1>=1 && f2>=1
+
+ return (f1>=0f && f1<=1f);
+ }
+
+ if (f2==0f) {
+ // Projection of the point on the segment line:
+ // <0 -> means before first point
+ // >1 -> means after second point
+ // otherwhise on the segment.
+
+ f2 = (vx2b * vx1 + vy2b * vy1) / squaredLength;
+
+ // No intersection when:
+ // f1<0 && f2<0 or
+ // f1>1 && f2>1
+
+ return (f2>=0 && f2<=1f);
+ }
+
+ return false;
+ }
+
+ private static boolean intersectsSSWoE(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
+ float vx1, vy1, vx2a, vy2a, vx2b, vy2b, f1, f2, sign;
+
+ vx1 = x2 - x1;
+ vy1 = y2 - y1;
+
+ vx2a = x3 - x1;
+ vy2a = y3 - y1;
+ f1 = vx2a * vy1 - vy2a * vx1;
+
+ vx2b = x4 - x1;
+ vy2b = y4 - y1;
+ f2 = vx2b * vy1 - vy2b * vx1;
+
+ // s = f1 * f2
+ //
+ // f1 f2 s intersect
+ // -1 -1 1 F
+ // -1 0 0 F
+ // -1 1 -1 T
+ // 0 -1 0 F
+ // 0 0 0 SEGMENT INTERSECTION?
+ // 0 1 1 F
+ // 1 -1 -1 T
+ // 1 0 0 F
+ // 1 1 1 F
+
+ sign = f1 * f2;
+
+ if (sign<0f) return true;
+ if (sign>0f) return false;
+
+ if (f1==0f && f2==0f) {
+ // Projection of the point on the segment line:
+ // <0 -> means before first point
+ // >1 -> means after second point
+ // otherwhise on the segment.
+
+ float squaredLength = vx1*vx1 + vy1*vy1;
+
+ f1 = (vx2a * vx1 + vy2a * vy1) / squaredLength;
+ f2 = (vx2b * vx1 + vy2b * vy1) / squaredLength;
+
+ // No intersection when:
+ // f1<=0 && f2<=0 or
+ // f1>=1 && f2>=1
+
+ return (f1>0f || f2>0) && (f1<1f || f2<1f);
+ }
+
+ return false;
+ }
+
/** Replies if two segments are intersecting.
+ * This function considers that the ends of
+ * the segments are not intersecting.
+ * To include the ends of the segments in the intersection ranges, see
+ * {@link #intersectsSegmentSegmentWithEnds(float, float, float, float, float, float, float, float)}.
*
* @param x1 is the first point of the first segment.
* @param y1 is the first point of the first segment.
@@ -388,15 +529,40 @@
* @param y4 is the second point of the second segment.
* @return <code>true</code> if the two shapes are intersecting; otherwise
* <code>false</code>
+ * @see #intersectsSegmentSegmentWithEnds(float, float, float, float, float, float, float, float)
*/
- public static boolean intersectsSegmentSegment(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
- return (MathUtil.ccw(x1, y1, x2, y2, x3, y3, false) *
- MathUtil.ccw(x1, y1, x2, y2, x4, y4, false) <= 0)
- &&
- (MathUtil.ccw(x3, y3, x4, y4, x1, y1, false) *
- MathUtil.ccw(x3, y3, x4, y4, x2, y2, false) <= 0);
+ public static boolean intersectsSegmentSegmentWithoutEnds(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
+ boolean r;
+ r = intersectsSSWoE(x1, y1, x2, y2, x3, y3, x4, y4);
+ if (!r) return r;
+ return intersectsSSWoE(x3, y3, x4, y4, x1, y1, x2, y2);
}
+ /** Replies if two segments are intersecting.
+ * This function considers that the ends of
+ * the segments are intersecting.
+ * To ignore the ends of the segments, see
+ * {@link #intersectsSegmentSegmentWithoutEnds(float, float, float, float, float, float, float, float)}.
+ *
+ * @param x1 is the first point of the first segment.
+ * @param y1 is the first point of the first segment.
+ * @param x2 is the second point of the first segment.
+ * @param y2 is the second point of the first segment.
+ * @param x3 is the first point of the second segment.
+ * @param y3 is the first point of the second segment.
+ * @param x4 is the second point of the second segment.
+ * @param y4 is the second point of the second segment.
+ * @return <code>true</code> if the two shapes are intersecting; otherwise
+ * <code>false</code>
+ * @see #intersectsSegmentSegmentWithoutEnds(float, float, float, float, float, float, float, float)
+ */
+ public static boolean intersectsSegmentSegmentWithEnds(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
+ boolean r;
+ r = intersectsSSWE(x1, y1, x2, y2, x3, y3, x4, y4);
+ if (!r) return r;
+ return intersectsSSWE(x3, y3, x4, y4, x1, y1, x2, y2);
+ }
+
/** X-coordinate of the first point. */
protected float ax = 0f;
/** Y-coordinate of the first point. */
@@ -710,7 +876,7 @@
@Override
public boolean intersects(Segment2f s) {
- return intersectsSegmentSegment(
+ return intersectsSegmentSegmentWithoutEnds(
getX1(), getY1(),
getX2(), getY2(),
s.getX1(), s.getY1(),
@@ -718,6 +884,21 @@
}
@Override
+ public boolean intersects(Path2f s) {
+ return intersects(s.getPathIterator());
+ }
+
+ @Override
+ public boolean intersects(PathIterator2f s) {
+ int mask = (s.getWindingRule() == PathWindingRule.NON_ZERO ? -1 : 2);
+ int crossings = Path2f.computeCrossingsFromSegment(
+ getPathIterator(),
+ getX1(), getY1(), getX2(), getY2());
+ return (crossings == MathConstants.SHAPE_INTERSECTS ||
+ (crossings & mask) != 0);
+ }
+
+ @Override
public String toString() {
StringBuilder b = new StringBuilder();
b.append("["); //$NON-NLS-1$
Modified: trunk/math/src/test/java/org/arakhne/afc/math/continous/object2d/Segment2fTest.java
===================================================================
--- trunk/math/src/test/java/org/arakhne/afc/math/continous/object2d/Segment2fTest.java 2013-04-05 10:04:20 UTC (rev 408)
+++ trunk/math/src/test/java/org/arakhne/afc/math/continous/object2d/Segment2fTest.java 2013-04-05 10:06:40 UTC (rev 409)
@@ -329,6 +329,17 @@
/**
*/
+ public static void testComputeCrossingsFromSegment_Others() {
+ assertEquals(
+ 0,
+ Segment2f.computeCrossingsFromSegment(
+ 0,
+ 7f, -5f, 1f, 1f,
+ 4f, -3f, 1f, 1f));
+ }
+
+ /**
+ */
public static void testComputeCrossingsFromSegment_0110() {
assertEquals(
0,
@@ -409,7 +420,7 @@
5f, -.01f, .75f, .5f));
assertEquals(
- MathConstants.SHAPE_INTERSECTS,
+ 1,
Segment2f.computeCrossingsFromSegment(
0,
0f, 1f, 1f, 0f,
@@ -505,7 +516,7 @@
20f, -5f, .75f, .5f));
assertEquals(
- MathConstants.SHAPE_INTERSECTS,
+ 1,
Segment2f.computeCrossingsFromSegment(
0,
1f, 0f, 0f, 1f,
@@ -917,39 +928,106 @@
/**
*/
- public static void testIntersectsSegmentSegment() {
- assertTrue(Segment2f.intersectsSegmentSegment(
+ public static void testIntersectsSegmentSegmentWithoutEnds() {
+ assertTrue(Segment2f.intersectsSegmentSegmentWithoutEnds(
0f, 0f, 1f, 1f,
+ 0f, .5f, 1f, .5f));
+ assertTrue(Segment2f.intersectsSegmentSegmentWithoutEnds(
+ 0f, 0f, 1f, 1f,
0f, 0f, 1f, 1f));
- assertTrue(Segment2f.intersectsSegmentSegment(
+ assertTrue(Segment2f.intersectsSegmentSegmentWithoutEnds(
0f, 0f, 1f, 1f,
0f, 0f, 2f, 2f));
- assertTrue(Segment2f.intersectsSegmentSegment(
+ assertTrue(Segment2f.intersectsSegmentSegmentWithoutEnds(
0f, 0f, 1f, 1f,
0f, 0f, .5f, .5f));
- assertTrue(Segment2f.intersectsSegmentSegment(
+ assertTrue(Segment2f.intersectsSegmentSegmentWithoutEnds(
0f, 0f, 1f, 1f,
-3f, -3f, .5f, .5f));
- assertTrue(Segment2f.intersectsSegmentSegment(
+ assertFalse(Segment2f.intersectsSegmentSegmentWithoutEnds(
0f, 0f, 1f, 1f,
-3f, -3f, 0f, 0f));
- assertFalse(Segment2f.intersectsSegmentSegment(
+ assertFalse(Segment2f.intersectsSegmentSegmentWithoutEnds(
0f, 0f, 1f, 1f,
-3f, -3f, -1f, -1f));
- assertTrue(Segment2f.intersectsSegmentSegment(
+ assertFalse(Segment2f.intersectsSegmentSegmentWithoutEnds(
0f, 0f, 1f, 1f,
-3f, 0f, 4f, 0f));
- assertFalse(Segment2f.intersectsSegmentSegment(
+ assertFalse(Segment2f.intersectsSegmentSegmentWithoutEnds(
0f, 0f, 1f, 1f,
+ -3f, -1f, 4f, -1f));
+
+ assertFalse(Segment2f.intersectsSegmentSegmentWithoutEnds(
+ 0f, 0f, 1f, 1f,
+ -3f, -1f, -1f, -1f));
+
+ assertFalse(Segment2f.intersectsSegmentSegmentWithoutEnds(
+ 0f, 0f, 1f, 1f,
-3f, 0f, -2f, 1f));
- assertFalse(Segment2f.intersectsSegmentSegment(
+ assertFalse(Segment2f.intersectsSegmentSegmentWithoutEnds(
0f, 0f, 1f, 1f,
10f, 0f, 9f, -1f));
+
+ assertFalse(
+ Segment2f.intersectsSegmentSegmentWithoutEnds(
+ 7f, -5f, 1f, 1f,
+ 4f, -3f, 1f, 1f));
}
+ /**
+ */
+ public static void testIntersectsSegmentSegmentWithEnds() {
+ assertTrue(Segment2f.intersectsSegmentSegmentWithEnds(
+ 0f, 0f, 1f, 1f,
+ 0f, .5f, 1f, .5f));
+ assertTrue(Segment2f.intersectsSegmentSegmentWithEnds(
+ 0f, 0f, 1f, 1f,
+ 0f, 0f, 1f, 1f));
+ assertTrue(Segment2f.intersectsSegmentSegmentWithEnds(
+ 0f, 0f, 1f, 1f,
+ 0f, 0f, 2f, 2f));
+ assertTrue(Segment2f.intersectsSegmentSegmentWithEnds(
+ 0f, 0f, 1f, 1f,
+ 0f, 0f, .5f, .5f));
+ assertTrue(Segment2f.intersectsSegmentSegmentWithEnds(
+ 0f, 0f, 1f, 1f,
+ -3f, -3f, .5f, .5f));
+ assertTrue(Segment2f.intersectsSegmentSegmentWithEnds(
+ 0f, 0f, 1f, 1f,
+ -3f, -3f, 0f, 0f));
+ assertFalse(Segment2f.intersectsSegmentSegmentWithEnds(
+ 0f, 0f, 1f, 1f,
+ -3f, -3f, -1f, -1f));
+
+ assertTrue(Segment2f.intersectsSegmentSegmentWithEnds(
+ 0f, 0f, 1f, 1f,
+ -3f, 0f, 4f, 0f));
+
+ assertFalse(Segment2f.intersectsSegmentSegmentWithEnds(
+ 0f, 0f, 1f, 1f,
+ -3f, -1f, 4f, -1f));
+
+ assertFalse(Segment2f.intersectsSegmentSegmentWithEnds(
+ 0f, 0f, 1f, 1f,
+ -3f, -1f, -1f, -1f));
+
+ assertFalse(Segment2f.intersectsSegmentSegmentWithEnds(
+ 0f, 0f, 1f, 1f,
+ -3f, 0f, -2f, 1f));
+
+ assertFalse(Segment2f.intersectsSegmentSegmentWithEnds(
+ 0f, 0f, 1f, 1f,
+ 10f, 0f, 9f, -1f));
+
+ assertTrue(
+ Segment2f.intersectsSegmentSegmentWithEnds(
+ 7f, -5f, 1f, 1f,
+ 4f, -3f, 1f, 1f));
+ }
+
@Override
public void testDistancePoint2D() {
assertEpsilonEquals(0f, this.r.distance(new Point2f(0f, 0f)));