找到罗盘航向数组的最大差异
Finding largest difference in array of compass headings
我正在尝试获取过去 X 秒内的 "range" 罗盘航向。示例：在最后一分钟，我的航向在罗盘上一直在 120 度和 140 度之间。够简单吧？我有一个数组，其中包含一段时间内的罗盘航向，例如每秒 1 个读数。
[ 125, 122, 120, 125, 130, 139, 140, 138 ]
我可以取 最小值和最大值 值，然后就可以了。我的范围是 从 120 到 140。
只是没那么简单。举个例子，如果我的航向从 10 度转移到 350 度（即它 "passed" 通过北方，改变 -20 度。
现在我的数组可能看起来像这样：
[ 9, 10, 6, 3, 358, 355, 350, 353 ]
现在最小值为 3，最大值为 358，这不是我需要的 :( 我正在寻找最大的 "right hand"（顺时针）值，并且大多数 "left hand"（逆时针）值。
我唯一能想到的方法是沿着包含数组中 none 个值的圆找到最大的圆弧，但我什至不知道该怎么做。
非常感谢任何帮助！
问题分析
总结一下这个问题，听起来你想要找到以下两个：
- 最接近的两个读数（为简单起见：顺时针方向）AND
- 包含它们之间的所有其他读数。
因此，在您的第二个示例中，9 和 10 仅相差 1°，但它们不包含所有其他读数。相反，从 10 顺时针移动到 9 将包含所有其他读数，但它们在那个方向上相隔 359°，因此它们不是最近的。
在这种情况下，我不确定使用最小和最大读数是否有帮助。相反，我建议对所有读数进行排序。然后您可以更轻松地检查上面指定的两个条件。
这是您提供的第二个示例，按升序排列：
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
如果我们从头开始，我们知道从阅读 3 到阅读 358 将涵盖所有其他阅读，但它们 358 - 3 = 355° 是分开的。我们可以继续逐步扫描结果。请注意，一旦我们绕了一圈，我们必须加上 360 才能正确计算分离度。
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
*--------------------------> 358 - 3 = 355° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
-> *----------------------------- (360 + 3) - 6 = 357° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
----> *-------------------------- (360 + 6) - 9 = 357° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
-------> *----------------------- (360 + 9) - 10 = 359° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
----------> *------------------- (360 + 10) - 350 = 20° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
--------------> *-------------- (360 + 350) - 353 = 357° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
-------------------> *--------- (360 + 353) - 355 = 358° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
------------------------> *---- (360 + 355) - 358 = 357° separation
伪代码解决方案
这里有一个伪代码算法，用于确定读取值的最小度数范围。如果性能是一个问题，肯定有一些方法可以优化它。
// Somehow, we need to get our reading data into the program, sorted
// in ascending order.
// If readings are always whole numbers, you can use an int[] array
// instead of a double[] array. If we use an int[] array here, change
// the "minimumInclusiveReadingRange" variable below to be an int too.
double[] readings = populateAndSortReadingsArray();
if (readings.length == 0)
{
// Handle case where no readings are provided. Show a warning,
// throw an error, or whatever the requirement is.
}
else
{
// We want to track the endpoints of the smallest inclusive range.
// These values will be overwritten each time a better range is found.
int minimumInclusiveEndpointIndex1;
int minimumInclusiveEndpointIndex2;
double minimumInclusiveReadingRange; // This is convenient, but not necessary.
// We could determine it using the
// endpoint indices instead.
// Check the range of the greatest and least readings first. Since
// the readings are sorted, the greatest reading is the last element.
// The least reading is the first element.
minimumInclusiveReadingRange = readings[array.length - 1] - readings[0];
minimumInclusiveEndpointIndex1 = 0;
minimumInclusiveEndpointIndex2 = array.length - 1;
// Potential to skip some processing. If the ends are 180 or less
// degrees apart, they represent the minimum inclusive reading range.
// The for loop below could be skipped.
for (int i = 1; i < array.length; i++)
{
if ((360.0 + readings[i-1]) - readings[i] < minimumInclusiveReadingRange)
{
minimumInclusiveReadingRange = (360.0 + readings[i-1]) - readings[i];
minimumInclusiveEndpointIndex1 = i;
minimumInclusiveEndpointIndex2 = i - 1;
}
}
// Most likely, there will be some different readings, but there is an
// edge case of all readings being the same:
if (minimumInclusiveReadingRange == 0.0)
{
print("All readings were the same: " + readings[0]);
}
else
{
print("The range of compass readings was: " + minimumInclusiveReadingRange +
" spanning from " + readings[minimumInclusiveEndpointIndex1] +
" to " + readings[minimumInclusiveEndpointIndex2]);
}
}
还有一种这种伪代码算法没有涵盖的边缘情况，即存在多个最小包含范围的情况...
- 示例 1：[0, 90, 180, 270] 范围为 270（90 到 0/360、180 到 90、270 到 180 和 0 到 270）。
- 示例 2：[85, 95, 265, 275] 范围为 190（85 到 275 和 265 到 95）
如果有必要报告创建最小包含范围的每对可能的端点，这种边缘情况会稍微增加逻辑的复杂性。如果重要的是确定最小包含范围的值，或者仅报告代表最小包含范围的一对就足够了，那么提供的算法就足够了。
我正在尝试获取过去 X 秒内的 "range" 罗盘航向。示例：在最后一分钟，我的航向在罗盘上一直在 120 度和 140 度之间。够简单吧？我有一个数组，其中包含一段时间内的罗盘航向，例如每秒 1 个读数。
[ 125, 122, 120, 125, 130, 139, 140, 138 ]
我可以取 最小值和最大值 值，然后就可以了。我的范围是 从 120 到 140。
只是没那么简单。举个例子，如果我的航向从 10 度转移到 350 度（即它 "passed" 通过北方，改变 -20 度。
现在我的数组可能看起来像这样：
[ 9, 10, 6, 3, 358, 355, 350, 353 ]
现在最小值为 3，最大值为 358，这不是我需要的 :( 我正在寻找最大的 "right hand"（顺时针）值，并且大多数 "left hand"（逆时针）值。
我唯一能想到的方法是沿着包含数组中 none 个值的圆找到最大的圆弧，但我什至不知道该怎么做。
非常感谢任何帮助！
问题分析
总结一下这个问题，听起来你想要找到以下两个：
- 最接近的两个读数（为简单起见：顺时针方向）AND
- 包含它们之间的所有其他读数。
因此，在您的第二个示例中，9 和 10 仅相差 1°，但它们不包含所有其他读数。相反，从 10 顺时针移动到 9 将包含所有其他读数，但它们在那个方向上相隔 359°，因此它们不是最近的。
在这种情况下，我不确定使用最小和最大读数是否有帮助。相反，我建议对所有读数进行排序。然后您可以更轻松地检查上面指定的两个条件。
这是您提供的第二个示例，按升序排列：
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
如果我们从头开始，我们知道从阅读 3 到阅读 358 将涵盖所有其他阅读，但它们 358 - 3 = 355° 是分开的。我们可以继续逐步扫描结果。请注意，一旦我们绕了一圈，我们必须加上 360 才能正确计算分离度。
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
*--------------------------> 358 - 3 = 355° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
-> *----------------------------- (360 + 3) - 6 = 357° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
----> *-------------------------- (360 + 6) - 9 = 357° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
-------> *----------------------- (360 + 9) - 10 = 359° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
----------> *------------------- (360 + 10) - 350 = 20° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
--------------> *-------------- (360 + 350) - 353 = 357° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
-------------------> *--------- (360 + 353) - 355 = 358° separation
[ 3, 6, 9, 10, 350, 353, 355, 358 ]
------------------------> *---- (360 + 355) - 358 = 357° separation
伪代码解决方案
这里有一个伪代码算法，用于确定读取值的最小度数范围。如果性能是一个问题，肯定有一些方法可以优化它。
// Somehow, we need to get our reading data into the program, sorted
// in ascending order.
// If readings are always whole numbers, you can use an int[] array
// instead of a double[] array. If we use an int[] array here, change
// the "minimumInclusiveReadingRange" variable below to be an int too.
double[] readings = populateAndSortReadingsArray();
if (readings.length == 0)
{
// Handle case where no readings are provided. Show a warning,
// throw an error, or whatever the requirement is.
}
else
{
// We want to track the endpoints of the smallest inclusive range.
// These values will be overwritten each time a better range is found.
int minimumInclusiveEndpointIndex1;
int minimumInclusiveEndpointIndex2;
double minimumInclusiveReadingRange; // This is convenient, but not necessary.
// We could determine it using the
// endpoint indices instead.
// Check the range of the greatest and least readings first. Since
// the readings are sorted, the greatest reading is the last element.
// The least reading is the first element.
minimumInclusiveReadingRange = readings[array.length - 1] - readings[0];
minimumInclusiveEndpointIndex1 = 0;
minimumInclusiveEndpointIndex2 = array.length - 1;
// Potential to skip some processing. If the ends are 180 or less
// degrees apart, they represent the minimum inclusive reading range.
// The for loop below could be skipped.
for (int i = 1; i < array.length; i++)
{
if ((360.0 + readings[i-1]) - readings[i] < minimumInclusiveReadingRange)
{
minimumInclusiveReadingRange = (360.0 + readings[i-1]) - readings[i];
minimumInclusiveEndpointIndex1 = i;
minimumInclusiveEndpointIndex2 = i - 1;
}
}
// Most likely, there will be some different readings, but there is an
// edge case of all readings being the same:
if (minimumInclusiveReadingRange == 0.0)
{
print("All readings were the same: " + readings[0]);
}
else
{
print("The range of compass readings was: " + minimumInclusiveReadingRange +
" spanning from " + readings[minimumInclusiveEndpointIndex1] +
" to " + readings[minimumInclusiveEndpointIndex2]);
}
}
还有一种这种伪代码算法没有涵盖的边缘情况，即存在多个最小包含范围的情况...
- 示例 1：[0, 90, 180, 270] 范围为 270（90 到 0/360、180 到 90、270 到 180 和 0 到 270）。
- 示例 2：[85, 95, 265, 275] 范围为 190（85 到 275 和 265 到 95）
如果有必要报告创建最小包含范围的每对可能的端点，这种边缘情况会稍微增加逻辑的复杂性。如果重要的是确定最小包含范围的值，或者仅报告代表最小包含范围的一对就足够了，那么提供的算法就足够了。