在 O(n log n) 中计算平面中一组线段的 "lower contour"
Compute the "lower contour" of a set of segments in the plane in `O(n log n)`
假设您在平面中有一组 s 水平线段，由起点 p、终点 q 和 y-值。
我们可以假设 p 和 q 的所有值成对不同并且没有两个片段重叠。
我想计算段的 "lower contour"。
我们可以按 p 排序 s 并遍历每个片段 j。如果 i 是 "active" 段并且 j->y < i->y 我们 "switch to" j （并输出相应的轮廓元素）。
然而，当不存在这样的 j 并且我们找到 j 和 i->q < j->p 时，我们能做什么呢？然后，我们需要切换到 "next higher segment"。但是我们怎么知道那个细分市场呢？我找不到一种方法使生成的算法的 运行 时间为 O(n log n)。有什么想法吗？
首先按x坐标（起点和终点）对所有端点进行排序。遍历端点并保留活动段的所有 y 坐标的 std::set。当你到达一个起点时，将它的 y 坐标添加到集合中，如果它是最低的，则将 "switch" 添加到它；当你到达一个终点时，从集合中删除它的 y 坐标并使用集合重新计算最低的 y 坐标。这给出了 O(n log n) 整体解决方案。
用于实现std::set的平衡二叉搜索树通常具有较大的常数因子。您可以通过使用二叉堆 (std::priority_queue) 而不是集合来加快此方法的速度，最低的 y 坐标位于根部。在这种情况下，您不能删除非根节点，但是当您到达这样的终点时，只需在数组中将段标记为非活动状态即可。当根节点弹出时，继续弹出，直到有一个新的根节点尚未被标记为非活动。我认为这将比基于集合的方法快两倍，但您必须自己编写代码，看看是否有问题。
A sweep line algorithm 是解决您问题的有效方法。正如 Brian 之前解释的那样，我们可以按 x 坐标对所有端点进行排序并按顺序处理它们。这里要做出的一个重要区别是，我们正在对段的 端点 进行排序，而不是按起始点递增的顺序对段进行排序。
如果您想象一条垂直线从左到右扫过您的线段，您会注意到两件事：
- 在任何位置，垂直线要么与一组线段相交，要么不相交。我们称这个集合为活动集合。下面的轮廓是活动集中具有最小 y 坐标的段。
- 唯一可以更改下轮廓的 x 坐标是线段端点。
这立即带来了一个观察结果：下部轮廓应该是 段 的列表。点列表没有提供足够的信息来定义轮廓，在某些 x 坐标（没有线段）处可能未定义轮廓。
我们可以使用按段的 y 位置排序的 std::set 对活动集进行建模。按 x 坐标递增的顺序处理端点。遇到左端点时，insert 段。遇到右端点时，erase 线段。由于排序，我们可以在恒定时间内找到具有最低 y 坐标且 set::begin() 的活动段。由于每个段只会插入一次和擦除一次，因此维护活动集总共需要 O(n log n) 时间。
事实上，如果更容易的话，可以为与扫掠线相交的每个线段仅保留 y 坐标 std::multiset。
段不重叠且具有不同端点的假设并非完全必要。重叠段由段的有序 set 和 y 坐标的 multiset 处理。可以通过一次考虑具有相同 x 坐标的所有端点来处理重合端点。
在这里，我假设没有零长度段（即点）来简化事情，尽管它们也可以用一些额外的逻辑来处理。
std::list<segment> lower_contour(std::list<segment> segments)
{
enum event_type { OPEN, CLOSE };
struct event {
event_type type;
const segment &s;
inline int position() const {
return type == OPEN ? s.sp : s.ep;
}
};
struct order_by_position {
bool operator()(const event& first, const event& second) {
return first.position() < second.position();
}
};
std::list<event> events;
for (auto s = segments.cbegin(); s != segments.cend(); ++s)
{
events.push_back( event { OPEN, *s } );
events.push_back( event { CLOSE, *s } );
}
events.sort(order_by_position());
// maintain a (multi)set of the y-positions for each segment that intersects the sweep line
// the ordering allows querying for the lowest segment in O(log N) time
// the multiset also allows overlapping segments to be handled correctly
std::multiset<int> active_segments;
bool contour_is_active = false;
int contour_y;
int contour_sp;
// the resulting lower contour
std::list<segment> contour;
for (auto i = events.cbegin(); i != events.cend();)
{
auto j = i;
int current_position = i->position();
while (j != events.cend() && j->position() == current_position)
{
switch (j->type)
{
case OPEN: active_segments.insert(j->s.y); break;
case CLOSE: active_segments.erase(j->s.y); break;
}
++j;
}
i = j;
if (contour_is_active)
{
if (active_segments.empty())
{
// the active segment ends here
contour_is_active = false;
contour.push_back( segment { contour_sp, current_position, contour_y } );
}
else
{
// if the current lowest position is different from the previous one,
// the old active segment ends here and a new active segment begins
int current_y = *active_segments.cbegin();
if (current_y != contour_y)
{
contour.push_back( segment { contour_sp, current_position, contour_y } );
contour_y = current_y;
contour_sp = current_position;
}
}
}
else
{
if (!active_segments.empty())
{
// a new contour segment begins here
int current_y = *active_segments.cbegin();
contour_is_active = true;
contour_y = current_y;
contour_sp = current_position;
}
}
}
return contour;
}
正如 Brian 还提到的，像 std::priority_queue 这样的二叉堆也可以用来维护活动集，并且往往优于 std::set，即使它不允许删除任意元素。您可以通过将段标记为已删除而不是将其擦除来解决此问题。然后，重复删除 priority_queue 的 top()（如果它是已标记的段）。这最终可能会更快，但对于您的用例来说可能重要也可能无关紧要。
假设您在平面中有一组 s 水平线段，由起点 p、终点 q 和 y-值。
我们可以假设 p 和 q 的所有值成对不同并且没有两个片段重叠。
我想计算段的 "lower contour"。
我们可以按 p 排序 s 并遍历每个片段 j。如果 i 是 "active" 段并且 j->y < i->y 我们 "switch to" j （并输出相应的轮廓元素）。
然而，当不存在这样的 j 并且我们找到 j 和 i->q < j->p 时，我们能做什么呢？然后，我们需要切换到 "next higher segment"。但是我们怎么知道那个细分市场呢？我找不到一种方法使生成的算法的 运行 时间为 O(n log n)。有什么想法吗？
首先按x坐标（起点和终点）对所有端点进行排序。遍历端点并保留活动段的所有 y 坐标的 std::set。当你到达一个起点时，将它的 y 坐标添加到集合中，如果它是最低的，则将 "switch" 添加到它；当你到达一个终点时，从集合中删除它的 y 坐标并使用集合重新计算最低的 y 坐标。这给出了 O(n log n) 整体解决方案。
用于实现std::set的平衡二叉搜索树通常具有较大的常数因子。您可以通过使用二叉堆 (std::priority_queue) 而不是集合来加快此方法的速度，最低的 y 坐标位于根部。在这种情况下，您不能删除非根节点，但是当您到达这样的终点时，只需在数组中将段标记为非活动状态即可。当根节点弹出时，继续弹出，直到有一个新的根节点尚未被标记为非活动。我认为这将比基于集合的方法快两倍，但您必须自己编写代码，看看是否有问题。
A sweep line algorithm 是解决您问题的有效方法。正如 Brian 之前解释的那样，我们可以按 x 坐标对所有端点进行排序并按顺序处理它们。这里要做出的一个重要区别是，我们正在对段的 端点 进行排序，而不是按起始点递增的顺序对段进行排序。
如果您想象一条垂直线从左到右扫过您的线段，您会注意到两件事：
- 在任何位置，垂直线要么与一组线段相交，要么不相交。我们称这个集合为活动集合。下面的轮廓是活动集中具有最小 y 坐标的段。
- 唯一可以更改下轮廓的 x 坐标是线段端点。
这立即带来了一个观察结果：下部轮廓应该是 段 的列表。点列表没有提供足够的信息来定义轮廓，在某些 x 坐标（没有线段）处可能未定义轮廓。
我们可以使用按段的 y 位置排序的 std::set 对活动集进行建模。按 x 坐标递增的顺序处理端点。遇到左端点时，insert 段。遇到右端点时，erase 线段。由于排序，我们可以在恒定时间内找到具有最低 y 坐标且 set::begin() 的活动段。由于每个段只会插入一次和擦除一次，因此维护活动集总共需要 O(n log n) 时间。
事实上，如果更容易的话，可以为与扫掠线相交的每个线段仅保留 y 坐标 std::multiset。
段不重叠且具有不同端点的假设并非完全必要。重叠段由段的有序 set 和 y 坐标的 multiset 处理。可以通过一次考虑具有相同 x 坐标的所有端点来处理重合端点。
在这里，我假设没有零长度段（即点）来简化事情，尽管它们也可以用一些额外的逻辑来处理。
std::list<segment> lower_contour(std::list<segment> segments)
{
enum event_type { OPEN, CLOSE };
struct event {
event_type type;
const segment &s;
inline int position() const {
return type == OPEN ? s.sp : s.ep;
}
};
struct order_by_position {
bool operator()(const event& first, const event& second) {
return first.position() < second.position();
}
};
std::list<event> events;
for (auto s = segments.cbegin(); s != segments.cend(); ++s)
{
events.push_back( event { OPEN, *s } );
events.push_back( event { CLOSE, *s } );
}
events.sort(order_by_position());
// maintain a (multi)set of the y-positions for each segment that intersects the sweep line
// the ordering allows querying for the lowest segment in O(log N) time
// the multiset also allows overlapping segments to be handled correctly
std::multiset<int> active_segments;
bool contour_is_active = false;
int contour_y;
int contour_sp;
// the resulting lower contour
std::list<segment> contour;
for (auto i = events.cbegin(); i != events.cend();)
{
auto j = i;
int current_position = i->position();
while (j != events.cend() && j->position() == current_position)
{
switch (j->type)
{
case OPEN: active_segments.insert(j->s.y); break;
case CLOSE: active_segments.erase(j->s.y); break;
}
++j;
}
i = j;
if (contour_is_active)
{
if (active_segments.empty())
{
// the active segment ends here
contour_is_active = false;
contour.push_back( segment { contour_sp, current_position, contour_y } );
}
else
{
// if the current lowest position is different from the previous one,
// the old active segment ends here and a new active segment begins
int current_y = *active_segments.cbegin();
if (current_y != contour_y)
{
contour.push_back( segment { contour_sp, current_position, contour_y } );
contour_y = current_y;
contour_sp = current_position;
}
}
}
else
{
if (!active_segments.empty())
{
// a new contour segment begins here
int current_y = *active_segments.cbegin();
contour_is_active = true;
contour_y = current_y;
contour_sp = current_position;
}
}
}
return contour;
}
正如 Brian 还提到的，像 std::priority_queue 这样的二叉堆也可以用来维护活动集，并且往往优于 std::set，即使它不允许删除任意元素。您可以通过将段标记为已删除而不是将其擦除来解决此问题。然后，重复删除 priority_queue 的 top()（如果它是已标记的段）。这最终可能会更快，但对于您的用例来说可能重要也可能无关紧要。