Trouver une intersection entre 2 segments

Bonjour tout le monde,

J'aimerai trouver le point d'intersection entre le segment AB et CD, voilà mon code:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Point2D.Double A = eye.get(0); Point2D.Double B = image.get(0); Point2D.Double C = eye.get(1); Point2D.Double D = image.get(1);   Point2D.Double I = new Point2D.Double((B.x - A.x), (B.y - A.y)); Point2D.Double J = new Point2D.Double((D.x - C.x), (D.y - C.y));   double m = 0; double diviseur = (I.x * J.y - I.y * J.x);   if(diviseur != 0) { m = (I.x * A.y - I.x * C.y - I.y * A.x + I.y * C.x ) / diviseur; }   Point2D.Double point = new Point2D.Double(C.x + m * J.x, C.y + m * J.y);

---

Ça fonctionne presque, le résultat n'est pas très précis surtout lorsque les points A et C sont alignés.
Une idée?

Salut,

Extrait de mes vielles bibliothèques :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

import java.awt.geom.Point2D;   public class GeometryAwtUtils {   /**          * Compute the intersection between two line segments, or two lines of          * infinite length.          */ public static Point2D getSegmentLineIntersections(Point2D s1p1, Point2D s1p2, Point2D s2p1, Point2D s2p2) {   double x0 = s1p1.getX(); double y0 = s1p1.getY(); double x1 = s1p2.getX(); double y1 = s1p2.getY();   double x2 = s2p1.getX(); double y2 = s2p1.getY(); double x3 = s2p2.getX(); double y3 = s2p2.getY();   double[] intersection = new double[2]; int r = Geometry.findLineSegmentIntersection(x0, y0, x1, y1, x2, y2, x3, y3, intersection);   Point2D result; if ( r==1 || r==0 ) { result=new Point2D.Double(intersection[0],intersection[1]); } else { result=null; } return result;   }   }

---

Si tu veux que l'intersection appartienne à l'un des segments, il faut éliminer le cas r=0 :

Code:

---

1 2 3 4 5 6 7 8 9

Point2D result; if ( r==1 ) { result=new Point2D.Double(intersection[0],intersection[1]); } else { result=null; } return result;

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235

