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)];
}
} |
Partager