C++ 中的扫描线算法

2025年5月13日 | 阅读 13 分钟

扫描线算法在计算几何学领域有着广泛的应用，包括线段交点查找、矩形并集计算、**面积计算**、**最近点对**查找以及**多边形三角剖分**等。事实上，该课程特别强调了在三维空间中解决从三维扫描问题。**扫描线算法**由于其通用性、效率和吸引力，对计算几何学产生了重大影响。

扫描线算法是计算几何学的基础。这种表达方式在提及时间或地点与直线、曲面或图相关时非常受欢迎。扫描线概念是扫描线算法的核心：一个投射到几何空间中的假想投影，看起来有点像时钟的指针。当前线移动时，它会以不同的方式接触自然风景，展示出令人惊叹的几何图案。这些里程碑可以是区间的开始、区间的交集创建，或者第三种，其他更特殊的事件。

为了**高效地**管理这些事件，扫描线算法通常使用两种主要的数据结构：处理事件队列和**状态结构**。事件队列包含所有事件点，按照它们在x和y坐标（二维空间的情况下）中的位置排序。分割是处理数据成不同部分的操作，每次都能以**有序的方式**执行事件。

方法 1：使用优先队列

扫描线算法在**计算几何学**中有广泛的应用，这是通过扫描线过程实现的，该过程对问题进行了分割和分类。接下来，优先队列数据结构处理这些算法的**重复方面**，并将扫描线中的所有内容以排序的方式加载，这也大大提高了**速度和准确性**。因此，可以轻松处理大量的事件或几何问题可解的事件时间。

**扫描线：** 扫描线算法的原理是**假想的直线**穿过我们几何对象所占据的空间，并像我们实际拾取东西一样对其进行扫描。当扫描线遇到可能导致分析或**计算**中特定步骤的事件或区间时，它会停止在该事件或区间上。

**事件处理：** 这些可以是区间的开始或结束、区间的碎片、碰撞以及任何其他几何事件。正确地近似这些个体是解决**几何事物**问题的关键时刻。

**优先队列：** 优先队列是数据结构的一个重要实现，它维护一个元素集合并返回优先级最高（或最低）的元素。对于扫描线算法，它使得**优先队列**如此有用，因为要处理的事件是根据当前扫描线索引排序的。这导致了事件的分割，提高了编写算法时的清晰度，并且实现也变得简单。

程序

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// Structure to represent an event
struct Event {
    int position;   //Position along the sweep line
    bool isStart;   // Flag indicating whether it's the start of a segment or not
    int segmentIndex;   //Index of the segment in the input array
    Event(int pos, bool start, int index) : position(pos), isStart(start), segmentIndex(index) {}
    // Custom comparison operator for sorting in the priority queue
    bool operator<(const Event& other) const {
        // Sort events based on Position along the sweep line
        // In case of a tie, prioritize start events over end events
        if (position == other.position)
            return isStart && !other.isStart; // Start event comes first if tied
        return position < other.position;
    }
};
// Structure to represent a line segment
struct Segment {
    int start;  // Starting point of the segment
    int end;    // Ending point of the segment
    Segment(int s, int e) : start(s), end(e) {}
};
// Function to find intersections using sweep line algorithm
vector<pair<int, int>> findIntersections(vector<Segment>& segments) {
    vector<pair<int, int>> intersections;   // Store intersections found
    priority_queue<Event> events;   // Priority queue to manage events
    // Populate the priority queue with events (start and end points of segments)
    for (int i = 0; i < segments.size(); ++i) {
        events.push(Event(segments[i].start, true, i));  // Start event
        events.push(Event(segments[i].end, false, i));   // End event
    }
    int activeSegments = 0; //Number of active segments at any point along the sweep line
    // Process events from the priority queue
    while (!events.empty()) {
        Event currentEvent = events.top();
        events.pop();
        // If it's the start of a segment, increment the count of active segments
        if (currentEvent.isStart) {
            activeSegments++;
            // Check for intersections with other active segments
            for (int i = 0; i < segments.size(); ++i) {
                if (i != currentEvent.segmentIndex &&
                    segments[i].start <= currentEvent.position &&
                    segments[i].end >= currentEvent.position) {
                    // Found an intersection
                    intersections.push_back({currentEvent.segmentIndex, i});
                }
            }
        } else {
            // If it's the end of a segment, decrement the count of active segments
            activeSegments--;
        }
    }
    return intersections;
}
int main() {
    // Example input: segments represented as pairs of start and end points
    vector<Segment> segments = {{1, 3}, {2, 4}, {5, 7}, {6, 8}};
    // Find intersections using the sweep line algorithm
    vector<pair<int, int>> intersections = findIntersections(segments);
    //Output the intersections found
    cout << "Intersections found:" << endl;
    for (const auto& intersection : intersections) {
        cout << "Segments " << intersection.first << " and " << intersection.second << endl;
    }
    return 0;
}

