问题描述
说我有一个多边形。它可以是一个凸的一个或不是，它并不重要，但它不具有孔。它也有内的顶点和边，这意味着它是分配。
Say I have a polygon. It can be a convex one or not, it doesn't matter, but it doesn't have holes. It also has "inner" vertices and edges, meaning that it is partitioned.
有没有当我要检查，如果一个点是那种多边形内部的任何一种流行/已知算法或标准程序？
Is there any kind of popular/known algorithm or standard procedures for when I want to check if a point is inside that kind of polygon?
我这么问是因为匝数和光线投射不是在这种情况下，准确
I'm asking because Winding Number and Ray Casting aren't accurate in this case
在此先感谢
推荐答案
您需要澄清你所说的内在的顶点和边'的意思。让我们以一个非常一般的情况下，希望你找到的相关性。
You need to clarify what you mean by 'inner vertices and edges'. Let's take a very general case and hope that you find relevance.
的射线浇铸（点在多边形）算法拍摄断一个射线与该多边形的边计数的交点（奇数交叉口=内，即使=外）。
因此，它准确地给出正确的结果，无论您从相交梯形孔或三角孔（内边缘？）内启动或即使多边形的一部分，是完全分离式和/或自相交。
但是，在什么样的顺序做你喂使得所有点被正确计算多边形的顶点问题
虽然这是code具体地说，如果您使用的是计算每一个路口与多边形的边的实现，那么这种做法将工作 - 中国 - 打破主多边形到多边形元素。例如： - 梯形洞是一个多边形组成部分
。 - 开始与（0,0）的顶点（无所谓是否（0,0），在于WRT您的多边形），接着由第一组件的顶点，最后的顶点后重复其第一顶点。 - 包括另一个（0,0）的顶点
。 - 包含下一个组件，最后一个顶点之后，重复它的第一个顶点
。 - 重复上述两个步骤为每个组件
。 - 结束与最后的（0,0）的顶点
。2成分EG-让两种组分的顶点是（1×，1Y），（2X，2Y），（3×，3Y）和（AX，AY），（Bx的，通过），（CX，CY）。凡（AX，AY），（BX，BY），（CX，CY）可能是从一个不相交的三角孔什么，相交三角形或分开三角形。
因此，一个单一的连续多边形在数学上等同于2部件的顶点是 -
The ray casting (point in polygon) algorithm shoots off a ray counting the intersections with the sides of the POLYGON (Odd intersections = inside, Even = outside).
Hence it accurately gives the correct result regardless of whether you start from inside the disjoint trapezoidal hole or the triangular hole (inner edges?) or even if a part of the polygon is completely seperated and/or self intersecting.
However, in what order do you feed the vertices of the polygon such that all the points are evaluated correctly?
Though this is code specific, if you're using an implementation that is counting every intersection with the sides of the polygon then this approach will work -
- Break the master polygon into polygonal components. eg - trapezoidal hole is a polygonal component.
- Start with (0,0) vertex (doesn't matter whether (0,0) actually lies wrt your polygon) followed by the first component' vertices, repeating its first vertex after the last vertex.- Include another (0,0) vertex.
- Include the next component , repeating its first vertex after the last vertex.
- Repeat the above two steps for each component.
- End with a final (0,0) vertex.
2 component eg- Let the vertices of the two components be (1x,1y), (2x,2y), (3x,3y) and (Ax,Ay), (Bx,By), (Cx,Cy). Where (Ax,Ay), (Bx,By), (Cx,Cy) could be anything from a disjoint triangular hole, intersecting triangle or separated triangle.
Hence , the vertices of a singular continous polygon which is mathematically equivalent to the 2 components is -
(0,0),(1x,1y),(2x,2y),(3x,3y),(1x,1y),(0,0),(Ax,Ay),(Bx,By),(Cx,Cy),(Ax,Ay),(0,0)
要了解它是如何工作的，试上一刮pad.-
绘制这个数学上等价的多边形1.标记所有顶点，但不加入他们呢。
2.标记重复顶点分别也。为此，标志着他们接近原始点，而不是他们。 （在距离电子邮件，其中 E-> 0 （趋于/办法））（以帮助观察）
3.现在加入以正确的顺序所有顶点（如上面的例子）
你会发现，这个形成连续的多边形，只有变得不相交的E = 0的限制。
现在，您可以发送该数学上等价多边形以你的光线投射功能（甚至蜿蜒数函数吗？）没有任何问题。
To understand how it works, try drawing this mathematically equivalent polygon on a scratch pad.-
1. Mark all the vertices but don't join them yet.
2. Mark the repeated vertices separately also. Do this by marking them close to the original points, but not on them. (at a distance e, where e->0 (tends to/approaches) ) (to help visualize)
3. Now join all the vertices in the right order (as in the example above)
You will notice that this forms a continuous polygon and only becomes disjoint at the e=0 limit.
You can now send this mathematically equivalent polygon to your ray casting function (and maybe even winding number function?) without any issues.
这篇关于点任意多边形的分区里面的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！