c++ - 在对任意区域有限制的二维空间中找到有效点

Question

我有一个二维 double 空间，其中的区域(任意定义，主要是圆圈)是“无效的”，可以这么说，我想得到最近的有效点，给定一个所需的目的地(那不是'必须有效)。到目前为止，我已经尝试从个案的角度出发来避免这些区域，但是当存在多个约束时(比如必须避免 2-3 个靠近/混合在一起的区域)，这种方法不起作用。我考虑过某种搜索，但将空间离散化将是另一个问题，因为这些区域不会真正符合它。

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

谢谢!

Answer 1

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

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