输出

Intersections found:
Segments 3 and 2
Segments 1 and 0

说明

扫描线算法

扫描线算法方法用于执行自动过程，其中扫描线将事件视为扫描线在几何空间上移动的点。从这个意义上说，点是基本的（主要的），或者有些是非基本的（次要的）；这可能是线段的开始或结束。这些事件的处理遵循中学几何课中所描述的顺序，沿着算法的扫描线，从而高效地确定**线段**之间的交点。

事件结构

事件结构被建模为通过扫描线收集的事件数据。每个事件包含其在x轴上的位置、一个布尔值，表示线段是闭合的还是开放的，以及它所属线段的索引。此框架的**灵活性**有助于我们无缝地处理事件或程序的进程。

优先队列

基于事件的实现将使用优先队列数据结构来存储扫描线忽略的事件。优先队列确保事件**逐步**处理，从那些发生在扫描线附近的事件开始，然后向前推进。创建了专门用于匹配坐标（位置）和事件类型（开始或结束）的运算符。

事件处理

算法遍历线段，创建相同的开始和结束事件，然后将它们放入优先队列。发生的情况是，在算法过程中，事件正从**优先队列**中获取，输出是扫描线状态的更新，该状态跟踪活动的线段并确定是否存在交点。

交点检测

当**遇到**开始事件时，活动线段的数量会增加，算法会进一步验证活动线段之间是否发生交点。记录器记录两种数据：如果找到交点，则将其添加到交点列表中。达到结束事件时，活动线段数量递减。

输出

处理完所有事件后，算法输出线段之间的交点。这些交点代表了在**扫描线**上两条或多条线段相交的点。

示例

在提供的示例中，输入由由起点和终点对表示的线段组成。算法使用**扫描线技术**查找这些线段之间的交点。

结论

使用扫描线算法，通过扫描线遇到的事件和穿过的线，可以确保正确确定线段之间的交点。该算法通过使用优先队列确保了**效率和可扩展性**，从而能够以排序的方式管理对象。因此，我们有一个例子说明了扫描线（技术）的过度复杂性，它有助于解决几何学中的一些问题。

复杂度分析

时间复杂度

**事件处理：** 优先队列内部的处理非常重要。其复杂度为**O(log N)**，其中 N 是事件的数量。另一方面，需要对数时间复杂度，因为需要访问/删除**优先队列**的顶层元素。

**插入事件：** 将每个事件放入优先队列需要**O(log N)**时间，其中 N 表示事件的数量。因此，必须将两个事件插入到 N 条线段中，这表明此操作的总时间复杂度为**O(N log N)**。

**交点检测：** 该算法在每次开始时验证与现有线段相交的可能性。它涵盖了重复部分，即通过所有**活动线段**，在最坏的情况下，其时间复杂度为**O(N)**，其中 N 是在任何时刻相对于扫描线的活动线段的数量。

**整体时间复杂度：** 由于复杂度涉及算法内的步骤，因此其时间计算可近似为**O(NlogN)**，其中 N 指的是事件的总数。

空间复杂度

**优先队列：** 用于存储事件数的优先队列的空间复杂度为**O(N)**，其中 N 是事件总数。这是因为队列必须为扫描线遇到的每个事件保存一些数据。

