如何确定一个对角线是在一个凹多边形内还是外？ [英] How to determine a diagonal is in or out of a concave polygon?

问题描述

凹形（非凸形）多边形的对角线（对角线是连接不相邻顶点的线段）可以完全位于多边形之内或之外（或者可以与多边形的边相交）。如何确定它是否完全处于多边形？（没有多边形测试的方法）。

解决方案如果对角线与边缘至少有一个交点，则它的一部分位于多边形内部并且部分位于该多边形之外，但是，如果对角线与它们没有交集，则只有两种状态：它是完全的或完全在多边形之外。

确定它是在多边形之内还是之外：

假设多边形的顶点逆时针排序。考虑位于名为P [i]的顶点（另一个端点是p [j]）的对角线的端点之一。然后，制作三个向量，其第一点是p [i]：

V1：p [i + 1] - p [i]

V2：p [i-1] - p [i]

V3：p [j] - p [i]

当且仅当V3在V1和V2之间时，我们逆时针从V1移动到V2时，对角线完全位于多边形中。

替代文字http://www.freeimagehosting.net/uploads/1b97107f4a.jpg

当我们从V1逆时针走向V2时，如何确定V3是否在V1和V2之间？去在这里。

我已经使用这种方法编写了一个程序，它可以有效地工作。 b $ b

The diagonal (a diagonal is a segment connecting nonadjacent vertices) of a concave (non-convex) polygon can be completely in or out of the polygon(or can intersect with the edges of polygon). How to determine whether it is completely in the polygon?(a method without point-in-polygon test).

解决方案

If the diagonal has at least one intersection with the edges, it is partially in and partially out of the polygon, however, If the diagonal has no intersection with them, there are only two states: it is compeletely in or completely out of the polygon.

To determine whether it is in or out of the polygon:

Suppose polygon's vertices are sorted counterclockwise. Consider one of the endpoints of the diagonal which lies on the vertex named P[i] (the other endpoint is p[j]). Then, Make three vectors whose first points are p[i] :

V1 : p[i+1] - p[i]

V2 : p[i-1] - p[i]

V3 : p[j] - p[i]

The diagonal is completely in the polygon if and only if V3 is between V1 and V2 when we move around counterclockwise from V1 to V2.

alt text http://www.freeimagehosting.net/uploads/1b97107f4a.jpg

How to determine whether V3 is between V1 and V2 when we go from V1 to V2 counterclockwise? go to here.

I've written a program using this method and it works effectively .

这篇关于如何确定一个对角线是在一个凹多边形内还是外？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！