algorithm - 查找线段是否完全在多边形内

Question

我如何才能找到给定的对角线（连接多边形的两个顶点而不是多边形边缘的线段）是否是给定多边形的有效对角线..？我正在 LEDA 中编写代码。LEDA 中是否有任何特定功能用于验证对角线。？需要帮忙。

Answer 1

您可以调用intersection多边形的方法，该方法将返回与段的交点。如果有两个端点以外的其他交叉点（即超过 2 个交叉点），则它是无效的。这是函数声明：

list<POINT> Polygon.intersection(const SEGMENT& s)

更新：正如 j_random_hacker 指出的，如果对角线在多边形之外，这可能会失败。对于弱简单的多边形，可以通过检查线段的内部点是否位于多边形之外来避免这种情况。

bool   Polygon.outside(const POINT& p)

然而，对于像自相交这样的复杂多边形，这仍然可能失败。根据什么是有效对角线，如果存在连接孔边界和多边形外边界的重合边，则对于弱简单多边形甚至可能会失败。