如何发现物体何时改变运动方向

Question

问题：

1. 一个球在失去动力并开始一段时间后被抛起 后退
2. 一辆汽车沿 x 方向行驶并掉头并开始返回
3. 行星顺行并在某个时间点逆行

我们有：

• 定期读取物体位置。 （下面的例子）

| datetime            | position | direction               |
|---------------------|----------|-------------------------|
| .......             | ..       | ...                     |
| 2024-02-10 10:00:00 | 15       | ..                      |
| 2024-02-11 10:00:00 | 17       | forward (17 - 15 = 2)   |
| 2024-02-12 10:00:00 | 20       | forward (20 - 17 = 3)   |
| 2024-02-13 10:00:00 | 21       | forward (21 - 20 = 1)   |
| 2024-02-14 10:00:00 | 22       | forward (22 - 21 = 1)   |
| 2024-02-15 10:00:00 | 21       | backward (21 - 22 = -1) |
| 2024-02-16 10:00:00 | 19       | backward (19 - 21 = -2) |
| .....               | ..       | ..                      |

• 一个函数，它为我们提供给定时间点的对象位置

  position(datetime)

    func position(datetime){
        return position
    }

从上面的示例读数中，我们用前一个位置减去一个位置，并确定物体是否仍在沿相同方向移动或已改变方向。 IE。自

21 - 22 = -1

以来，第 14 个和第 15 个物体之间的某个位置改变了其运动方向。

我们必须找到物体改变方向的确切时间。
您建议找到时间的最佳方式是什么？
除了检查每一分钟或每一秒之外的任何事情，因为

position()

的计算成本很高

我尝试通过检查中点并根据它向左或向右移动边界来使用二分搜索。但它仍然不起作用，因为在 t0 之后，对象仍然可以朝同一方向移动。

我对问题的格式感到抱歉。我无法在这里发布确切的问题。所以我用了一些类似案例的例子。请随时要求更多说明

Answer 1

最佳效果取决于功能。

想法仍然是这样。您需要考虑 3 个点：

low

、

mid

和

high

。你知道他们的立场。你知道吗

position_mid >= max(position_low, position_high)

。

通过某种方式，您会选择介于

choose

和

low

之间或介于

mid

和

mid

之间的

high

。然后你就缩小了这个逻辑的范围：

try_choice(low, low_position, mid, mid_position, high, high_position, choose):
    choose_position = position(choose)
    if choose < mid:
        if choose_position <= position_mid:
            return (choose, choose_position, mid, mid_position, high, high_position)
        elif low_position <= choose_position:
            return (low, low_position, choose, choose_position, mid, mid_position)
        else:
            # it looks like we were falling at low, let's find the peak from choose to high
            return (choose, choose_position, mid, mid_position, high, high_position)
    else:
        if choose_position <= position_mid:
            return (low, low_position, mid, mid_position, choose, choose_position)
        elif high_position <= choose_position:
            return (low, low_position, choose, mid, mid_position, choose, choose_position)
        else:
            # it looks like we were falling at high, let's find the peak from low to choose
            return (low, low_position, mid, mid_position, choose, choose_position)

现在我们如何选择答案？

一种选择是我们取更宽区间的中点，

(low, mid)

或

(mid, high)

。这总是能让我们摆脱至少 1/4 的范围。因此，范围每次都会缩小一个常数因子，并且所需的总步数是我们想要的精度的对数。

另一种选择是我们根据现有的三个点绘制二次方程，并尝试猜测峰值在哪里。如果我们已经接近解决方案，这将比我们现有的观点好得多。

还有一个选择是看看峰值应该在哪里，然后稍微超过它。不仅要猜测我们认为的峰值在哪里，还要尝试确保将其限制在较小的范围内。

对于最佳算法，我认为您可以使用所有三种方法。逻辑可能看起来像这样 1-2 猜测逻辑：

generate candidate from quadratic fit
if the candidate is in the smaller of the two intervals:
    try candidate
        if candidate didn't wind up as midpoint:
            then try splitting larger interval
else:
    if candidate is < 1/3 from mid as the end:
        try just a bit past the candidate away from the mid
        if that did not wind up as end:
            then try splitting larger interval
    else:
        just split the larger interval

我们的想法是，我们的精度永远不会比对数差，但有时我们会好得多。