如何找到由各种 2D 矩形组合创建的边框长度？

Question

给定一组矩形，要求你确定由重叠矩形的轮廓形成的复杂多边形的周长。

Answer 1

我们从各个较小的重叠矩形的（所有 4 个点的）位置开始。
我们通过遍历各个矩形的角点来构造新的多边形。
我们找到矩阵的任何给定行或列遇到的最外围点（最远 North/South/East/West），将它们存储在单独的数组中。
一旦我们收集了新多边形的所有点，我们就会围绕网格中心按顺时针顺序对它的点进行排序（如果尚未排序）。
我们通过测量其表面上每条线（每组连续点之间）的距离并将其加到总数来测量其周长。

 .  .  .  .  .  .  .  .  .  .  .  .
 .  .  .  .  *  x  x  *  .  .  .  .
 .  .  .  .  x  .  .  x  .  .  .  .
 .  .  .  .  x  .  .  x  .  .  .  .
 .  .  *  z  *  z  .  x  .  .  .  .
 .  .  z  .  x  z  .  x  .  .  .  .
 .  .  z  .  x  z  .  x  .  .  .  .
 .  *  *  y  y  y  y  *  y  y  *  .
 .  y  z  .  x  z  .  x  .  .  y  .
 .  *  *  y  y  y  y  *  y  y  *  .
 .  .  z  .  x  z  .  x  .  .  .  .
 .  .  z  .  x  *  x  *  .  .  .  .
 .  .  z  .  .  z  .  .  .  .  .  .
 .  .  *  z  z  *  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .

在上图中，我们有矩形 x、y 和 z。星号是我们新多边形的边角。

Answer 2

矩形是否轴对齐？如果是这样，你可以试试这个。沿一个轴（假设为 x）排序开始和结束，然后维护一个连续间隔列表 - 点，按 y 排序，每个间隔都有一个整数 'winding number'（最初是 ymin..ymax，0）。然后，当您沿着 x 处理下一条边时，您会发现它与现有间隔重叠，将两端的间隔分开，并更新（++ 用于前缘，-- 用于后缘）它们的缠绕数。例如：

 0000111111122222111000
+000++++++++++000000000
=0001222222233222111000
    1                   (perimeter update)

对于开放的 eges，将绕组编号为 1 的新间隔添加到周边。对于关闭 - 为 0。为了提高效率，您还可以合并具有相同绕组数的区间。

然后对 y 做同样的事情。

Answer 3

在 Preparata 和 Shamos 的书 "Computational Geometry" 中，第 8 章专门讨论矩形并集问题。联合周长问题用扫线算法(link one link two)和线段树在O(NLogN)时间内解决

Addition

如何找到由各种 2D 矩形组合创建的边框长度？

How to find the border length created from a conglomeration of various 2D rectangles?

algorithm

geometry

computational-geometry