python中如何高效地求图的上边界线

Question

我有一组图，我想从中找到一个轮廓图（图this中的黑线）

不可能在x轴上的所有点上找到每个图形的最大值，因为所有图形的x值都不相同。这些点精确到小数点后几位。this图可能有助于更好地理解。你知道吗

我试着将每个图形转换成一个多边形，使用形状级联的联合，然后裁剪底部。 它适用于少量的图，但是当图的数量变大时。这需要很多时间。你知道吗

还有其他有效的方法吗？你知道吗

Answer 1

按x坐标对所有点进行排序。你知道吗

最终输出的像素数有限。您可以计算每个像素内的x值范围（小范围但不是0）。所以把你的分数分成桶。因为它们已经被排序，所以您只需要在列表中前进，直到值属于下一个范围。你知道吗

对于每个像素列，计算您找到的最大y值。在（x，y）处添加一点作为黑线。你知道吗

其复杂性为o（nlogn）。你知道吗

如果在x轴上有间隙，可以选择跳过它并在黑线中有间隙，或者只是在相邻值之间进行插值。如果将黑线绘制为线段的集合，则可以跳过为该列生成点，并让渲染器为您执行插值。你知道吗

如果你的原始点太少（他们跳过像素），你的线可能看起来参差不齐（跳上跳下）。在这个范围内添加一个不能避免的插值函数。线性插值应该工作得很好。确保在间隔的开始和结束处生成一个点，并取较大的y值。你知道吗