查找许多线段的并集长度 [英] Finding union length of many line segments

问题描述

我在x轴上以其起始和结束x坐标的形式显示了一些粗体线段。一些线段可能重叠。如何找到所有线段的并集长度。

I have few bolded line segments on x-axis in form of their beginning and ending x-coordinates. Some line segments may be overlapping. How to find the union length of all the line segments.

例如，一条线段为5,0至8,0，另一段为9,0至12,0 。两者都不重叠，因此长度之和为3 + 3 = 6。

Example, a line segment is 5,0 to 8,0 and other is 9,0 to 12,0. Both are non overlapping, so sum of length is 3 + 3 = 6.

线段为5,0至8,0，其他为7,0至12 ，0。但是它们在7.0至8.0范围内重叠。所以长度的并集是7。

a line segment is 5,0 to 8,0 and other is 7,0 to 12,0. But they are overlapping for range, 7,0 to 8,0. So union of length is 7.

但是x坐标可能是浮点数。

But the x- coordinates may be floating points.

推荐答案

将线段表示为2个 EndPoint 对象。每个 EndPoint 对象的格式为< coordinate，isStartEndPoint> 。将所有线段的所有 EndPoint 对象放到列表 endPointList 中。

Represent a line segment as 2 EndPoint object. Each EndPoint object has the form <coordinate, isStartEndPoint>. Put all EndPoint objects of all the line segments together in a list endPointList.

算法：

• 排序 endPointList ，首先（按升序），然后然后将起点放在尾端终点之前（无论哪个段，因为这无关紧要-都在同一坐标上）



• 根据此伪代码遍历排序列表：

• Sort endPointList, first by coordinate in ascending order, then place the start end points in front of the tail end points (regardless of which segment, since it doesn't matter - all at the same coordinate).

• Loop through the sorted list according to this pseudocode:

prevCoordinate = -Inf
numSegment = 0
unionLength = 0

for (endPoint in endPointList):
    if (numSegment > 0):
        unionLength += endPoint.coordinate - prevCoordinate

    prevCoordinate = endPoint.coordinate

    if (endPoint.isStartCoordinate):
        numSegment = numSegment + 1
    else:
        numSegment = numSegment - 1

numSegment 变量将告诉我们是否在细分市场中。当它大于0时，我们在某个线段内，因此我们可以包括到上一个端点的距离。如果为0，则表示当前端点之前的部分不包含任何段。

The numSegment variable will tell whether we are in a segment or not. When it is larger than 0, we are inside some segment, so we can include the distance to the previous end point. If it is 0, it means that the part before the current end point doesn't contain any segment.

由于基于比较，因此复杂度由排序部分所控制。排序算法的下界为Omega（n log n），而循环显然最好为O（n）。因此，如果选择基于O（n log n）比较的排序算法，该算法的复杂度可以说是O（n log n）。

The complexity is dominated by the sorting part, since comparison-based sorting algorithm has lower bound of Omega(n log n), while the loop is clearly O(n) at best. So the complexity of the algorithm can be said to be O(n log n) if you choose an O(n log n) comparison-based sorting algorithm.

这篇关于查找许多线段的并集长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！