检查两组点是否位于源点的不同半球

Question

我有一个整数坐标的二维平面图。

这个方案有很多点，分为三类。

"Source"。只有一个点是源头。
尼斯组，包含未知（但合理）数量的点
邪恶集团，包含未知（但合理）数量的点

我首先要做的是弄清楚 (yes/no) 这两个群体是否在不同的半球。

如果你能在源头（图中的蓝色）画一条线，所有好的都在一侧，所有的邪恶都在另一侧，那么它们被认为在不同的半球。如果任何一组中的一个不能与其他组放在同一侧，则为错误。

第二步是算出这个半球的角度。在第一个示例（下图）中，我画了一个 180 度角（直线），但我想计算最不平衡的角度（接近 0），这将允许完美地分离组。那么这条线将是两条半线，从源头开始到无穷远。我想知道使第一个测试保持真实的最小角度（因此，从逻辑上讲，如果测量另一侧，则为最大角度）

示例：

1:

2:

3:

现在我可以通过代码计算每个点与源之间的角度。我一直在弄清楚如何测试组的 "togetherness"，最重要的是，中间没有其他组的成员。

我在 C# 工作，但这个问题实际上更多是关于算法的（我想不出一个有效的算法），所以我会接受用任何（可读）语言解决问题的任何答案，包括伪代码或直接文本解释。

在上下文中，所有点都是包含 X 和 Y 坐标的复杂对象。其他属性与问题无关，因为它们已经在所需的组中分开（来源是单独的，其余的有两个列表）。

Answer 1

您可以排序和扫描。下面介绍一下极坐标系，原点在Origin，任意轴

为每个点（好的或坏的）计算 azimuth
按 azimuth 订购积分，例如
扫描已排序的集合；如果你有 2 或 less 从善到恶或从恶到善的转换； returntrue，否则false

例如（让方位角以度为单位）

   {nice,  12}
   {nice,  13}
   {nice,  15}
   {nice,  21} // nice to evil transition
   {evil,  47}
   {evil, 121}
   {evil, 133} // evil to nice transition
   {nice, 211}
   {nice, 354}

我们有两个转换，答案是 true。

   {nice,  12}
   {nice,  13}
   {nice,  15} // nice to evil transition
   {evil, 121}
   {evil, 349}

只有一个过渡，答案是肯定的

   {nice,  12}
   {nice,  13} // nice to evil transition
   {evil, 121} // evil to nice transition
   {nice,  15} // nice to evil transition
   {evil, 121} // evil to nice transition
   {nice, 349}

四个过渡点，分不开，答案是false

Answer 2

得到on组的最低电流x和最低电流y。并获得最高...然后比较另一组以查看两者之间的差异。如果在点 (highx,highy) 和 (lowx,lowy) 之间发现其他点之一，它们就会混合在一起。如果不是，它们是分开的...

一旦你知道它们是分开的，从你的最低（x，y）画一条线到你的最高（x，y）并将该线转换为你的原点，给你两个 'hemispheres'

请注意，这仅在它们被一条线而不是一个角分开时才有效。

角度

将 a 和 y 分开一旦你有另一组没有穿过的最低（或最高）x，那么对 y 做同样的事情。有了这两个坐标和你的原点，你应该能够确定你的角度。

检查两组点是否位于源点的不同半球

Check if two sets of points are in different hemispheres from a source point

c#

algorithm

2d

angle

coordinates