algorithm - 如何覆盖平面中具有恒定半径的不相交圆的一组圆？

Question

所以你有一个给定尺寸的片材/区域，并且在这个区域内是孔（它们的中心点（x，y）和半径是给定的）。问题是您需要用补丁覆盖这些孔。这些圆形贴片具有固定的半径（即：半径为 5），不允许相互重叠（但可以接触）。您可以使用尽可能多的数量，目标不是找到最佳数量，而是查看是否有可能覆盖每个孔。

我已经用 KD 树解决了一个类似的问题，但是由于这个问题中孔洞的 3D 维度性质，我不确定如何解决它。只是寻找正确方向的指针，而不是编码解决方案:)

标签： algorithmgeometrylanguage-agnosticmathematical-optimizationcomputational-geometry

Answer 1

您可能正在为此寻找分析或至少是确定性的解决方案。但我担心它太复杂了，没有一个。另一方面，像EA这样的元启发式算法由于其随机性而可以应对此类问题。当您决定采用这种方法时，您必须将问题更改为优化问题。

我尝试使用基本形式的DE 算法来解决这个问题。为了定义一个优化问题，我假设一个解向量是一个2*N浮点变量数组，其中N是孔的数量。该数组表示补丁X的Y坐标，因为N最多需要补丁来覆盖N孔。

成本函数（需要最小化）定义如下：

Find closest patch to each hole
Find A1 as sum of uncovered areas of holes by their closest patchs
Find A2 as sum of intersection areas of active(!) patches
return max(A1, A2)

在此功能中，活动补丁是最接近至少一个孔的补丁。这个定义被添加到问题中，以涵盖您在对 Ripi2 的回答的评论中提到的情况（当一个补丁覆盖两个洞时，还有另一个无用的补丁）。为了更具描述性，让我们假设这个P1补丁不是最接近任何洞的补丁。H1是最接近这个补丁的洞，但它最近的补丁是P2. 所以我们可以肯定地说 和 的交集面积H1小于P1或等于 和 的H1一个P2。由于它最近的洞是这样的，所以所有其他洞都是一样的，所以让我们认为它不存在！

这是一个示例：

请记住，这些算法永远不能保证找到全局最优解，但是，它们会在手边给出 [一组] 次优解。