**事件：** 每个**事件结构**由位置、事件类型和事件段索引组成。此外，存储所有事件的空间复杂度为**O(N)**。

**交点存储：** 算法的空间复杂度也受程序操作期间加倍的交点数量的影响。在上限情况下，所有线段的交点可能存储在空间复杂度为**O(N^2)**的空间中。此外，交点的数量通常很少，可能低于线段的数量。

**整体空间复杂度：** 值得一提的是，优先队列、事件队列和交点占用的空间可以相加为**O(N)**。

方法 2：通过创建有序集或映射。

在这里，我们利用有序集或映射数据结构的现有功能来处理扫描线在空间中遍历时遇到的情况。与选择事件根据其在扫描线中的位置的静态队列方法不同，**有序集或映射**提供了一种更灵活的方式，根据事件类型或线段索引等附加参数来排序和检索事件。通过这种技术，开发人员可以实现类似的指令执行数量减少，并更精确地控制**事件处理过程**。

**扫描线：** 该方法以扫描线为主要参数，扫描线是跨越几何空间以系统顺序处理事件的虚拟线。在扫描线时，例程会遇到事件，事件被定义为**线段**的开始或结束，或几何图形的典型事件。

**事件处理：** 事件是扫描线算法的关键要素，它充当关键事件发生的孔。已排序的事件用于更快地解决**几何问题**或检测线段之间的交点。

**有序集或映射：** 与仅根据事件在扫描线上的位置排序事件的**优先队列**不同，有序集或映射提供了更大的**灵活性**，可以根据各种标准进行事件排序和检索。这种灵活性允许更量身定制的事件处理，并可以简化某些算法的**实现**。

程序

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
// Structure to represent an event
struct Event {
    int position;   //Position along the sweep line
    bool isStart;   // Flag indicating whether it's the start of a rectangle or not
    int rectangleIndex;   //Index of the rectangle in the input array
    Event(int pos, bool start, int index) : position(pos), isStart(start), rectangleIndex(index) {}
    // Custom comparison operator for sorting in an ordered set
    bool operator<(const Event& other) const {
        // Sort events based on Position along the sweep line
        // In case of a tie, prioritize start events over end events
        if (position == other.position)
            return isStart && !other.isStart; // Start event comes first if tied
        return position < other.position;
    }
};
// Structure to represent a rectangle
struct Rectangle {
    int left;   // Left edge of the rectangle
    int right;  // Right edge of the rectangle
    int top;    // Top edge of the rectangle
    int bottom; // Bottom edge of the rectangle
    Rectangle(int l, int r, int t, int b) : left(l), right(r), top(t), bottom(b) {}
};
// Function to compute the union of rectangles and the total area covered
int computeRectangleUnionArea(vector<Rectangle>& rectangles) {
    int totalArea = 0;  // Total area covered by rectangles
    set<Event> events;   // Ordered set to manage events
    // Populate the ordered set with events (start and end points of rectangles)
    for (int i = 0; i < rectangles.size(); ++i) {
        events.insert(Event(rectangles[i].left, true, i));   // Start event for left edge
        events.insert(Event(rectangles[i].right, false, i)); // End event for right edge
    }
    int activeRectangles = 0; //Number of active rectangles at any point along the sweep line
    int previousX = 0; // Previous x-coordinate encountered along the sweep line
    // Process events from the ordered set
    for (const auto& event : events) {
        int deltaX = event.position - previousX; //Width of the current slice along the sweep line
        totalArea += deltaX * activeRectangles; // Add the area of the slice covered by active rectangles
        // Update the state of active rectangles based on the current event
        if (event.isStart) {
            activeRectangles++;
        } else {
            activeRectangles--;
        }
        previousX = event.position; // Update previous x-coordinate
    }
    return totalArea;
}
int main() {
    //Example input: rectangles represented by their left, right, top, and bottom edges
    vector<Rectangle> rectangles = {{1, 3, 4, 2}, {2, 5, 5, 3}, {4, 6, 6, 4}, {7, 9, 7, 5}};
    // Compute the union of rectangles and the total area covered
    int totalArea = computeRectangleUnionArea(rectangles);
    //Output the total area covered by the rectangles
    cout << "Total area covered by the rectangles: " << totalArea << endl;
    return 0;
}

