找到一个线段是否是完全内部的多边形或不 [英] Finding whether a line segment is completely inside the Polygon or not

问题描述

我如何能找到一个给定的对角线（线段连接面比多边形边缘之外的两个顶点）是否是一个给定的多边形有效的对角..？我写code在LEDA。有在LEDA验证对角线任何特定的功能。？需要帮忙。

How I can find whether a given diagonal(line segment joining two vertices of polygon other than polygon edge) is valid diagonal for a given polygon ..? I am writing code in LEDA. Is there any specific function in LEDA for validating diagonal .? need help.

推荐答案

您可以致电路口的多边形方法，该方法将返回路口与段。如果有其他的交叉点比两个端点（即超过2交点），那么它是无效的。下面是函数的声明：

You can call the intersection method of your polygon which will return the intersections with a segment. If there are other intersections than the two endpoints (i.e. more than 2 intersections) then it is not valid. Here is the function declaration:

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

更新：由于j_random_hacker指出，这可能失败，如果对角线是多边形之外。对于弱简单多边形这可避免通过检查该段的内点位于多边形外

UPDATE: As j_random_hacker pointed out this can fail if the diagonal is outside the polygon. For weakly simple polygons this could be avoided by checking if an inner point of the segment lies outside the polygon.

bool   Polygon.outside(const POINT& p)

然而，这仍然无法对复杂的多边形像自相交的。根据什么是一个有效的对角甚至有可能为弱简单的多边形失败，如果有连接孔的边界和多边形的外边界重合边缘。

However this could still fail for complex polygons like self-intersecting ones. Depending on what is a valid diagonal it could even fail for weakly simple polygons if there are coincident edges connecting the boundary of a hole and the outside boundary of a polygon.

这篇关于找到一个线段是否是完全内部的多边形或不的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！