algorithm - 极平面中的线段方向

Question

我有以下情况:基点(绿色)和线段，对于每个线段，他的顶点表示为极点，与基点成 θ 角。

问题:对于每个段，我都有他的 2 个顶点 theta。未订购!我只需要从这些数据中找出该段重叠的角度范围。例如，对于属于顶部段的 2 个顶点 {20,300}，正确答案是所有角度从 300 到 20 而不是从 20 到 300。

方向是从 0 到 359，如示例所示，它是循环的。

编辑:假设 - Segment 的最大重叠角小于 180，即 179。

我认为解决方案只是为if...找到“正确的条件”

class Node {
    int theta;  //angle from base point e.g. 45
    double radius;  //distance (in problem specific metric) from base point
}

class Segment {
    //nodes not ordered in any way
    Node node_1;
    Node node_2;
}

List<Segments> allSegments = new ArrayList<>();
//populate allSegments...

Segment mSegment;
for (int i=0; i<allSegments.size(); i++) {
    mSegment = allSegments.get(i);
    if (TODO? mSegment.node_1.tetha ? mSegment.node_2.theta) {
       //the order is from node_1 to node_2 or otherwise...
    }
}

谢谢，

Answer 1

先不考虑线段通过原点的情况。我们稍后再考虑。

角度将定义两条弧:一条小于 180 度，一条大于 180 度。您的圆弧将始终小于 180 度。为什么？考虑垂直位移非常小的 x 轴。范围将是 90 度到 270 度，粗略地，给予或取少量。只要您保持在 x 轴的同一侧，两个角都不会大于直角，因此总和将小于 2 x 90 度。

给定任意两个角 x 和 y，x 和 y 在 [0, 360)(半开区间)内，我们可以 w.l.o.g.假设 x >= y。那么范围是 (x - y) 和 (y - x + 360)。计算两者并取两者中较小的一个。在您的示例中:(300 - 20) = 280 和 (20 - 300 + 360) = 80，因此答案为 80(如果您喜欢范围格式，则为 300-20)。再次:计算 (x - y) 和 (y - x + 360)，如果 (x - y) 较小，你的范围将是“y 到 x”，如果 (y - x + 360)，你的范围将是“x 到 y”更小。

现在考虑 x = y + 180 的情况。那么您的算法应该回答什么？这不是反问句 - 这是给用户的问题。