c - 如何找到多边形内沿 vector 的最长距离？

Question

给定一个方向 vector 和一个任意多边形(可以是非凸多边形)，什么是沿着由多边形界定的 vector 找到最长直线的有效算法？

注意:与上述问题有些相关的原始问题是:给定一个三角形，找到给定多边形内最大的有界相似三角形。

Answer 1

这是您第一个问题的 O(n log n) 时间扫描线算法(“原始”看起来更难)。

不失一般性地假设 vector 为 (1, 0)。假设没有退化(这对我来说有点顽皮)。对于多边形的每条边，为具有较小 y 坐标的顶点创建一个“开始”事件，为具有较大 y 坐标的顶点创建一个“停止”事件。按 y 坐标对事件进行排序，并从小到大处理它们。对于开始事件，将边插入到由边与当前扫掠线的交点的 x 坐标作为键控的有序集中。对于停止事件，删除边缘。在对集合进行操作之前和之后，检查在插入/删除点连接两条边的扫描线段是否比目前找到的最长线段长。 (可以通过相对于多边形以逆时针顺序遍历的这两条边是 y 递增还是 y 递减来判断线段是否在多边形内部。)