旋转行扫描分选边

Question

我正在尝试实现Lee的可见性图。

可能有n个多边形，其中多边形的每一边都是边。假设有一个点p1，一个与p1处的正x轴平行的半线性。我需要找到与r相交的边，并按排序顺序存储它们。

首先由r行相交的边具有较高的优先级，而较近的边具有较高的优先级，但当看到>距离时。

例如，p1 = (0，1)，以及具有以下顶点{(2，4)，(3,6)，(5，20)}的多边形。这个多边形的边应该排序为((2,4)，(5，20)，((2，4)，(3，6)，(3，6)，(5，20))。

因此，，我如何排序这些边

(如果你去看这个链接，我想你会有一个更好的主意，对不起我的解释)。

我的主要想法是:从p1到r所遇到的边的第一个顶点的距离和天使对它们进行排序。但是，所有的顶点都有多个边(因为每个顶点/边都是多边形的一部分)，我不知道如何对这两个边进行排序。

任何想法或暗示都将不胜感激。

只是一些参考资料，：https://taipanrex.github.io/2016/10/19/Distance-Tables-Part-2-Lees-Visibility-Graph-Algorithm.html 和一本书：计算几何、ALgorithms和应用。

Answer 1

我为那些感兴趣的人找到了一种方法：

扫描线是逆时针旋转的，它的有序边是在遇到该边的第一个顶点时进行测量的，即:半直线的初始位置(当它与正x轴平行时)与所遇到的顶点之间的夹角、p1与遇到的顶点之间的距离。越小的角度和距离越好，角度也比距离有更高的优先级。

我也做了第三次测量，因为半线旋转，当它到达一个顶点时，它应该相交，因此我取了半线和顶点边缘之间的角度。角度越大，这个角度的优先级就越高，因为这意味着边缘越近。这个角度是用半条线来区分具有相同第一次遇到的顶点的边。因此，这种测量的优先级是最低的。

希望这能帮上忙。