输出

Total area covered by the rectangles: 9

说明

矩形表示

矩形由其左、右、上、下x坐标表示。每个单独矩形的平方由其在笛卡尔平面中的轴确定。

事件结构

使用具有**扫描线结构**的事件类来表示每个扫描线遇到的事件。在每个事件中，都有关于其在扫描线上的位置、它是否标记**矩形形成**的开始或结束以及输入数组中索引矩形的索引的信息。事件根据它们在垂直线上的位置进行排序。

用于事件管理的有序集

**扫描算法变量**存储和操作扫描线遇到的事件。有序数组确保事件被处理，即根据它们在**扫描线**上的位置进行排序。

计算矩形并集

算法通过遍历数组，以正确的顺序将开始和停止事件放入集合中。在处理来自**排序集**的事件元素时，算法会更新扫描线上活动的矩形的状态。在每一步，算法都确定由活动矩形覆盖的面积，并将其添加到所有**矩形**的总面积中（即矩形的并集）。

面积计算

矩形并集覆盖的面积是通过在扫描线时**累加**单个切片的面积来计算的，其中给定阶段的每个切片等于该点活动矩形的宽度。

效率

通过将**扫描线**方法与有序集结合使用，该算法可以快速检测矩形并集和接触的表面积。有序队列确保按顺序处理连续事件，从而使整个方法变得**流畅而有效**。

复杂度分析

时间复杂度

**事件处理：** 在有序集中**处理一个事件**的时间复杂度为**O(logN)**，其中 N 代表由扫描线识别的事件数量。当事件按顺序处理时，获取和删除它们的复杂度为 O(log(n))，其中 n 是**有序集**的大小。

**插入事件：** 将每个事件放入集合需要**O(log N)**时间，其中 N 是事件总数。现在，在每个矩形中，会发生两个事件（一个开始和一个结束）（这意味着 2N 个事件）被插入到有序集中。因此，插入例程的整个时间复杂度为**O(N log N)**。

**事件管理：** 该算法通过在排序线上执行所有操作来精确地更新活动矩形的状态。这是计算活动矩形和循环事件的阶段。由于元素只处理一次，因此处理事件的时间复杂度为**O(N)**。

**总时间复杂度：** 此整体时间复杂度可近似为**O(N log N)**，其中 N 是扫描线可能遇到的事件次数。复杂性源于事件处理是计算负担的主要特征。

空间复杂度

**有序集：** 用于存储事件的有序数据类型空间复杂度为 O(N)，其中 N 是**扫描线遇到的**事件总数。由于有序集旨在传达每个事件的详细信息，因此所需空间与事件数量成正比。

**事件：** 每个事件结构将包含其位置、类型和与相应矩形的关联索引的数据。因此，存储所有事件的空间复杂度为**O(N)**。

**总空间复杂度：** 考虑到集合和事件所需的空间，算法的虚拟空间复杂度可粗略地称为**O(N)**。这种复杂性随着扫描线在算法过程中捕获事件而结束。

下一个主题C++ 中的自恋数

← 上一个下一个 →

C++ 中的扫描线算法

方法 1：使用优先队列

程序

方法 2：通过创建有序集或映射。

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中的扫描线算法

方法 1：使用优先队列

程序

方法 2：通过创建有序集或映射。

程序

相关帖子

C++ 中的瓦格斯塔夫素数

C++ 中的汉明数序列

C++ 标签分派

C++ 中的 std::basic_ospanstream

C++ 中使用 Binet 公式查找第 n 个斐波那契数

C++ std::tmpnam

C++ std::student_t_distribution

C++ 中的最大电影院座位分配

C++ 中的 std::codecvt

C++ 中查找第 n 个埃尔米特数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器