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
| public class Rectangle
{
public float x;
public float y;
public float w;
public float h;
public Rectangle(float X, float Y, float W, float H)
{
x = X; y = Y; w = W; h = H;
}
public override string ToString()
{
return "(X:" + x + ", Y:" + y + ", W:" + w + ", H:" + h + ")";
}
}
class RectanglePartition
{
IntervalPartition xPartition;
IntervalPartition yPartition;
Rectangle[,] grid;
float epsilon = 1e-6f; // epsilon utilisé à cause des erreurs lors des comparaisons de flottants.
public RectanglePartition(Rectangle[] rectangles)
{
// On suppose que les rectangles donnés forment bien une partition d'un plus grand rectangle
List<float> xPartitionList = new List<float>();
List<float> yPartitionList = new List<float>();
for (int i=0; i<rectangles.Length; i++)
{
// Pour chaque rectangle
int indexPartition;
// Ajout du côté gauche
for (indexPartition = 0; indexPartition < xPartitionList.Count; indexPartition++)
if (xPartitionList[indexPartition] >= rectangles[i].x * (1 - epsilon))
break;
if(indexPartition == xPartitionList.Count || Math.Abs(xPartitionList[indexPartition] - rectangles[i].x) > epsilon)
xPartitionList.Insert(indexPartition, rectangles[i].x);
// Ajout du côté haut
for (indexPartition = 0; indexPartition < yPartitionList.Count; indexPartition++)
if (yPartitionList[indexPartition] >= rectangles[i].y * (1-epsilon))
break;
if (indexPartition == yPartitionList.Count || Math.Abs(yPartitionList[indexPartition] - rectangles[i].y) > epsilon)
yPartitionList.Insert(indexPartition, rectangles[i].y);
// Ajout du côté droit
for (indexPartition = 0; indexPartition < xPartitionList.Count; indexPartition++)
if (xPartitionList[indexPartition] >= (rectangles[i].x + rectangles[i].w) * (1 - epsilon))
break;
if (indexPartition == xPartitionList.Count || Math.Abs(xPartitionList[indexPartition] - (rectangles[i].x + rectangles[i].w)) > epsilon)
xPartitionList.Insert(indexPartition, rectangles[i].x + rectangles[i].w);
// Ajout du côté bas
for (indexPartition = 0; indexPartition < yPartitionList.Count; indexPartition++)
if (yPartitionList[indexPartition] >= (rectangles[i].y + rectangles[i].h) * (1 - epsilon))
break;
if (indexPartition == yPartitionList.Count || Math.Abs(yPartitionList[indexPartition] - (rectangles[i].y + rectangles[i].h)) > epsilon)
yPartitionList.Insert(indexPartition, rectangles[i].y + rectangles[i].h);
}
xPartition = new IntervalPartition(xPartitionList.ToArray());
yPartition = new IntervalPartition(yPartitionList.ToArray());
grid = new Rectangle[xPartitionList.Count-1, yPartitionList.Count-1];
// On remplit le tableau pour référencer chaque rectangle.
foreach(Rectangle rectangle in rectangles)
{
int xStart = xPartition.GetIntervalOf(rectangle.x);
int yStart = yPartition.GetIntervalOf(rectangle.y);
int xEnd = xPartition.GetIntervalOf(rectangle.x + rectangle.w);
int yEnd = yPartition.GetIntervalOf(rectangle.y + rectangle.h);
for (int x = xStart; x < xEnd; x++)
for (int y = yStart; y < yEnd; y++)
grid[x, y] = rectangle;
}
}
public Rectangle GetRectangleOf(float x, float y)
{
return grid[xPartition.GetIntervalOf(x), xPartition.GetIntervalOf(y)];
}
} |
Trouver efficacement à quel intervalle appartient un élément
:
)
Répondre avec citation
Envoyé par anapurna
en bas à droite du message.
.
Partager