l*********8 发帖数: 4642 | 1 A 2-D bounding box can represented as (Xmin, Xmax, Ymin, Ymax). We have a
set of bounding boxes. There is no intersection between any two of the
bounding boxes.
Now we want to insert one bounding box into the bounding boxes set and merge
the intersected bounding boxes if necessary. Two intersected boxes can be
merged into a big box like this:
Xmin = min(Xmin1, Xmin2); Xmax = max(Xmax1, Xmax2);
Ymin = min(Ymin1, Ymin2); Ymax = max(Ymax1, Ymax2);
Design an algorithm to do the insertion.
Example:
Exising bounding boxes set is { (1,4,0,2), (0,2,3,6) }
Bounding box to be inserted: (3,5,1,4)
Result: { (0, 5, 0, 6) } | b******u 发帖数: 81 | 2 递归。
public static List Insert(List boundBoxs, BoundBox boundBox)
{
List result = new List();
BoundBox bb = null;
int i;
for (i = 0; i < boundBoxs.Count(); i++)
{
bb = Merge(boundBoxs[i], boundBox);
if (bb != null)
{
break;
}
}
result.AddRange(boundBoxs);
if (bb == null)
{
result.Add(boundBox);
}
else
{
result.RemoveAt(i);
result = Insert(result, bb);
}
return result;
} | l*********8 发帖数: 4642 | 3 看了大概思路是对的。
这个算法复杂度是O(n^2)吧。 有没有更好的算法?
boundBox)
【在 b******u 的大作中提到】 : 递归。 : public static List Insert(List boundBoxs, BoundBox boundBox) : { : List result = new List(); : BoundBox bb = null; : int i; : for (i = 0; i < boundBoxs.Count(); i++) : { : bb = Merge(boundBoxs[i], boundBox); : if (bb != null)
| p*****2 发帖数: 21240 | 4
感觉很难比n^2好的。
【在 l*********8 的大作中提到】 : 看了大概思路是对的。 : 这个算法复杂度是O(n^2)吧。 有没有更好的算法? : : boundBox)
|
|