---------------------------------------------------
//已发布改进后的轮廓问题算法：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 = 0; i < buildCount; i++) { int l = rndRange.Next(leftLimitInclusive, rightLimitInclusive); int r = rndRange.Next(l + 1, rightLimitInclusive + 1); int h = rndHeight.Next(1, maxHeightLimitInclusive + 1); 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 <= 1)//one or two buildings { return mergeTwoBuildingsImpl(blds[leftIndex], blds[rightIndex]); } else { int middle = (rightIndex + leftIndex) / 2; List<Point> firstOutlines = MergeBuildings(blds, leftIndex, middle); List<Point> secondOutlines = MergeBuildings(blds, middle + 1, 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,0), new Point(left.X1,left.H), new Point(left.X2,left.H), new Point(left.X2,0), new Point(right.X1,0), new Point(right.X1,right.H), new Point(right.X2,right.H), new Point(right.X2,0), }); } else//== { if (left.H == right.H) { points.AddRange( new List<Point>() { new Point(left.X1,0), new Point(left.X1,left.H), new Point(right.X2,right.H), new Point(right.X2,0), }); } else { points.AddRange( new List<Point>() { new Point(left.X1,0), 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,0), }); } } } #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,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), }); } else if (left.H > right.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,right.H), new Point(right.X2,right.H), new Point(right.X2,0), }); } else//== { points.AddRange( new List<Point>() { new Point(left.X1,0), new Point(left.X1,left.H), new Point(right.X2,right.H), new Point(right.X2,0), }); } } if (left.X1 == right.X1 && left.X2 < right.X2) { if (left.H <= right.H) { points.AddRange( new List<Point>() { new Point(right.X1,0), new Point(right.X1,right.H), new Point(right.X2,right.H), new Point(right.X2,0), }); } else { 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,right.H), new Point(right.X2,right.H), new Point(right.X2,0), }); } } if (left.X1 < right.X1 && left.X2 == right.X2) { if (left.H >= right.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 && left.X2 == right.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), }); } } #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,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,left.H), new Point(left.X2,left.H), new Point(left.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,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,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(right.X1,0), 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,0), }); } } } #endregion return points; }
合并两个轮廓线
private static List<Point> mergeTwoOutLinesImpl(List<Point> L1, List<Point> L2) { int cursorL = 0; int cursorR = 0; int min = Convert.ToInt32(Math.Min(L1[0].X, L2[0].X)); int max = Convert.ToInt32(Math.Max(L1.Last().X, L2.Last().X)); List<Point> points = new List<Point>(); points.Add(new Point(min, 0)); for (double x = min; x <= max; x = x + 0.5) { int y1 = -1, y2 = -1; if (cursorL <= L1.Count - 2) { if (L1[cursorL].X == x && L1[cursorL].X == L1[cursorL + 1].X) { y1 = Math.Max(L1[cursorL].Y, L1[cursorL + 1].Y); cursorL = cursorL + 2; } else if (x > L1[0].X && x < L1[cursorL].X) { y1 = L1[cursorL].Y; } } if (cursorR <= L2.Count - 2) { if (L2[cursorR].X == x && L2[cursorR].X == L2[cursorR + 1].X) { y2 = Math.Max(L2[cursorR].Y, L2[cursorR + 1].Y); cursorR = cursorR + 2; } else if (x > L2[0].X && x < L2[cursorR].X) { y2 = L2[cursorR].Y; } } if (points.Count >= 3) { //当前水平线上已经存在两个等高的点，此时只需修改第二个点的x坐标以延伸水平线，此种情况不需要拐点 if (points[points.Count - 1].Y == points[points.Count - 2].Y && points[points.Count - 1].Y == Math.Max(y1, y2)) { points[points.Count - 1].X = x; } else//此时需添加拐点，分为两种情况，一种是新添加的点与拐点x坐标相同，另一种是y坐标相同 { //第一种情况，新的y值大于上一个点的y if (Math.Max(y1, y2) > points[points.Count - 1].Y) { if (points[points.Count - 1].Y == points[points.Count - 2].Y) { points[points.Count - 1].X = x;//水平线上已经存在两个点，改造第二个点x坐标到拐点位置 } else { points.Add(new Point(x, points[points.Count - 1].Y));//新拐点 } } //第二种情况，新的y值小于上一个点的y if (Math.Max(y1, y2) < points[points.Count - 1].Y) { points.Add(new Point(points[points.Count - 1].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, 0)); return points; }
//算法的调用方法，随机生成10万个建筑，其中x坐标范围为1-2000，高度不超过50。
static void Main(string[] args) { Building[] blds = OutLineUtility.initBuildings(100000, 1, 50, 2000); 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, 0, blds.Length - 1); 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 = 0; i < result.Count; i++) { if (i % 2 == 0) { Console.Write(result[i].X); Console.Write(" "); } if (i % 2 == 1) { 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 = 0; i < blds.Length; i++) { Lps[i] = OutLineUtility.convertSingleBuilding2Outline(blds[i]); } result = OutLineUtility.MergeBuildings2(Lps, 0, blds.Length - 1); 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 <= 1)//one or two buildings { return mergeTwoOutLinesImpl(bldsOutline[leftIndex], bldsOutline[rightIndex]); } else { int middle = (rightIndex + leftIndex) / 2; List<Point> firstOutlines = MergeBuildings2(bldsOutline, leftIndex, middle); List<Point> secondOutlines = MergeBuildings2(bldsOutline, middle + 1, rightIndex); return mergeTwoOutLinesImpl(firstOutlines, secondOutlines); } } public static List<Point> convertSingleBuilding2Outline(Building bld) { return new List<Point>() { new Point(bld.X1,0), new Point(bld.X1,bld.H), new Point(bld.X2,bld.H), new Point(bld.X2,0), }; }
方法二完毕。
下载源码。
作者：Andy Zeng
欢迎任何形式的转载，但请务必注明出处。