/**  * Excerpt.  *  */ public class Geometry { /**          * Compute the intersection between two line segments, or two lines of          * infinite length.          *          * @param x0          *            X coordinate first end point first line segment.          * @param y0          *            Y coordinate first end point first line segment.          * @param x1          *            X coordinate second end point first line segment.          * @param y1          *            Y coordinate second end point first line segment.          * @param x2          *            X coordinate first end point second line segment.          * @param y2          *            Y coordinate first end point second line segment.          * @param x3          *            X coordinate second end point second line segment.          * @param y3          *            Y coordinate second end point second line segment.          * @param intersection          *            [2] Preallocated by caller to double[2]          * @return -1 if lines are parallel (x,y unset), -2 if lines are parallel          *         and overlapping (x, y center) 0 if intesrection outside segments          *         (x,y set) +1 if segments intersect (x,y set)          */ public static int findLineSegmentIntersection(double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3, double[] intersection) { // TODO: Make limit depend on input domain final double LIMIT = 1e-5; final double INFINITY = 1e10;   double x, y;   // // Convert the lines to the form y = ax + b //   // Slope of the two lines double a0 = Geometry.equals(x0, x1, LIMIT) ? INFINITY : (y0 - y1) / (x0 - x1); double a1 = Geometry.equals(x2, x3, LIMIT) ? INFINITY : (y2 - y3) / (x2 - x3);   double b0 = y0 - a0 * x0; double b1 = y2 - a1 * x2;   // Check if lines are parallel if (Geometry.equals(a0, a1)) { if (!Geometry.equals(b0, b1)) return -1; // Parallell non-overlapping   else { if (Geometry.equals(x0, x1)) { if (Math.min(y0, y1) < Math.max(y2, y3) || Math.max(y0, y1) > Math.min(y2, y3)) { double twoMiddle = y0 + y1 + y2 + y3 - Geometry.min(y0, y1, y2, y3) - Geometry.max(y0, y1, y2, y3); y = (twoMiddle) / 2.0; x = (y - b0) / a0; } else return -1; // Parallell non-overlapping } else { if (Math.min(x0, x1) < Math.max(x2, x3) || Math.max(x0, x1) > Math.min(x2, x3)) { double twoMiddle = x0 + x1 + x2 + x3 - Geometry.min(x0, x1, x2, x3) - Geometry.max(x0, x1, x2, x3); x = (twoMiddle) / 2.0; y = a0 * x + b0; } else return -1; }   intersection[0] = x; intersection[1] = y; return -2; } }   // Find correct intersection point if (Geometry.equals(a0, INFINITY)) { x = x0; y = a1 * x + b1; } else if (Geometry.equals(a1, INFINITY)) { x = x2; y = a0 * x + b0; } else { x = -(b0 - b1) / (a0 - a1); y = a0 * x + b0; }   intersection[0] = x; intersection[1] = y;   // Then check if intersection is within line segments double distanceFrom1; if (Geometry.equals(x0, x1)) { if (y0 < y1) distanceFrom1 = y < y0 ? Geometry.length(x, y, x0, y0) : y > y1 ? Geometry.length(x, y, x1, y1) : 0.0; else distanceFrom1 = y < y1 ? Geometry.length(x, y, x1, y1) : y > y0 ? Geometry.length(x, y, x0, y0) : 0.0; } else { if (x0 < x1) distanceFrom1 = x < x0 ? Geometry.length(x, y, x0, y0) : x > x1 ? Geometry.length(x, y, x1, y1) : 0.0; else distanceFrom1 = x < x1 ? Geometry.length(x, y, x1, y1) : x > x0 ? Geometry.length(x, y, x0, y0) : 0.0; }   double distanceFrom2; if (Geometry.equals(x2, x3)) { if (y2 < y3) distanceFrom2 = y < y2 ? Geometry.length(x, y, x2, y2) : y > y3 ? Geometry.length(x, y, x3, y3) : 0.0; else distanceFrom2 = y < y3 ? Geometry.length(x, y, x3, y3) : y > y2 ? Geometry.length(x, y, x2, y2) : 0.0; } else { if (x2 < x3) distanceFrom2 = x < x2 ? Geometry.length(x, y, x2, y2) : x > x3 ? Geometry.length(x, y, x3, y3) : 0.0; else distanceFrom2 = x < x3 ? Geometry.length(x, y, x3, y3) : x > x2 ? Geometry.length(x, y, x2, y2) : 0.0; }   return Geometry.equals(distanceFrom1, 0.0) && Geometry.equals(distanceFrom2, 0.0) ? 1 : 0; }   /**          * Compute the length of the line from (x0,y0) to (x1,y1)          *          * @param x0          *            , y0 First line end point.          * @param x1          *            , y1 Second line end point.          * @return Length of line from (x0,y0) to (x1,y1).          */ public static double length(double x0, double y0, double x1, double y1) { double dx = x1 - x0; double dy = y1 - y0;   return Math.sqrt(dx * dx + dy * dy); }   /**          * Check if two double precision numbers are "equal", i.e. close enough to a          * given limit.          *          * @param a          *            First number to check          * @param b          *            Second number to check          * @param limit          *            The definition of "equal".          * @return True if the twho numbers are "equal", false otherwise          */ public static boolean equals(double a, double b, double limit) { return Math.abs(a - b) < limit; }   /**          * Check if two double precision numbers are "equal", i.e. close enough to a          * prespecified limit.          *          * @param a          *            First number to check          * @param b          *            Second number to check          * @return True if the twho numbers are "equal", false otherwise          */ public static boolean equals(double a, double b) { return equals(a, b, 1.0e-5); }   /**          * Return largest of four numbers.          *          * @param a          *            First number to find largest among.          * @param b          *            Second number to find largest among.          * @param c          *            Third number to find largest among.          * @param d          *            Fourth number to find largest among.          * @return Largest of a, b, c and d.          */ public static double max(double a, double b, double c, double d) { return Math.max(Math.max(a, b), Math.max(c, d)); }   /**          * Return smallest of four numbers.          *          * @param a          *            First number to find smallest among.          * @param b          *            Second number to find smallest among.          * @param c          *            Third number to find smallest among.          * @param d          *            Fourth number to find smallest among.          * @return Smallest of a, b, c and d.          */ public static double min(double a, double b, double c, double d) { return Math.min(Math.min(a, b), Math.min(c, d)); }   /**          * Construct the vector specified by two points.          *          * @param p0          *            , p1 Points the construct vector between [x,y,z].          * @return v Vector from p0 to p1 [x,y,z].          */ public static double[] createVector(double[] p0, double[] p1) { double v[] = { p1[0] - p0[0], p1[1] - p0[1], p1[2] - p0[2] }; return v; }   }

---

PS Tu devrais poser ce genre de questions dans le forum Mathématiques & Algorithmes, c'est plus adapté.

Il ne manque pas un truc Joel ?

Code:

---

Geometry.findLineSegmentIntersection(x0, y0, x1, y1, x2, y2, x3, y3, intersection);

---

Citation:

---

Envoyé par wax78

Il ne manque pas un truc Joel ?

---

Faut cliquer sur le bouton [Montrer]. Le code est assez long, alors pour éviter un post de 3 km, j'ai mis le code de base (non AWT, donc réutilisable (perso je l'utilise (aussi) en SWT)) en spoiler. Et encore, la classe que j'utilise est beaucoup plus longue, j'y ai compilé tout un tas de méthodes glannées ici ou là, ou perso, avec tous les trucs de géométrie utiles (intersections, projections, appartenance, etc × segment/ligne, cercle, rectangle, polygone... et plein d'autres trucs)

Oups j'avais pas vu sorry.