2

我有角度间隔（以弧度为单位）[0,2π）

  • 例如区间 [(2π)/3,(3π)/4],[π/2,π] 等。
  • 但也可能存在区间 [(3π)/2,π/3]

我必须找到位于大多数区间的角度。在 C++ 中找到它的最佳方法是什么？我怎样才能表示角度间隔？

4

4 回答 4

4

你可以实现一个简单的扫描线算法来解决这个问题。

对于每个区间，将区间的开始和结束添加到向量中；排序这个向量，然后遍历它。如果您有任何跨越 2π 边界的区间，只需将其分成两个区间，它们都在 (0, 2π) 之内。

当您遍历列表时，请跟踪当前点有多少重叠迭代，以及到目前为止您看到的最佳角度是多少（以及在该角度重叠了多少间隔）。一旦到达终点，您就会知道最佳角度是多少。

如果您需要多个角度，您可以很容易地采用这种方法来记住具有最大重叠的间隔，而不是单个角度。

于 2012-11-09T16:50:06.133 回答
1

我会通过将 [0, 2π] 的分区维护为与区间覆盖相对应的范围来做到这一点，每个范围都有一个计数。首先，这是算法在没有任何区间超过 0（或 2π）的条件下的工作方式。还假设区间归一化如下：如果区间以 0 结束，则将其更改为以 2π 结束；如果从 2π 开始，则改为从 0 开始。

  1. 创建一个 (range, count) 对的列表，使用单个范围 [0, 2π] 和计数 0 进行初始化。（列表将按范围的开头进行排序。列表中的范围只会在它们的位置重叠端点并且将始终覆盖 [0, 2π])。
  2. 如下所述处理每个间隔
  3. 扫描列表以查找具有最高计数的 (range, count) 对。随意解决关系。返回范围内的任意角度。

处理一个区间i：

  1. 找到第一个（范围，计数）对（称为它s）i.start >= s.range.start（即范围包含i.start）。（请注意，如果i.start是一个范围的结束，那么它将是另一个范围的开始；这会选择它作为开始的对。）
  2. 找到最后一个（范围，计数）e对i.end <= e.range.end。（请注意，如果i.end是一个范围的开始，那么它将是另一个范围的结束；这会选择它作为结束的对。）
  3. 如果i.start > s.range.start(i.range开始于s) 的内部，s分成两对 (range, count)s1 = ([s.range.start, i.start], s.count)和s2 = ([i.start, s.range.end], s.count). s在列表中替换为s1和s2（按此顺序）。
  4. 如果，以与上一步平行的方式i.end < e.range.end替换，用于进行拆分。ei.end
  5. s对于从（或s2如果s在步骤 3 中拆分）到包括e（或e1如果e在步骤 4 中拆分）的每一对，将计数加 1。

如果您不关心包含特定角度的间隔的实际数量，只是它是最大值，则跨 0（或 2π）的间隔的簿记更容易：只需取间隔的补数（反向开始和结束）并从第 5 步中的计数中减去 1 而不是加法。如果您确实需要绝对计数，请执行补码技巧，然后将列表中的每个计数加 1。

以上将无法正确处理相邻的区间（例如：[0, π/3] 和 [π/3, π]；或 [2π/3, 2π] 和 [0, 1]）。在这些情况下，据我了解，它们邻接的角度（π/3 或 0）应计为两个间隔。可以调整上述算法，以便当间隔开始与范围结束点重合时，在相关对之后插入一个新的（范围，计数）对；新对将具有单角度范围（即range.start == range.end）。类似的过程将适用于从间隔末尾开始的范围。我认为通过这些调整，上述算法可以正确处理所有情况。

于 2012-11-09T18:49:30.073 回答
1

我的解决方案将涉及间隔开始对的列表以及有多少间隔与其重叠：

     1        2       3       2              1
|---------|--------|-----|---------------|------|

|------------------|
          |--------------|
                   |---------------------|
                   |----------------------------|

因此，对所有起点和终点进行排序并遍历列表，为每个新间隔分配与其重叠的间隔计数（如果它是起点则增加，否则减少）。然后从重叠计数中取最大值。

于 2012-11-09T16:52:05.930 回答
0

如果你不象征性地这样做，我认为你会遇到奇怪的边缘情况。

您的角度范围不仅不能完全表示为二进制分数（引入舍入误差），而且它们是不合理的。（大于 3.14159265359 但小于 3.14159265360；除了象征性外Pi，如何说角度等于/2？）Pi

我看到的最稳健的方法是依次获取所有区间组合，确定它们的交集，并查看这些组合区间中的哪些是最独立区间交集的结果。

这也有一个好处，它不仅给你一个，而且给你满足你条件的所有角度。

于 2012-11-09T16:58:10.440 回答