查找阵列中角度之间的最大差异

我正在使用一些加速度计数据，这些数据是介于-180和180之间的数值数组。以度为单位表示角度。查找阵列中角度之间的最大差异

有没有一种巧妙的算法来找出任意两个角度之间的最大差异？

2013-09-29 wmil

聪明吗？你的意思是像排序他们，然后采取[1]和[N] –

数据是圆形的，180 = -180。所以找到最小和最大是不够的。 – wmil

先转换，然后排序。 –

真的应该有很多角度来担心它。但是当然，你可以击败O（n^2）

排序数组。使用指针a和b。首先找到从a开始的最大角度的b，并将其存储到best。然后重复提前a一步并且步b，直到它停止增加差异。您将遍历约150次的清单，以O（n）为界，因为b无法跨越a。所以它不会比分类花费的时间更糟糕。

来源

2013-09-29 05:57:00 clwhisk

我认为你已经在这里得到了正确的答案，但它可以做更多的解释，将它从“排序并选择第一个和最后一个”的建议中分离出来。例如，你可以证明为什么对于一个有序数组'A'，如果'A [j]'与'A [i]'有最大的角度差，而'A [k]'与'A [ i + 1]'''k> = j'。这是真正阻止你必须通过O（n^2）对进行搜索的原因。 – beaker

如果角度为[0，180]，则表示角度为正，如果角度为[-180,0]，则表示角度为负。

扫描列表中，执行如下：
1结果的最大和最小正角度
2记录最大和最小负角度
3如果角度为正角度，将其转换（让它减去180 ）到负角度，并用一些标记标记以指示它来自转换

对于＃1，最大的差别就是最大的角度减去最小的角度。所以是＃2。

对于＃3，首先排序角度。从排序列表的末尾扫描。如果相邻的角度是不同种类的（一个来自转换，一个不是），然后计算差异。如果差异是有史以来最小的差异，请记录下来，并继续扫描。完成后，使用180-差值，并将结果作为差值＃3。

现在你有3个差异，挑选最大的一个。我认为这是答案。

对于复杂性，所有扫描都是O（n）。对于分类，如果所有角度都是正值或负值，则根本不需要相位＃3。如果需要阶段＃3，我们可以让它有更少的角度。例如，如果列表的正面角度较小，我们可以将正面转换为负面，反之亦然。排序是O（nlgn），但我们可以有更小的n。

来源

2013-09-29 06:15:00 Hong

你也可以跳过转换，并有两个扫描仪：一个从正角开始，一个在负角开始。 – Teepeemm

从RW教程中得到了这个。

它与你想要的相反（返回最小的角度），但你可以调整它。

// Returns shortest angle between two angles, 
// between -M_PI and M_PI 

static inline CGFloat ScalarShortestAngleBetween(const CGFloat a, const CGFloat b) 
{ 
    CGFloat difference = b - a; 
    CGFloat angle = fmodf(difference, M_PI * 2); 
    if (angle >= M_PI) 
    { 
     angle -= M_PI * 2; 
    } 
    return angle; 
}

来源

2013-09-29 07:42:52 DogCoffee

这是错过了重点。 OP已经可以找到两个角度之间的差异（我们假设）。我们正在寻找最大的角度返回，希望没有经过所有成对转换的显而易见的'O（n^2）'过程。 – Teepeemm

查找阵列中角度之间的最大差异

回答

相关问题