---------------------------------------------------
//已发布改进后的轮廓问题算法：http://www.cnblogs.com/andyzeng/p/3683498.html
---------------------------------------------------
对于城市中几座建筑外形，给出这些建筑的二维轮廓。
每个建筑的输入为 L H R，其中L，R分辨代表建筑在水平线上的左右x坐标，H表示建筑的高度。在图形上，一个建筑就是一个条形图。
建筑随机输入，请设计一个算法能够输出所有建筑所产生的轮廓线。
输入建筑的文件内容格式为，粗体格式为建筑高度：
10 110 50
20 60 70
30 130 90
120 70 160
140 30 250
190 180 220
230 130 290
240 40 280
输入轮廓的文件内容格式为，粗体格式为轮廓高度：10 110 30 130 90 0 120 70 160 30 190 180 220 30 230 130 290 0
解答如下：
给出建筑类和轮廓线上点的定义：
public class Building
{
public Building(int x1, int h, int x2)
{
X1 = x1;
H = h;
X2 = x2;
}
public int X1 { get; set; }
public int H { get; set; }
public int X2 { get; set; }
} //轮廓线上点的定义
public class Point
{
public Point(double x, int y)
{
X = x;
Y = y;
}
public double X { get; set; }
public int Y { get; set; }
}
初始化输入，按照一定要求随机生成建筑
public static Building[] initBuildings(int buildCount, int leftLimitInclusive, int maxHeightLimitInclusive, int rightLimitInclusive)
{
Building[] buildings = new Building[buildCount];
Random rndRange = new Random(DateTime.Now.Millisecond);
Random rndHeight = new Random(DateTime.Now.Millisecond);
for (int i = ; i < buildCount; i++)
{
int l = rndRange.Next(leftLimitInclusive, rightLimitInclusive);
int r = rndRange.Next(l + , rightLimitInclusive + );
int h = rndHeight.Next(, maxHeightLimitInclusive + );
Building bld = new Building(l, h, r);
buildings[i] = bld;
}
return buildings;
}
运用分治法\divide and conquer 来进行建筑两两合并，然后将产生的轮廓线再进行两两合并
public static List<Point> MergeBuildings(Building[] blds, int leftIndex, int rightIndex)
{
if (rightIndex - leftIndex <= )//one or two buildings
{
return mergeTwoBuildingsImpl(blds[leftIndex], blds[rightIndex]);
}
else
{
int middle = (rightIndex + leftIndex) / ;
List<Point> firstOutlines = MergeBuildings(blds, leftIndex, middle);
List<Point> secondOutlines = MergeBuildings(blds, middle + , rightIndex);
return mergeTwoOutLinesImpl(firstOutlines, secondOutlines);
}
}
其中建筑合并的时候考虑两个建筑的相对横坐标（L和R）和纵坐标（高H）的关系。
private static List<Point> mergeTwoBuildingsImpl(Building first, Building second)
{
Building left, right;
if (Math.Min(first.X1, second.X1) == second.X1)
{
left = second;
right = first;
}
else
{
left = first;
right = second;
}
List<Point> points = new List<Point>();
#region Lx1<Lx2<=Rx1<Rx2
if (left.X2 <= right.X1)
{
if (left.X2 < right.X1)
{
points.AddRange(
new List<Point>()
{
new Point(left.X1,),
new Point(left.X1,left.H),
new Point(left.X2,left.H),
new Point(left.X2,),
new Point(right.X1,),
new Point(right.X1,right.H),
new Point(right.X2,right.H),
new Point(right.X2,),
});
}
else//==
{
if (left.H == right.H)
{
points.AddRange(
new List<Point>()
{
new Point(left.X1,),
new Point(left.X1,left.H),
new Point(right.X2,right.H),
new Point(right.X2,),
});
}
else
{
points.AddRange(
new List<Point>()
{
new Point(left.X1,),
new Point(left.X1,left.H),
new Point(left.X2,left.H),
new Point(right.X1,right.H),
new Point(right.X2,right.H),
new Point(right.X2,),
});
}
}
}
#endregion
#region Lx1<=Rx1<Lx2<=Rx2
if (left.X1 <= right.X1 && right.X1 < left.X2 && left.X2 <= right.X2)
{
if (left.X1 < right.X1 && left.X2 < right.X2)
{
if (left.H < right.H)
{
points.AddRange(
new List<Point>()
{
new Point(left.X1,),
new Point(left.X1,left.H),
new Point(right.X1,left.H),
new Point(right.X1,right.H),
new Point(right.X2,right.H),
new Point(right.X2,),
});
}
else if (left.H > right.H)
{
points.AddRange(
new List<Point>()
{
new Point(left.X1,),
new Point(left.X1,left.H),
new Point(left.X2,left.H),
new Point(left.X2,right.H),
new Point(right.X2,right.H),
new Point(right.X2,),
});
}
else//==
{
points.AddRange(
new List<Point>()
{
new Point(left.X1,),
new Point(left.X1,left.H),
new Point(right.X2,right.H),
new Point(right.X2,),
});
}
}
if (left.X1 == right.X1 && left.X2 < right.X2)
{
if (left.H <= right.H)
{
points.AddRange(
new List<Point>()
{
new Point(right.X1,),
new Point(right.X1,right.H),
new Point(right.X2,right.H),
new Point(right.X2,),
});
}
else
{
points.AddRange(
new List<Point>()
{
new Point(left.X1,),
new Point(left.X1,left.H),
new Point(left.X2,left.H),
new Point(left.X2,right.H),
new Point(right.X2,right.H),
new Point(right.X2,),
});
}
}
if (left.X1 < right.X1 && left.X2 == right.X2)
{
if (left.H >= right.H)
{
points.AddRange(
new List<Point>()
{
new Point(left.X1,),
new Point(left.X1,left.H),
new Point(left.X2,left.H),
new Point(left.X2,),
});
}
else
{
points.AddRange(
new List<Point>()
{
new Point(left.X1,),
new Point(left.X1,left.H),
new Point(right.X1,left.H),
new Point(right.X1,right.H),
new Point(right.X2,right.H),
new Point(right.X2,),
});
}
}
if (left.X1 == right.X1 && left.X2 == right.X2)
{
points.AddRange(
new List<Point>()
{
new Point(right.X1,),
new Point(right.X1,Math.Max(left.H,right.H)),
new Point(right.X2,Math.Max(left.H,right.H)),
new Point(right.X2,),
});
}
}
#endregion
#region Lx1<=Rx1<Rx2<=Lx2
if (left.X1 <= right.X1 && right.X2 <= left.X2)
{
//if (left.X1 == right.X1 && right.X2 == left.X2)
//{
// points.AddRange(
// new List<Point>()
// {
// new Point(right.X1,0),
// new Point(right.X1,Math.Max(left.H,right.H)),
// new Point(right.X2,Math.Max(left.H,right.H)),
// new Point(right.X2,0),
// });
//}
if (left.X1 < right.X1 && right.X2 < left.X2)
{
if (right.H <= left.H)
{
points.AddRange(
new List<Point>()
{
new Point(left.X1,),
new Point(left.X1,left.H),
new Point(left.X2,left.H),
new Point(left.X2,),
});
}
else
{
points.AddRange(
new List<Point>()
{
new Point(left.X1,),
new Point(left.X1,left.H),
new Point(right.X1,left.H),
new Point(right.X1,right.H),
new Point(right.X2,right.H),
new Point(right.X2,left.H),
new Point(left.X2,left.H),
new Point(left.X2,),
});
}
}
//if (left.X1 < right.X1 && right.X2 == left.X2)
//{
// if (right.H <= left.H)
// {
// points.AddRange(
// new List<Point>()
// {
// new Point(left.X1,0),
// new Point(left.X1,left.H),
// new Point(left.X2,left.H),
// new Point(left.X2,0),
// });
// }
// else
// {
// points.AddRange(
// new List<Point>()
// {
// new Point(left.X1,0),
// new Point(left.X1,left.H),
// new Point(right.X1,left.H),
// new Point(right.X1,right.H),
// new Point(right.X2,right.H),
// new Point(right.X2,0),
// });
// }
//}
if (left.X1 == right.X1 && right.X2 < left.X2)
{
if (right.H <= left.H)
{
points.AddRange(
new List<Point>()
{
new Point(left.X1,),
new Point(left.X1,left.H),
new Point(left.X2,left.H),
new Point(left.X2,),
});
}
else
{
points.AddRange(
new List<Point>()
{
new Point(right.X1,),
new Point(right.X1,right.H),
new Point(right.X2,right.H),
new Point(right.X2,left.H),
new Point(left.X2,left.H),
new Point(left.X2,),
});
}
}
}
#endregion
return points;
}
合并两个轮廓线
private static List<Point> mergeTwoOutLinesImpl(List<Point> L1, List<Point> L2)
{
int cursorL = ;
int cursorR = ;
int min = Convert.ToInt32(Math.Min(L1[].X, L2[].X));
int max = Convert.ToInt32(Math.Max(L1.Last().X, L2.Last().X));
List<Point> points = new List<Point>();
points.Add(new Point(min, ));
for (double x = min; x <= max; x = x + 0.5)
{
int y1 = -, y2 = -;
if (cursorL <= L1.Count - )
{
if (L1[cursorL].X == x && L1[cursorL].X == L1[cursorL + ].X)
{
y1 = Math.Max(L1[cursorL].Y, L1[cursorL + ].Y);
cursorL = cursorL + ; }
else if (x > L1[].X && x < L1[cursorL].X)
{
y1 = L1[cursorL].Y;
}
}
if (cursorR <= L2.Count - )
{
if (L2[cursorR].X == x && L2[cursorR].X == L2[cursorR + ].X)
{
y2 = Math.Max(L2[cursorR].Y, L2[cursorR + ].Y);
cursorR = cursorR + ; }
else if (x > L2[].X && x < L2[cursorR].X)
{
y2 = L2[cursorR].Y;
}
} if (points.Count >= )
{
//当前水平线上已经存在两个等高的点，此时只需修改第二个点的x坐标以延伸水平线，此种情况不需要拐点
if (points[points.Count - ].Y == points[points.Count - ].Y && points[points.Count - ].Y == Math.Max(y1, y2))
{
points[points.Count - ].X = x;
}
else//此时需添加拐点，分为两种情况，一种是新添加的点与拐点x坐标相同，另一种是y坐标相同
{
//第一种情况，新的y值大于上一个点的y
if (Math.Max(y1, y2) > points[points.Count - ].Y)
{
if (points[points.Count - ].Y == points[points.Count - ].Y)
{
points[points.Count - ].X = x;//水平线上已经存在两个点，改造第二个点x坐标到拐点位置
}
else
{
points.Add(new Point(x, points[points.Count - ].Y));//新拐点
}
}
//第二种情况，新的y值小于上一个点的y
if (Math.Max(y1, y2) < points[points.Count - ].Y)
{
points.Add(new Point(points[points.Count - ].X, Math.Max(y1, y2)));//新拐点
}
points.Add(new Point(x, Math.Max(y1, y2)));//添加水平线的第2个点
}
}
else
{
points.Add(new Point(x, Math.Max(y1, y2)));
}
}
points.Add(new Point(max, ));
return points;
}
//算法的调用方法，随机生成10万个建筑，其中x坐标范围为1-2000，高度不超过50。
static void Main(string[] args)
{
Building[] blds = OutLineUtility.initBuildings(, , , );
MergeBuildings(blds);
Console.ReadKey();
}
public static void MergeBuildings(Building[] blds)
{
Stopwatch sw = new Stopwatch();
Console.WriteLine("Start 1st Algorithm!");
sw.Start();
List<Point> result = OutLineUtility.MergeBuildings(blds, , blds.Length - );
sw.Stop();
Console.WriteLine("Complete!Execution time:{0}s", sw.Elapsed.TotalSeconds); Console.Write("Calculated outline:");
OutputOutlineToConsole(result);
Console.WriteLine();
}
private static void OutputOutlineToConsole(List<Point> result)
{
for (int i = ; i < result.Count; i++)
{
if (i % == )
{
Console.Write(result[i].X);
Console.Write(" ");
}
if (i % == )
{
Console.Write(result[i].Y);
Console.Write(" ");
}
}
}
方法一完毕。
另外考虑，是否可以把输入的建筑看成是轮廓线，这样在分治法里面直接合并轮廓线(试验得知，此方法比上面的方法要慢)
调用算法二的方法
Console.WriteLine("Start 2nd Algorithm!");
sw.Restart();
List<Point>[] Lps = new List<Point>[blds.Length];
for (int i = ; i < blds.Length; i++)
{
Lps[i] = OutLineUtility.convertSingleBuilding2Outline(blds[i]);
}
result = OutLineUtility.MergeBuildings2(Lps, , blds.Length - );
sw.Stop();
Console.WriteLine("Complete!Execution time:{0}s", sw.Elapsed.TotalSeconds);
Console.Write("Calculated outline:");
OutputOutlineToConsole(result);
Console.WriteLine();算法主体
public static List<Point> MergeBuildings2(List<Point>[] bldsOutline, int leftIndex, int rightIndex)
{
if (rightIndex - leftIndex <= )//one or two buildings
{
return mergeTwoOutLinesImpl(bldsOutline[leftIndex], bldsOutline[rightIndex]);
}
else
{
int middle = (rightIndex + leftIndex) / ;
List<Point> firstOutlines = MergeBuildings2(bldsOutline, leftIndex, middle);
List<Point> secondOutlines = MergeBuildings2(bldsOutline, middle + , rightIndex);
return mergeTwoOutLinesImpl(firstOutlines, secondOutlines);
}
}
public static List<Point> convertSingleBuilding2Outline(Building bld)
{
return new List<Point>()
{
new Point(bld.X1,),
new Point(bld.X1,bld.H),
new Point(bld.X2,bld.H),
new Point(bld.X2,),
}; }
方法二完毕。
下载源码。
作者：Andy Zeng
欢迎任何形式的转载，但请务必注明出处。