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
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
| /// <summary>
/// Calcule l'union de plusieurs rectangles (quand ceux-ci s'intersectent)
/// </summary>
/// <param name="rectangles">Une liste de rectangles</param>
/// <returns>Une liste de polygones (un polygone = un tableau de points)</returns>
public List<Point[]> compute(List<Rectangle> rectangles)
{
List<Point[]> result = new List<Point[]>();
List<Rectangle> intRectangles = new List<Rectangle>(rectangles);
while (intRectangles.Count > 0)
{
// Conversion du rectangle en polygone, puis destruction du rectangle:
Point[] polygon = getPolygon(intRectangles[0]);
intRectangles.RemoveAt(0);
// On réitére sur tous les rectangles tant que le polygone en absorbe:
bool changeRecorded = true;
while (changeRecorded)
{
changeRecorded = false;
for (int i = 0; (i < intRectangles.Count) && (polygon != null); i++)
{
Rectangle rect = intRectangles[i];
// Union du polygone courant et d'un rectangle
if (union(ref polygon, rect))
{
// Si le polygone a absorbé le rectangle, on supprime le rectangle
intRectangles.RemoveAt(i--);
changeRecorded = true;
}
}
}
if (polygon != null)
{
// Fermeture du polygone avant stockage:
closePolygon(ref polygon);
result.Add(polygon);
}
}
return result;
}
/// <summary>
/// Convertit un rectangle en un polygone (non fermé)
/// </summary>
/// <param name="rect">Le rectangle à convertir</param>
/// <returns>Un tableau de points correspondant au polygone</returns>
private Point[] getPolygon(Rectangle rect)
{
Point[] result = new Point[4];
result[0] = new Point(rect.Left, rect.Top);
result[1] = new Point(rect.Right, rect.Top);
result[2] = new Point(rect.Right, rect.Bottom);
result[3] = new Point(rect.Left, rect.Bottom);
return result;
}
/// <summary>
/// Ferme un polygone
/// </summary>
/// <param name="polygon">Le polygone à fermer</param>
private void closePolygon(ref Point[] polygon)
{
// Fermeture du polygone (si nécessaire)
if ((polygon.Length > 0) && (polygon[polygon.Length - 1] != polygon[0]))
{
Point[] result = new Point[polygon.Length + 1];
polygon.CopyTo(result, 0);
result[polygon.Length] = result[0];
polygon = result;
}
}
/// <summary>
/// Effectue l'union entre un polygone et un rectangle.
/// Le polygone est modifié si besoin est (extension lors de l'absorption du rectangle).
/// Si le polygone devient null, ça veut dire que le rectangle le contient entièrement.
/// </summary>
/// <param name="polygon">Le polygone</param>
/// <param name="rect">Le rectangle à ajouter</param>
/// <returns>true: le rectangle a été absorbé par le polygone, false sinon (intersection vide)</returns>
private bool union(ref Point[] polygon, Rectangle rect)
{
// Recherche d'un point du polygone HORS du rectangle:
int startPoint = -1;
for (int i = 0; (i < polygon.Length) && (startPoint == -1); i++)
{
if (!isInRectangle(polygon[i], rect))
{
startPoint = i;
}
}
if (startPoint == -1)
{
// Si tout le polygone est contenu dans le rectangle,
// alors le polygone disparait mais le rectangle reste:
polygon = null;
return false;
}
else
{
Point[] rectPolygon = getPolygon(rect);
// Verification de l'intersection entre le polygone et le rectangle
// S'il y a intersection: Modifier le polygone si besoin, puis retourner true
// Pas d'intersection : retourner false
List<Point> points = new List<Point>();
bool result = false;
bool pIntersectIsValid = false;
Point pIntersect = new Point();
int point = startPoint;
// Pour chaque point du polygone:
do
{
int rectIndex;
if (!pIntersectIsValid)
{
// Calcul de l'intersection entre le cote courant du polygone et le rectangle:
addPoint(points, polygon[point]);
rectIndex = intersect(polygon[point], polygon[(point + 1) % polygon.Length], rectPolygon, ref pIntersect);
}
else
{
// Calcul de l'intersection entre un tronçon du coté courant du polygone et le rectangle:
pIntersectIsValid = false;
rectIndex = intersect(pIntersect, polygon[(point + 1) % polygon.Length], rectPolygon, ref pIntersect);
}
if (rectIndex != -1)
{
// Cette arête du polygone croise le rectangle (le rectangle va être absorbé):
result = true;
addPoint(points, pIntersect);
pIntersectIsValid = true;
// Pour chaque arête du rectangle:
do
{
int polyIndex = pIntersectIsValid ?
intersect(pIntersect, rectPolygon[(rectIndex + 1) % rectPolygon.Length], polygon, ref pIntersect) :
intersect(rectPolygon[rectIndex], rectPolygon[(rectIndex + 1) % rectPolygon.Length], polygon, ref pIntersect);
rectIndex = (rectIndex + 1) % rectPolygon.Length;
if (polyIndex != -1)
{
// L'arête du rectangle croise à nouveau le polygone:
addPoint(points, pIntersect);
point = polyIndex - 1;
pIntersectIsValid = true;
}
else
{
// Ajout du coin du rectangle dans le polygone résultant:
addPoint(points, rectPolygon[rectIndex]);
pIntersectIsValid = false;
}
}
while (!pIntersectIsValid);
}
point = (point + 1) % polygon.Length;
}
while (point != startPoint);
polygon = points.ToArray();
// Si le rectangle n'a pas d'intersection ET qu'il est entièrement contenu dans le polygone,
// alors le rectangle disparait
return (result | isInPolygon(rectPolygon, polygon));
}
}
/// <summary>
/// Ajoute un point à la liste de points de manière optimale.
/// </summary>
/// <param name="points">Liste de points</param>
/// <param name="point">Point à ajouter</param>
private void addPoint(List<Point> points, Point point)
{
if (points.Count > 1)
{
Point prePrevious = points[points.Count - 2];
if ((prePrevious.X == point.X) || (prePrevious.Y == point.Y))
{
// Si le point à ajouter est dans l'alignement des 2 derniers,
// le nouveau point remplace directement le dernier point stocké:
points[points.Count - 1] = point;
return;
}
}
if ((points.Count == 0) || (points[points.Count - 1] != point))
{
// Ajout du point que s'il n'est pas égal au dernier point stocké (doublon contigu):
points.Add(point);
}
}
/// <summary>
/// Indique si un point est à l'interieur d'un rectangle ou non.
/// </summary>
/// <param name="p">Point contenu (ou non)</param>
/// <param name="polygon">Rectangle contenant (ou non)</param>
/// <returns>true: Le point est à l'intérieur, false sinon</returns>
private bool isInRectangle(Point p, Rectangle rect)
{
return (p.X >= rect.X && p.X <= rect.Right && p.Y >= rect.Y && p.Y <= rect.Bottom);
}
/// <summary>
/// Indique si un polygone est entièrement contenu dans un polygone (convexe) ou non.
/// </summary>
/// <param name="polygon1">Polygone contenu (ou non)</param>
/// <param name="polygon2">Polygone contenant (ou non)</param>
/// <returns>true: Le polygone est entièrement à l'intérieur, false sinon</returns>
private bool isInPolygon(Point[] polygon1, Point[] polygon2)
{
for (int i = 0; i < polygon1.Length; i++)
{
if (!isInPolygon(polygon1[i], polygon2))
{
return false;
}
}
return true;
}
/// <summary>
/// Indique si un point est à l'interieur d'un polygone ou non.
/// </summary>
/// <param name="p">Point contenu (ou non)</param>
/// <param name="polygon">Polygone contenant (ou non)</param>
/// <returns>true: Le point est à l'intérieur, false sinon</returns>
private bool isInPolygon(Point p, Point[] polygon)
{
int count = 0;
for (int i = 0; i < polygon.Length; i++)
{
Point p2a = polygon[i];
Point p2b = polygon[(i + 1) % polygon.Length];
int minY = (p2a.Y < p2b.Y) ? p2a.Y : p2b.Y;
int maxY = (p2a.Y >= p2b.Y) ? p2a.Y : p2b.Y;
int maxX = (p2a.X >= p2b.X) ? p2a.X : p2b.X;
if ((p.Y > minY) && (p.Y < maxY) && (p.X <= maxX))
{
count++;
}
}
return ((count % 2) != 0);
}
/// <summary>
/// Calcule l'intersection entre 1 segment et 1 polygone.
/// </summary>
/// <param name="p1a">1ere extrémité du segment</param>
/// <param name="p1b">2eme extrémité du segment</param>
/// <param name="polygon">Polygone</param>
/// <param name="result">Point d'intersection si celui-ci a été trouvé</param>
/// <returns>Index du point précédent le point d'intersection trouvé, -1 sinon</returns>
private int intersect(Point pa, Point pb, Point[] polygon, ref Point result)
{
for (int i = 0; i < polygon.Length; i++)
{
if ((intersect(pa, pb, polygon[i], polygon[(i + 1) % polygon.Length], ref result)) &&
(isOrtho(pa, pb, polygon[i], polygon[(i + 1) % polygon.Length])))
{
return i;
}
}
return -1;
}
/// <summary>
/// Calcule l'intersection entre 2 segments (UNIQUEMENT verticaux ou horizontaux).
/// </summary>
/// <param name="p1a">1ere extrémité du 1er segment</param>
/// <param name="p1b">2eme extrémité du 1er segment</param>
/// <param name="p2a">1ere extrémité du 2eme segment</param>
/// <param name="p2b">2eme extrémité du 2eme segment</param>
/// <param name="result">Point d'intersection si celui-ci a été trouvé</param>
/// <returns>true: un point d'intersection est trouvé, false sinon</returns>
private bool intersect(Point p1a, Point p1b, Point p2a, Point p2b, ref Point result)
{
if (p1a.X == p1b.X)
{
// p1 Vertical, p2 Horizontal:
Point p1Min = (p1a.Y < p1b.Y) ? p1a : p1b;
Point p1Max = (p1a.Y >= p1b.Y) ? p1a : p1b;
Point p2Min = (p2a.X < p2b.X) ? p2a : p2b;
Point p2Max = (p2a.X >= p2b.X) ? p2a : p2b;
if (((p1Min.X >= p2Min.X) && (p1Min.X <= p2Max.X)) &&
((p1Min.Y <= p2Min.Y) && (p1Max.Y >= p2Min.Y)))
{
result = new Point(p1a.X, p2a.Y);
return true;
}
}
else
{
// p1 Horizontal, p2 Vertical:
Point p1Min = (p1a.X < p1b.X) ? p1a : p1b;
Point p1Max = (p1a.X >= p1b.X) ? p1a : p1b;
Point p2Min = (p2a.Y < p2b.Y) ? p2a : p2b;
Point p2Max = (p2a.Y >= p2b.Y) ? p2a : p2b;
if ((p1Min.Y >= p2Min.Y) && (p1Min.Y <= p2Max.Y) &&
(p1Min.X <= p2Min.X) && (p1Max.X >= p2Min.X))
{
result = new Point(p2a.X, p1a.Y);
return true;
}
}
return false;
}
/// <summary>
/// Verifie si 2 segments sont orthonormés.
/// </summary>
/// <param name="p1a">1ere extrémité du 1er segment</param>
/// <param name="p1b">2eme extrémité du 1er segment</param>
/// <param name="p2a">1ere extrémité du 2ème segment</param>
/// <param name="p2b">2eme extrémité du 2ème segment</param>
/// <returns>true: les 2 segments sont orthonormés, false sinon</returns>
private bool isOrtho(Point p1a, Point p1b, Point p2a, Point p2b)
{
int u1 = p1b.X - p1a.X;
int u2 = p1b.Y - p1a.Y;
int v1 = p2b.X - p2a.X;
int v2 = p2b.Y - p2a.Y;
// Le produit vectoriel doit être < 0 (sens anti-horaire)
return (u1 * v2 - u2 * v1) < 0;
} |
