找到一组点的中心,顺时针对它们进行排序？
jma*_*erx 6 c++ algorithm geometry computational-geometry
我想按顺时针方向对点矢量进行排序以形成多边形,但我需要适当的中心来完成.我已经尝试过averages方法,但有些要点根本没有正确排序.找到顺时针分拣点时工作中心的正确方法是什么？
凹陷部分失败了
谢谢
这是一张图片:
绿色圆圈是中心.
它应该看起来更像这样:
AnT*_*AnT 11
如果您没有预先定义的中心点,则"按顺时针顺序排序"的概念没有明确定义.
如果你所拥有的只是一堆你需要排序的点,并且你事先并不知道中心,那么这个问题通常没有一个解决方案.该问题有许多替代解决方案,每个解决方案都会为您提供不同的多边形.
此外,找到一个允许您通过CW(或CCW)排序重新创建原始多边形的中心只能用于特殊类别的多边形:所谓的星形多边形.星形多边形的主要特性是可以在多边形内部找到一个点,多边形的整个内部是"可观察的"(我希望很明显没有定义"可观察"的含义).
如果您的多边形不是星形,那么这个中心点就不存在了.并且,由于这个原因,无法通过CW排序重新创建原始多边形.
图片中的牛轮廓显然不是星形多边形,这意味着您将永远无法通过对某个中心,任何中心周围的点进行排序来重新创建原始的牛轮廓.没有"正确的方法".这不可能.
- @Milo:如果轮廓上的点非常密集地打包(特别是在弯曲的部分),那么你可以通过从一个点跳到下一个最近点来重新创建牛.但是,如果点数不够密集,那么在某些地方可能会出现错误.通常情况下,根本无法从无序的点集重新创建原始轮廓.如上所述,有许多不同的轮廓可以从一组点构建.由于您无法决定哪一个是正确的,因此您无法重新创建它. (2认同)