我有一个整数坐标的二维平面图。
在这一计划中,有许多要点,分为三类。
“源头”。只有一个点是源头。
nice组,包含未知(但合理)点数
邪恶集团,包含未知(但合理)点数
我首先要做的是弄清楚(是/否)这两个群体是否处于分离的半球。
如果你能在源头上画一条线(图片中是蓝色的),好的一面都是好的,坏的一面都是坏的,那么它们被认为是在不同的半球上。如果两组中有一组不能和其他组放在同一边,那就错了。
第二步是计算出这个半球的角度。在下面的第一个例子中,我画了一个180度的角度(直线),但是我想计算出最不平衡的角度(接近0),这将允许完美地分离组然后这条线是两条半直线,从源头开始,一直到无穷远我想知道使第一次测试保持正确的最小角度(所以,逻辑上,如果你测量另一边,那么最大角度)
示例:
1:c# - 检查两组点与源点是否在不同的半球中-LMLPHP
2:c# - 检查两组点与源点是否在不同的半球中-LMLPHP
3:c# - 检查两组点与源点是否在不同的半球中-LMLPHP
现在我可以通过代码计算每个点和源之间的角度。我一直在琢磨如何测试团队的“团结”,最重要的是,在这两者之间没有其他团队的成员。
我在C_工作,但这个问题实际上更多的是关于算法(我想不出一个有效的),所以我会接受任何用任何(可读的)语言解决问题的答案,包括伪代码或直接文本解释。
在上下文中,所有点都是包含x和y坐标的复杂对象。其他属性与问题无关,因为它们已经在所需的组中分离(origin是单独的,其余的有两个列表)。

最佳答案

你可以分类和扫描让我们介绍极坐标系的原点和任意轴的起源。
计算每个点的azimuth(好的或坏的)
按其azimuth排序,例如。
扫描已排序的集合;如果您在从好到坏或从坏到好之间有2或更少的转换;返回true,否则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

10-08 03:32