visual-c++ - 给定两条曲线（都由某些点组成），确定一条曲线在另一条曲线上的点数

Question

如图所示，两条曲线都是样条线，并且点有限。我想弄清楚绿点的数量。有什么想法吗？

标签： visual-c++pointcurve

Answer 1

我假设黑色曲线是 x 单调的（否则“一个高于另一个”术语可能不明确）。

一种简单的方法是将黑色曲线视为折线，并为p红色曲线上的每个点找到q折线上具有相同 x 坐标的点。那么绿点是那些py 坐标大于它们对应的 y 坐标的点q。

找到q与给定p数量相对应的点以越过折线的线段并识别具有一个端点具有较小 x 坐标而另一个端点具有较大 x 坐标的线段。一旦有了这样的段， y 值q就只是一个线性插值。

由于折线是 x 单调的，所以点的 x 坐标是排序的。因此，可以使用对数二进制搜索有效地完成对相应段的搜索。