主页 / 问题 / 679634
Accepted
Naf
Asked:2020-06-15 19:46:25 +0000 UTC2020-06-15 19:46:25 +0000 UTC

段的并集和差集

  • 772

我有一个这样的段对象列表：

public Class Line
{
    public int Type;
    public float From;
    public float To;
}

type 字段可以是 2 或 3，如果是 2，则需要合并段，如果是 3，则从所有先前的段中减去当前段。
例如，让我们有一个包含以下元素的列表：
在此处输入图像描述

列表中元素的顺序很重要。

在结果列表中，我需要获取以下列表：

在此处输入图像描述

那些。重点是：我正在遍历原始列表，找到当前元素和结果列表的元素之间的共同点。如果结果列表为空，那么我将当前元素添加到那里，如果那里有元素，那么，根据段的类型，我需要将它与结果列表中的所有内容组合起来，或者从所有元素中减去当前元素结果列表的元素。
以这种形式表示初始和结果段列表对我来说更方便：

在垂直实线后面，我形成了最终版本

提交一个想法来解决这个问题。欢迎任何帮助。

c#

2 个回答

  1. Best Answer

    将数据转换为 (value-delta)。该值是来自“from”或“to”列的数字（简而言之，所有内容都集中在一起），delta 对于类型 2 的开头为 +1，对于类型 2 的结尾为 -1，对于类型 2 为 -N类型3的开头，其中N大于类型2的记录数，为类型3的结尾，分别+N。我们按 Value 对结果堆进行排序，并按 Delta 计算增量和。如果总和大于零，则开始间隔，如果总和为零或更小，则结束间隔。

    一切。

    关于显示的初始数据，结果将是

    Значение Дельта Сумма
0         1      1
3        -5     -4
5         1     -3
7        -1     -4
9        -1     -5
10        1     -4
11        5      1
12       -1      0
15        1      1
17       -1      0

    因此，间隔为 0-3、11-12 和 15-17。

    如果顺序很重要，那么我们按顺序处理 - 首先是两条记录，然后是总计（它被分配为类型 2）加上第三条，总计加上第四条......对于初始数据它将是：

    前两个：

    0   1   1
5   1   2
7   -1  1
9   -1  0

    总计 - (0-9)。

    底线加三分之一：

    0   1   1
9   -1  0
10  1   1
12  -1  0

    总计 - (0-9)，(10-12)。

    结果加第四：

    0   1   1
3   -5  -4
9   -1  -5
10  1   -4
11  5   1
12  -1  0

    总计 - (0-3), (11-12)

    添加第五个：

    0   1   1
3   -1  0
11  1   1
12  -1  0
15  1   1
17  -1  0

    结果 - (0-3), (11-12), (15-17)

    • 4

  2. @Akina提出的方法是最优的，解决了问题，但是由于 值的数量相对较少；我建议使用正面方法作为替代方法，这可能更容易阅读/测试。

    训练：

    要准备，您需要在以下位置创建辅助方法Line：

    • 一种检查线段交集的方法，例如bool DoesIntrsect(Line other)
    • 组合两个相交线段的方法：Line Join(Line other)
    • 从一个片段中减去另一个片段的方法：List<Line> Subtract(Line other)

    前两个是相当微不足道的。对于第三种情况，需要考虑几种情况：

        Случай 1   │   Случай 2  │  Случай 3   │  Случай 4    │  Случай 5 
 ----          │   -----     │      -----  │ -----------  │     ----
        ————   │      ————   │   —————     │    ——————    │   —————————

    在前三种情况下，返回一个片段，在第四种情况下，返回两个，在第五种情况下，没有。

    算法：

    主要思想是创建一个段列表，其中包含每个步骤的当前结果并且满足条件：

    • 不包含交叉段；
    • 排序。

    起初列表是空的。我们一步一步地处理这些片段。对于每个步骤：

    • 从列表中删除与当前段相交的所有段；
    • 如果减去当前段：从每个远程段中减去当前段，Subtract将结果添加到列表中；
    • if the current segment is merged: 将所有远程段依次与当前段合并，合并的结果添加到列表中。

    列表已排序的事实可能会减少通过列表的里程数。也许这不是当前数量所必需的。

    注意：特别注意线段相切（它们必须合并）/重合（减法结果必须为空）的情况。极值点容易出错。

    • 1

相关问题