作一条直线，求思路

mahuan1279

先求出多段线凸包，然后求均值点（X=Σxi/N,Y=Σyi/N）所在的竖直线与凸包相交的那条边线即所求。

自贡黄明儒

highflybird 发表于 2025-7-21 14:17
经过发现，此问题可以在O(N*log(N))时间复杂度 内求解，下面是求解的lisp代码：

感谢大师，直接给出了答案。

mahuan1279

highflybird 发表于 2025-7-21 14:29
发一个演示上来，可以看到效率应该没问题。

是不是判断有点问题？检测图中似乎结果不对。

highflybird

mahuan1279 发表于 2025-7-22 16:04
是不是判断有点问题？检测图中似乎结果不对。

问了一下楼主可能那个间距20等分的可以不需要。

如果需要20等分的话，下面的程序和你的输出结果是一致的。

mahuan1279

highflybird 发表于 2025-7-22 21:00
问了一下楼主可能那个间距20等分的可以不需要。

如果需要20等分的话，下面的程序和你的输出结果是一致 ...

还是有问题。

highflybird

mahuan1279 发表于 2025-7-22 21:44
还是有问题。

重新上传了，你再测试一下

mahuan1279

highflybird 发表于 2025-7-22 21:56
重新上传了，你再测试一下

这下应该是对的了！

mahuan1279

highflybird 发表于 2025-7-22 21:56
重新上传了，你再测试一下

逐一累加，然后选取最小和值，是吧？

mahuan1279

highflybird 发表于 2025-7-22 21:00
问了一下楼主可能那个间距20等分的可以不需要。

如果需要20等分的话，下面的程序和你的输出结果是一致 ...

感觉复杂度可以优化到O（N）。根据推理演算可知，最佳直线必然经过凸包上两点，且与中垂线有交点，必然一顶点在左半图，一顶点在右半图，使用左右指针来依次寻找此两点（左顶点序号1~N/2,右顶点序号N~N/2），不符合要求的顶点依次舍去，最终求得的经过两点的直线就是最佳直线。向左搜点使得直线斜率值减小，向右搜点使得直线斜率值增大。注意收尾时细节处理，左顶点序号不超过N/2,当中间搜到LiRj时，且此时固定Rj,继续依次搜索L(i+1)~L(N/2),均不能使直线斜率值减小时则固定Li直接依次搜索R(j-1)~R(N/2),斜率最大的直线即是最佳直线。同理，右顶点序号不小于N/2,当中间搜到LiRj时，且此时固定Li,继续依次搜索R(j-1)~R(N/2),均不能使直线斜率值增大时，则固定Rj直接依次搜索L(i+1)~L(N/2),斜率最小的直线即是最佳直线。每个点都只搜索了一遍，复杂度为O(N)。

mahuan1279

highflybird 发表于 2025-7-22 21:00
问了一下楼主可能那个间距20等分的可以不需要。

如果需要20等分的话，下面的程序和你的输出结果是一致 ...

如果不是等距划分，可以按点的横坐标来划分。