在2维空间中寻找对任意区域有限制的有效点

Question

我有一个2D双精度空间，其中的区域(任意定义，大部分是圆)是“无效的”，所以可以这么说，我想得到最近的有效点，给定一个期望的目的地(不一定是有效的)。现在，到目前为止，我已经尝试了从逐个案例的基础上来避免这些区域，但是当有多个约束时(比如必须避免2-3个接近/混合在一起的区域)，这种方法不起作用。我考虑过某种搜索，但将空间离散化将是另一个问题，因为这些区域不会真正符合它。

我希望你们能就如何解决这样的问题给我一些建议。一个相关但简单得多的案例是this。

谢谢!

Answer 1

这基本上是不可能的，除非你能对这些无效区域施加一些约束。

考虑一个无效区域(或区域的联合)，其形式为一个大的不规则斑点，其中某处有一个微小的有效针孔。假设您的目的地是在针孔附近的斑点内，因此所需的点实际上是在针孔中。如果检查这个斑点的唯一方法是使用yes/no方法来测试点的有效性，那么找到针孔的唯一方法就是穷举搜索，这将永远花费时间。

Answer 2

如果所有的无效区域都是不相交的，那么问题是可控的。对于给定点，如果它在其中一个区域内，则在区域边界上查找最近的点。这不一定是微不足道的，但应该有很多参考资料-甚至在这个网站上-来做这件事，考虑到各种类型的边界-直线，圆弧，圆，样条等。

如果区域不是不相交的，则可以将它们合并为不相交的区域。CGAL provides libraries for 2D booleans (具体地说是联合)。