algorithm - 哪些线段在多边形内至少有一个端点？

我有一个问题正在考虑：

我们有一组线段和一个多边形。找到至少有一个端点在多边形内的线段的算法是什么？

编辑：我们可以假设多边形总是凸的。

Edit2：我想用段交叉点来解决这个问题，但我真的不知道怎么做。

Edit3：现在我想也许可以尝试使用 Point In Polygon 算法，对吗？我可以暂时忘记段，因为我感兴趣的只是段的末端，它们是点，对吗？所以也许我可以以某种方式检查所有点是否在多边形内。对于其中的这些，我们有答案。

标签： algorithmgeometry

将多边形分解为具有两个水平边的梯形（使用通过多边形顶点的水平线）

过滤掉位于多边形边界框之外的点

对于每个端点，通过 Y 坐标的二进制搜索和左/右梯形边缘的一些数学运算，查找是否位于某个梯形中。

让我们找到合适的梯形，我们知道梯形顶部和底部 Y (and bottom<=py<=top)，以及左右边缘方程。如果左上点为(xlt, top)，左下点为(xlb, bottom)则左边缘方程为

x * (top - bottom) + y * (xlb - xlt) + (xlt * bottom - xlb * top) = 0

与右边缘类似xrt, xrb。

当我们将端点坐标代px, px入这个表达式时，我们会得到一些值。该值的符号告诉我们点相对于线的位置（哪一侧）。

如果左右线的符号不同，则点在边之间，即在梯形内。