不规则形状内部的点

Question

我并不是一名专业的程序员，所以请不要期望我在这里使用复杂的方法或语言。但我会非常感谢您提供的建议和推荐，帮助我实现一个算法，以便稍后将其编程添加到我的项目中... 这就是问题所在：

假设空间中有一个任意点（点X），具有以下属性： - 具有坐标 - 位于二维表面上 - 静止不动 - 在任何给定时间都属于单个区域（其边界坐标也已知）。换句话说，它是其“父”元素的唯一“子”元素。如果它不在一个区域内，那么它肯定在另一个区域内！

一个区域不是简单的正方形、四边形或圆形，而是一个不规则的形状。

现在，我的问题是：如何确定： (i) 点X是否位于特定区域内而不是相邻区域； (ii) 点属于哪个特定区域（A、B或C集合中的哪个）？请参见链接的图像以更好地理解问题：

PS：我研究了处理点在多边形内问题的可能性（特别是，“射线投射算法”听起来非常聪明！），但似乎并不是解决方案，因为（i）区域可能相邻；（ii）我需要确定点所属的区域，而不仅仅是它在内部/外部。

非常感谢您提前的帮助！！！

- Rustam Alhas

---

如果区域的边界可能有曲率，那么这些区域的“边界坐标”如何代表实际边界？您是否使用某种曲线参数化或者通过多边形逼近来表示该区域？ - ajd

一种变体的射线投射算法可能会起作用。如果您从您的点投射出一条射线并查看它所击中的第一条边，那么您将知道您的点位于共享该边缘的（最多）两个区域之一内。然后，您可以为每个候选区域使用两次射线投射算法。 - ajd

抱歉，我的错 - 我进一步编辑了我的问题：形状（区域）段的坐标在2D中定义，没有曲率！ - Rustam Alhas

你有被限定区域的坐标吗？如果有，那么你有多少个坐标？我不知道你所拥有的确切输入数据是什么。我假设你有足够的坐标来绘制一个良好的近似区域。在这种情况下，一种解决方案是找出具有最大和最小X坐标值的点。这给出了X轴上区域的边界。如果你的点位于该区域内，它的x坐标必须在这些值之间。对Y坐标执行相同的操作。但是，这可能不是一种有效的算法。 - sandyiscool

不确定您所说的“我需要确定一个点所属的区域，而不仅仅是它在内部/外部的位置。”的意思。除非您使用了我不理解的“所属于”的含义，否则您确定点属于哪个区域的方式是通过测试它是否在您集合中的每个可能的区域内：它将恰好在其中1个区域内。 （正如sandyiscool建议的那样，您可以通过使用边界框/圆来消除一些区域作为可能性，从而加快速度。） - j_random_hacker

Answer 1

一个程序员会这样做：

1. 编写一个函数，该函数接受一个区域数组和一个点作为参数。

2. 进行循环 - 检查所有的区域，并对于每个区域

   通过射线投射算法检查该点是否属于该区域。

   如果不是，则继续循环，

   如果是，则完成函数并返回当前区域的编号。

3. 如果您已经超出了所有区域，则返回-1。

当然，您可以改进算法，考虑公共边界，不重复计算它们的角度，但这些算法显然超出了您现在的能力范围。即使是一个好的程序员也会从易到难开始，但要保证其可行性。

- Gangnus