获取一组矩形的轮廓

Question

我正在寻找一种算法来获取由一组不重叠的矩形创建的图形的轮廓。该图可以是任何形状，但是它是简单连接的，即不包含孔。

我需要怎么写这样的一个功能的想法：

IEnumerable<Point> GetContour(IEnumerable<Rect> rects) 

算法的时间复杂度并不重要，它只是在合理的时间来执行。

Answer 1

我可能会在两遍中做到这一点。第一个将矩形转换为一组点（按照绕线顺序），包括另一个矩形的角点是沿着边缘的点。这样，您最终将得到一个点图，您可以轻松检测哪些点在哪些矩形之间共享。

因此，只需在图形中搜索没有共享矩形的第一个点，并沿着没有共享矩形的点开始步行路线，或者在前一个点没有共享矩形的情况下开始两个共享矩形，直到返回到起点。

您需要为您的路线维护一个堆栈，以及以前探索点的地图。

我刚刚刚刚做过这件事（虽然它不仅限于rects，而且我已经完成了第一次），它的工作原理非常好。我看到它能够在一秒钟内以更多次的时间计算出一条路线，而不是我可以用一个整数计算出来，所以表现看起来相当不错，尽管这是用C++编写的。

Answer 2

这似乎凹壳问题的一个特定情况..许多算法确实存在解决相反凸包问题：

• 贾维斯三月（wikipedia）为O（n^2）
• 格雷厄姆扫描（wikipedia）O（nlogn）

这些是最简单的，至少有3个，但他们只是优化性能，叔帽子不是你的主要目标之一。

我认为贾维斯3月可以很容易地适应你的情况，其中你只有矩形。考虑一下这样一个事实，即在每一段时间里，这个算法通常都会采用与计算的最后两点相交的线右侧的第一个点，所以如果有更好的选择规则，可以在特定情况下使其适应凹面的矩形。

在任何情况下也有一个特定的凹壳这里描述算法：link，你也可以下载他们的API here（这应该是描述算法的论文：link）