| [Arakhnę-Dev] [412] * Fixing intersection test between an ellipse and a line or a line segment . |
[ Thread Index |
Date Index
| More arakhne.org/dev Archives
]
Revision: 412
Author: galland
Date: 2013-04-05 22:39:23 +0200 (Fri, 05 Apr 2013)
Log Message:
-----------
* Fixing intersection test between an ellipse and a line or a line segment.
Modified Paths:
--------------
trunk/math/src/main/java/org/arakhne/afc/math/continous/object2d/Ellipse2f.java
trunk/math/src/test/java/org/arakhne/afc/math/continous/object2d/Ellipse2fTest.java
Modified: trunk/math/src/main/java/org/arakhne/afc/math/continous/object2d/Ellipse2f.java
===================================================================
--- trunk/math/src/main/java/org/arakhne/afc/math/continous/object2d/Ellipse2f.java 2013-04-05 10:09:47 UTC (rev 411)
+++ trunk/math/src/main/java/org/arakhne/afc/math/continous/object2d/Ellipse2f.java 2013-04-05 20:39:23 UTC (rev 412)
@@ -150,145 +150,119 @@
/** Replies if an ellipse and a line are intersecting.
*
- * @param x1 is the first corner of the ellipse.
- * @param y1 is the first corner of the ellipse.
- * @param x2 is the second corner of the ellipse.
- * @param y2 is the second corner of the ellipse.
- * @param x3 is the first point of the line.
- * @param y3 is the first point of the line.
- * @param x4 is the second point of the line.
- * @param y4 is the second point of the line.
+ * @param ex is the lowest corner of the ellipse.
+ * @param ey is the lowest corner of the ellipse.
+ * @param ew is the width of the ellipse.
+ * @param eh is the height of the ellipse.
+ * @param x1 is the first point of the line.
+ * @param y1 is the first point of the line.
+ * @param x2 is the second point of the line.
+ * @param y2 is the second point of the line.
* @return <code>true</code> if the two shapes are intersecting; otherwise
* <code>false</code>
+ * @see http://blog.csharphelper.com/2012/09/24/calculate-where-a-line-segment-and-an-ellipse-intersect-in-c.aspx
*/
- public static boolean intersectsEllipseLine(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
- float a = (x2 - x1) / 2f;
- float b = (y2 - y1) / 2f;
- float h = x1 + a; // h is center of ellipse
- float k = y1 + b; // k is center of ellipse
+ public static boolean intersectsEllipseLine(float ex, float ey, float ew, float eh, float x1, float y1, float x2, float y2) {
+ // If the ellipse or line segment are empty, return no intersections.
+ if (eh<=0f || ew<=0f || x1==x2 || y1==y2) {
+ return false;
+ }
- float aas = a*a;
- float bbs = b*b;
+ // Get the semimajor and semiminor axes.
+ float a = ew / 2f;
+ float b = eh / 2f;
- float aa, bb, cc;
+ // Translate so the ellipse is centered at the origin.
+ float ecx = ex + a;
+ float ecy = ey + b;
+ float px1 = x1 - ecx;
+ float py1 = y1 - ecy;
+ float px2 = x2 - ecx;
+ float py2 = y2 - ecy;
+
+ float sq_a = a*a;
+ float sq_b = b*b;
+ float vx = px2 - px1;
+ float vy = py2 - py1;
+
+ assert(sq_a!=0f && sq_b!=0f);
- if (x3!=x4) {
- float m = (y4-y3)/(x4-x3);
- float c = y3 - m*x3;
- //
- aa = bbs + aas*m*m;
- bb = 2*aas*c*m - 2*aas*k*m - 2*h*bbs;
- cc = bbs*h*h + aas*c*c - 2*aas*k*c + aas*k*k - aas*bbs;
- }
- else {
- //
- // vertical line case
- //
- aa = aas;
- bb = -2f*k*aas;
- cc = -aas*bbs + bbs*(x3-h)*(x3-h);
- }
+ // Calculate the quadratic parameters.
+ float A = vx * vx / sq_a +
+ vy * vy / sq_b;
+ float B = 2f * px1 * vx / sq_a +
+ 2f * py1 * vy / sq_b;
+ float C = px1 * px1 / sq_a + py1 * py1 / sq_b - 1;
- float d = bb*bb-4*aa*cc;
- return (d > 0f);
+ // Calculate the discriminant.
+ float discriminant = B * B - 4f * A * C;
+ return (discriminant>=0f);
}
/** Replies if an ellipse and a segment are intersecting.
*
- * @param x1 is the first corner of the ellipse.
- * @param y1 is the first corner of the ellipse.
- * @param x2 is the second corner of the ellipse.
- * @param y2 is the second corner of the ellipse.
- * @param x3 is the first point of the segment.
- * @param y3 is the first point of the segment.
- * @param x4 is the second point of the segment.
- * @param y4 is the second point of the segment.
+ * @param ex is the lowest corner of the ellipse.
+ * @param ey is the lowest corner of the ellipse.
+ * @param ew is the width of the ellipse.
+ * @param eh is the height of the ellipse.
+ * @param x1 is the first point of the segment.
+ * @param y1 is the first point of the segment.
+ * @param x2 is the second point of the segment.
+ * @param y2 is the second point of the segment.
* @return <code>true</code> if the two shapes are intersecting; otherwise
* <code>false</code>
+ * @see http://blog.csharphelper.com/2012/09/24/calculate-where-a-line-segment-and-an-ellipse-intersect-in-c.aspx
*/
- public static boolean intersectsEllipseSegment(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
- if (x1==x2 || y1==y2) return false;
-
- float a = (x2 - x1) / 2f;
- float b = (y2 - y1) / 2f;
- float h = x1 + a; // h is center of ellipse
- float k = y1 + b; // k is center of ellipse
+ public static boolean intersectsEllipseSegment(float ex, float ey, float ew, float eh, float x1, float y1, float x2, float y2) {
+ // If the ellipse or line segment are empty, return no intersections.
+ if (eh<=0f || ew<=0f || x1==x2 || y1==y2) {
+ return false;
+ }
- float aas = a*a;
- float bbs = b*b;
+ // Get the semimajor and semiminor axes.
+ float a = ew / 2f;
+ float b = eh / 2f;
- float aa, bb, cc;
+ // Translate so the ellipse is centered at the origin.
+ float ecx = ex + a;
+ float ecy = ey + b;
+ float px1 = x1 - ecx;
+ float py1 = y1 - ecy;
+ float px2 = x2 - ecx;
+ float py2 = y2 - ecy;
- float m = Float.NaN;
+ float sq_a = a*a;
+ float sq_b = b*b;
+ float vx = px2 - px1;
+ float vy = py2 - py1;
+
+ assert(sq_a!=0f && sq_b!=0f);
- if (x3!=x4) {
- m = (y4-y3)/(x4-x3);
- float c = y3 - m*x3;
- //
- aa = bbs + aas*m*m;
- bb = 2*aas*c*m - 2*aas*k*m - 2*h*bbs;
- cc = bbs*h*h + aas*c*c - 2*aas*k*c + aas*k*k - aas*bbs;
+ // Calculate the quadratic parameters.
+ float A = vx * vx / sq_a + vy * vy / sq_b;
+ float B = 2f * px1 * vx / sq_a + 2f * py1 * vy / sq_b;
+ float C = px1 * px1 / sq_a + py1 * py1 / sq_b - 1;
+
+ // Calculate the discriminant.
+ float discriminant = B * B - 4f * A * C;
+ if (discriminant<0f) {
+ // No solution
+ return false;
}
- else {
- //
- // vertical line case
- //
- aa = aas;
- bb = -2f*k*aas;
- cc = -aas*bbs + bbs*(x3-h)*(x3-h);
+
+ if (discriminant==0f) {
+ // One real solution.
+ float t = -B / 2f / A;
+ return ((t >= 0f) && (t <= 1f));
}
- float d = bb*bb-4*aa*cc;
- if (d > 0f) {
- // Intersection exists between the ellipse and the line.
- float rootd = (float)Math.sqrt(d);
- float aa2 = aa*2f;
-
- float root1 = (-bb + rootd) / aa2;
- float root2 = (-bb - rootd) / aa2;
-
- // Intersection points are (xi1;yi1) and (xi2;yi2)
- float xi1, xi2, yi1, yi2;
-
- if (Float.isNaN(m)) {
- // Vertical line
- xi1 = xi2 = x1;
- yi1 = root1;
- yi2 = root2;
- }
- else {
- xi1 = root1;
- xi2 = root2;
- yi1 = y1 + m * (xi1 - x1);
- yi2 = y1 + m * (xi2 - x1);
- }
-
- // Compute the relative position of the roots again the segment coordinates
- // Reuse aa and bb as temp vars.
- // Reuse d as the length of the segment.
- // Reuse a and b as the length of the two roots.
- aa = x4 - x3;
- bb = y4 - y3;
- d = aa*aa + bb*bb;
- aa = xi1 - x3;
- bb = yi1 - y3;
- a = aa*aa + bb*bb;
- aa = xi2 - x3;
- bb = yi2 - y3;
- b = aa*aa + bb*bb;
-
- if (b<a) {
- // Ensure root1 and root2 are ordered
- aa = a;
- a = b;
- b = aa;
- }
-
- // Test intersection of 1D segments [a;b] and [0;d]
- // No intersection when: ( b<=0f ) || ( a>=d )
- return ( b>0f ) && ( a<d );
- }
- return false;
+ assert(discriminant>0f);
+
+ // Two real solutions.
+ float t1 = (-B + (float)Math.sqrt(discriminant)) / 2f / A;
+ float t2 = (-B - (float)Math.sqrt(discriminant)) / 2f / A;
+
+ return (t1>=0 || t2>=0) && (t1<=1 || t2<=1);
}
/** Replies if two ellipses are intersecting.
@@ -410,7 +384,7 @@
x, y,
getMinX(), getMinY(), getWidth(), getHeight());
}
-
+
@Override
public boolean contains(Rectangle2f r) {
return containsEllipseRectangle(
@@ -427,7 +401,7 @@
getMinX(), getMinY(),
getWidth(), getHeight());
}
-
+
@Override
public PathIterator2f getPathIterator(Transform2D transform) {
if (transform==null) {
@@ -497,7 +471,7 @@
public boolean intersects(Segment2f s) {
return intersectsEllipseSegment(
getMinX(), getMinY(),
- getMaxX(), getMaxY(),
+ getWidth(), getHeight(),
s.getX1(), s.getY1(),
s.getX2(), s.getY2());
}
@@ -506,7 +480,7 @@
public boolean intersects(Path2f s) {
return intersects(s.getPathIterator());
}
-
+
@Override
public boolean intersects(PathIterator2f s) {
int mask = (s.getWindingRule() == PathWindingRule.NON_ZERO ? -1 : 2);
@@ -539,14 +513,14 @@
* @mavenartifactid $ArtifactId$
*/
public static class CopyPathIterator implements PathIterator2f {
-
+
private final float x1;
private final float y1;
private final float w;
private final float h;
private int index;
private float lastX, lastY;
-
+
/**
* @param x1
* @param y1
@@ -573,7 +547,7 @@
if (this.index>5) throw new NoSuchElementException();
int idx = this.index;
++this.index;
-
+
if (idx==0) {
float ctrls[] = CTRL_PTS[3];
this.lastX = this.x1 + ctrls[4] * this.w;
@@ -611,7 +585,7 @@
public PathWindingRule getWindingRule() {
return PathWindingRule.NON_ZERO;
}
-
+
}
/**
@@ -621,7 +595,7 @@
* @mavenartifactid $ArtifactId$
*/
public static class TransformPathIterator implements PathIterator2f {
-
+
private final Point2D lastPoint = new Point2f();
private final Point2D ptmp1 = new Point2f();
private final Point2D ptmp2 = new Point2f();
@@ -631,7 +605,7 @@
private final float w;
private final float h;
private int index;
-
+
/**
* @param x1
* @param y1
@@ -660,7 +634,7 @@
if (this.index>5) throw new NoSuchElementException();
int idx = this.index;
++this.index;
-
+
if (idx==0) {
float ctrls[] = CTRL_PTS[3];
this.lastPoint.set(
@@ -709,7 +683,7 @@
public PathWindingRule getWindingRule() {
return PathWindingRule.NON_ZERO;
}
-
+
}
-
+
}
\ No newline at end of file
Modified: trunk/math/src/test/java/org/arakhne/afc/math/continous/object2d/Ellipse2fTest.java
===================================================================
--- trunk/math/src/test/java/org/arakhne/afc/math/continous/object2d/Ellipse2fTest.java 2013-04-05 10:09:47 UTC (rev 411)
+++ trunk/math/src/test/java/org/arakhne/afc/math/continous/object2d/Ellipse2fTest.java 2013-04-05 20:39:23 UTC (rev 412)
@@ -412,6 +412,45 @@
-5f, -5f, .1f, .1f));
assertTrue(Ellipse2f.intersectsEllipseLine(0f, 0f, 1f, 1f,
-5f, -5f, .4f, .3f));
+
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.7773438f, -3.0272121f, 6.7890625f, -3.1188917f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.7890625f, -3.1188917f, 6.8007812f, -3.2118688f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.8007812f, -3.2118688f, 6.8125f, -3.3061523f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.8125f, -3.3061523f, 6.8242188f, -3.401752f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.8242188f, -3.401752f, 6.8359375f, -3.4986773f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.8359375f, -3.4986773f, 6.8476562f, -3.5969372f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.8476562f, -3.5969372f, 6.859375f, -3.6965408f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.859375f, -3.6965408f, 6.8710938f, -3.7974977f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.8710938f, -3.7974977f, 6.8828125f, -3.8998175f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.8828125f, -3.8998175f, 6.8945312f, -4.003509f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.8945312f, -4.003509f, 6.90625f, -4.1085815f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.90625f, -4.1085815f, 6.9179688f, -4.2150445f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.9179688f, -4.2150445f, 6.9296875f, -4.3229074f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.9296875f, -4.3229074f, 6.9414062f, -4.4321795f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.9414062f, -4.4321795f, 6.953125f, -4.5428696f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.953125f, -4.5428696f, 6.9648438f, -4.6549873f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.9648438f, -4.6549873f, 6.9765625f, -4.7685423f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.9765625f, -4.7685423f, 6.9882812f, -4.8835435f));
+ assertTrue(Ellipse2f.intersectsEllipseLine(
+ 6f, -5f, 1f, 2f, 6.9882812f, -4.8835435f, 7f, -5f));
}
/**
@@ -439,6 +478,45 @@
-5f, -5f, .1f, .1f));
assertTrue(Ellipse2f.intersectsEllipseSegment(0f, 0f, 1f, 1f,
-5f, -5f, .4f, .3f));
+
+ assertFalse(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.7773438f, -3.0272121f, 6.7890625f, -3.1188917f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.7890625f, -3.1188917f, 6.8007812f, -3.2118688f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.8007812f, -3.2118688f, 6.8125f, -3.3061523f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.8125f, -3.3061523f, 6.8242188f, -3.401752f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.8242188f, -3.401752f, 6.8359375f, -3.4986773f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.8359375f, -3.4986773f, 6.8476562f, -3.5969372f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.8476562f, -3.5969372f, 6.859375f, -3.6965408f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.859375f, -3.6965408f, 6.8710938f, -3.7974977f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.8710938f, -3.7974977f, 6.8828125f, -3.8998175f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.8828125f, -3.8998175f, 6.8945312f, -4.003509f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.8945312f, -4.003509f, 6.90625f, -4.1085815f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.90625f, -4.1085815f, 6.9179688f, -4.2150445f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.9179688f, -4.2150445f, 6.9296875f, -4.3229074f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.9296875f, -4.3229074f, 6.9414062f, -4.4321795f));
+ assertTrue(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.9414062f, -4.4321795f, 6.953125f, -4.5428696f));
+ assertFalse(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.953125f, -4.5428696f, 6.9648438f, -4.6549873f));
+ assertFalse(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.9648438f, -4.6549873f, 6.9765625f, -4.7685423f));
+ assertFalse(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.9765625f, -4.7685423f, 6.9882812f, -4.8835435f));
+ assertFalse(Ellipse2f.intersectsEllipseSegment(
+ 6f, -5f, 1f, 2f, 6.9882812f, -4.8835435f, 7f, -5f));
}
}
\ No newline at end of file