5

我正在尝试计算矩形联合的周长，其中我有左下角和右上角的点。每个矩形都位于 x 轴上（每个矩形的左下角是 (x, 0)）。我一直在研究不同的方法，似乎 Sweep-Line 算法是最好的方法。我也看过 Graham Scan。我的目标是 O(n log n) 算法。老实说，虽然我迷失了如何继续，我希望这里的人可以尽最大努力为我简化它并尝试帮助我准确理解如何实现这一点。

我从我所做的研究中收集到的一些东西：

我们需要对这些点进行排序（我不确定我们对它们进行排序的标准）。

我们将分而治之（达到 O (log n)）。

我们需要计算交叉点（最好的方法是什么？）

我们需要某种数据结构来保存这些点（也许是二叉树？）

我最终将在 Java 中实现这个算法。

4

2 回答 2

4

该算法是很多繁琐的案例分析。不是超级复杂，但很难完全正确。

假设所有矩形都按左下角和右上角 (x0, y0, x1, y1) 存储在数组 A 中。因此，我们可以将矩形的任何边表示为一对 (e, i)，其中 e \in {L, R, T, B} 表示左、右、上、下边，i 表示 A[i]。将所有对 (L, i) 放入起始列表 S 中，并在 A[i].x0 上对其进行排序。

我们还需要一条扫描线 C，它是一个三元组 (T, i, d) 的顶部边缘和底部的 (B, i, d) 的 BST。这里 i 是矩形索引，d 是整数深度，如下所述。BST 的关键是边缘的 y 坐标。最初它是空的。

请注意，您可以随时按顺序遍历 C 并确定扫描线的哪些部分被矩形隐藏而不是隐藏。通过保持深度计数器来做到这一点，最初为零。从最小 y 到最大，当遇到底边时，计数器加 1。当您看到顶部边缘时，减 1。对于计数器为零的区域，扫描线可见。否则它被一个矩形隐藏。

现在你从来没有真正完成整个遍历。相反，您可以通过逐步保持深度来提高效率。C 中每个三元组的 d 元素是其上方区域的深度。（C 中第一条边下方的区域的深度始终为 0。）

最后，我们需要一个输出寄存器 P。它存储一组折线（边的双向链表很方便），并允许查询形式为“给我所有的折线，其末端的 y 坐标落在范围 [y0.. y1]。算法的一个属性是，这些折线总是有两条水平边与扫描线交叉作为它们的末端，而所有其他边都在扫描线的左侧。此外，没有两条折线相交。它们是输出的片段多边形“正在建设中。”请注意，输出多边形可能不是简单的，由多个“循环”和“孔”组成。另一个 BST 将为 P 做。它最初也是空的。

现在算法看起来大致是这样的。我不会偷走弄清楚细节的所有乐趣。

 while there are still edges in S
   Let V = leftmost vertical edge taken from S
   Determine Vv, the intersection of V with the visible parts of C
   if V is of the form (L, i) // a left edge
     Update P with Vv (polylines may be added or joined)
     add (R, i) to S
     add (T, i) and (B, i) to C, incrementing depths as needed
   else // V is of the form (R, i) // a right edge
     Update P with Vv (polylines may be removed or joined)
     remove (T, i) and (B, i) from C, decrementing depths as needed

随着 P 的更新，您将生成复杂的多边形。最右边的边缘应该关闭最后一个循环。

最后，请注意重合边缘会产生一些棘手的特殊情况。当您遇到这些时，请再次发布，我们可以讨论。

排序的运行时间当然是 O(n log n)，但更新扫描线的成本取决于可以重叠的多边形数量：退化情况为 O(n) 或整个计算为 O(n^2) .

祝你好运。我已经实现了这个算法（几年前）和其他一些类似的算法。它们是严格的逻辑案例分析中的巨大练习。非常令人沮丧，但在您获胜时也会有所收获。

于 2015-09-23T03:10:23.290 回答
1

在此处输入图像描述

诀窍是首先找到沿 x 轴的每个段的最大高度（见上图）。一旦你知道了这一点，那么周界就很容易了：

注意：我没有测试过代码，所以可能有错别字。

// Calculate perimeter given the maxY at each line segment.
double calcPerimeter(List<Double> X, List<Double> maxY) {
    double perimeter = 0;

    for(int i = 1; i < X.size(); i++){
        // Add the left side of the rect, maxY[0] == 0
        perimeter += Math.abs(maxY.get(i) - maxY.get(i - 1))

        // add the top of the rect
        perimeter += X.get(i) - X.get(i-1);
    }

    // Add the right side and return total perimeter
    return perimeter + maxY.get(maxY.size() - 1);
}

综上所述，您需要先计算X和maxY。完整的代码如下所示：

double calcUnionPerimeter(Set<Rect> rects){
    // list of x points, with reference to Rect
    List<Entry<Double, Rect>> orderedList = new ArrayList<>();

    // create list of all x points
    for(Rect rect : rects){
        orderedList.add(new Entry(rect.getX(), rect));
        orderedList.add(new Entry(rect.getX() + rect.getW(), rect));
    }

    // sort list by x points 
    Collections.sort(orderedList, new Comparator<Entry<Double,Rect>>(){
        @Override int compare(Entry<Double, Rect> p1, Entry<Double, Rect> p2) {
            return Double.compare(p1.getKey(), p2.getKey());
        }
    });

    // Max PriorityQueue based on Rect height
    Queue<Rect> maxQ = new PriorityQueue<>(orderedList, new Comparator<Rect>(){
        @Override int compare(Rect r1, Rect r2) {
            return Double.compare(r1.getH(), r2.getH());
        }
    }

    List<Double> X = new ArrayList<>();
    List<Double> maxY = new ArrayList<>();

    // loop through list, building up X and maxY
    for(Entry<Double, Rect> e : orderedList) {
        double x = e.getKey();
        double rect = e.getValue();
        double isRightEdge = x.equals(rect.getX() + rect.getW());

        X.add(x);
        maxY.add(maxQ.isEmpty() ? 0 : maxQ.peek().getY());

        if(isRightEdge){ 
            maxQ.dequeue(rect);   // remove rect from queue
        } else {         
            maxQ.enqueue(rect);   // add rect to queue
        }
    }

    return calcPerimeter(X, maxY);
}
于 2015-09-23T16:48:38.883 回答