两个多边形之间的点如何找到它属于哪个？

Question

使用什么算法，以便我们可以确定如果红点属于Area1或Area2。 我最初的想法是使用连续点将多边形分成三角形，然后使用已知算法确定点是否属于这些三角形中的一个，但是存在图中所示的问题.p4 p5 p6是区域1中的点，但是他们在区域2中制作一个三角形。

Answer 1

继续从红点到任何方向的入射光线。计算这种射线与任何多边形的相切。即使交点的计数指示点位于多边形

Answer 2

这里的外面是观念 -

1. 画一条水平线的红点权，并将其扩展到无限

2. 数数该线与多边形边相交的时间。

3. 的点是多边形内部如果交点的任一数是奇数还是 点位于边缘

参见Check if a point lies inside or outside a polygon。

Answer 3

您可以使用多边形填充算法的想法。如果您知道多边形的顶点，则可以通过红色点放置水平光线并计算它相交的顶点。如果计数是偶数的话，那就在外面，否则就在里面。

如果您想象沿着那条光线从最左侧出现，则第一个交点将进入多边形，第二个交点将离开它，第三个交点将再次进入......依此类推。所以如果这个数字是奇数（1,3,5，...），当你点到点时你就在多边形内，否则你就在外面。