algorithm - 如何对旋转矩形的点进行排序？

Question

它是度数小于 90 的旋转矩形。它可以是顺时针或逆时针。我喜欢将这些点排序为矩形的原始序列。像文本注释一样，1、2、3、4……

我的算法是： 1.找到最左、右、上、最下的点， 2.比较top.x和bottom.x 3.根据比较值，可以找到四个角的序列。4.从四个角点，计算矩形边缘的线函数，然后排列其他点。

我不确定是否有另一种更有效或更优雅的算法来解决这个问题。谢谢你。

Answer 1

假设矩形已顺时针旋转小于 90 度。在这种情况下，请注意顶行中的第 (i+1) 个点始终位于第 i 个点的下方和右侧。所以我们可以剥离行：

1. 按 y 坐标（即从上到下）对所有点进行降序排序。
2. 将这些排序的点放在一个链表中。（这不是必需的，但会使点删除更有效。）
3. 设置 i = 1。
4. 设置 lastX = -inf。
5. 设置 p 指向已排序的点列表中的第一个元素。如果没有剩余元素，我们就完成了。
6. 从 p 开始，扫描点列表，直到找到 x 坐标大于 lastX 的点，表明它在上一个添加的点的右侧。（在每一行的第一次迭代中，这将始终取列表中的第一个点。）

7. 如果能找到这样一个点：

   • 从链表中删除该点并将其标记为 i。
   • 将 p 设置为列表中的下一个点。
   • 设置 i = i + 1。
   • 将 lastX 设置为刚刚添加的点的 x 坐标。
   • 转到 6 以查找该行中的下一个点。

   除此以外：

   • 我们已经完成了这一行，并且其中的所有点都已从链表中删除。转到 4 开始下一行。

这是一个 O(n^2) 算法，因为一旦找到了一行中最右边的点，它就会浪费地遍历所有剩余的点，然后再从顶部开始处理下一行。这可能已经足够好了，但是时间复杂度可以降低到 O(nlog n)通过维护一个包含从左到右排序的所有点的单独链表，并在自上而下列表中的每个节点中提供一个额外的字段，该字段指向从左到右列表中的相应节点。由于最上面一行中最右边的点始终是整个点集中的最右边的点，我们可以通过测试刚刚删除的点是否对应于整个点中的最后一个点来检测一行何时在 O(1) 时间内完成从左到右的列表。每当从自上而下的列表中删除一个点时，它也必须从从左到右的列表中删除。

但是如果矩形逆时针旋转呢？ 正如评论者 nm 指出的那样，如果没有进一步的信息，就无法将这种情况与顺时针旋转区分开来：逆时针旋转 d 度的 n x m 矩形看起来与顺时针旋转 (90-d) 度的 m x n 矩形完全一样。如果您有一些其他信息可以区分这些情况，则可以使用与以前相同的算法处理逆时针旋转，但要注意第一行（或任何行）的宽度，然后重新排列标签。