Trouver une intersection entre 2 segments

**Pecose** · 06/02/2020, 12h26

Bonjour tout le monde,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

**joel.drigo** · 06/02/2020, 14h21

Salut,

Extrait de mes vielles bibliothèques :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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é.

**wax78** · 06/02/2020, 14h39

Il ne manque pas un truc Joel ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**joel.drigo** · 06/02/2020, 15h28

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)

**wax78** · 06/02/2020, 16h17

Oups j'avais pas vu sorry.

Trouver une intersection entre 2 segments

avec Java

Vue hybride

Discussions similaires

Partager

Partager