我被给定为输入 n 对整数，它们描述了 2D 平面中的点，这些点提前知道是某个凸多边形的顶点。我想以顺时针或逆时针的方式有效地对这些点进行排序。
起初我想做一些类似于 Graham Scan 的初始步骤，但我看不到一种简单的方法来打破与锚点成相同角度的顶点的关系。请注意，当您沿着多边形的边走时，有时这些顶点可能会越来越靠近锚点，有时它们可能会越来越远。
似乎确实有效的方法是在多边形内部产生一个点（例如，n 个点的平均值），并使用它作为输入径向排序的锚点。事实上，因为锚点位于内部，所以从它发出的任何光线最多包含一个输入点，因此不会有联系。
整体复杂度不受影响：计算中点是 O(n) 任务，瓶颈是实际排序。
这确实涉及比有希望的 Graham Scan 版本更多的操作（我们假设没有要打破的关系），但更大的损失是通过在混合中引入除法来留下整数算术。
反过来，这可以通过将所有内容缩放 n 倍来解决，但在这一点上，这似乎是在抓住稻草。
我错过了什么吗？有没有一种更简单、更有效的方法来解决这个排序问题，最好是可以避免浮点计算的方法？