列出平面上最外层的圆
Making a list of outermost circles on a plane
我有一个充满圆圈的大矩形。这些圆圈可能相互重叠，但它们的直径都相同。我需要找到“边界”圈子。如果这些边界圆之间存在间隙 - 并且间隙大于圆直径 - 内部的那个也应该包括在内。
这里有些例子：
我需要做的是让这些外圆不能移动，这样当内圆移动时——它们永远不会离开矩形。如何制作，是否有任何已知的算法？我是用 TypeScript 做的，但我想，任何命令式语言解决方案都可以应用
这可能太保守了，但肯定不会放出任何磁盘。
在圆心上计算 Delaunay triangulation。高质量的库是最好的，因为退化的情况和浮点测试很难正确处理。
在平面对偶上使用深度优先搜索，找到所有可以从无限面到达的面只穿过边长于（或等于？取决于它们是闭合的还是开放的）圆盘）直径的两倍。
所有入射到这些面上的点都对应于外圆盘。
我不太确定我是否找到了您问题的答案，但我使用 Tinfour Delaunay 三角剖分库（用 Java 编写）将两个简单示例放在一起。我不得不手动将你的点数字化，所以在所有情况下我都没有完全击中中心。
第一张图显示Delaunay Triangulation的边界是一个凸多边形。这很容易构建，只需将顶点（圆心）添加到 Tintfour 的 IncrementalTin class，然后向它询问边界多边形。几乎任何 Delaunay 图书馆都会支持这一点。所以你不一定需要 Tinfour。
问题是这可能包括对您的内部圈子无效的区域。我尝试了一些将凹面引入边界多边形的方法。正如你在下面看到的，右下角的顶点必须被完全切掉（如果我明白你在找什么的话）。然后我遍历周边边缘并引入凹面，其中与每个外边缘相对的顶点是一个“保护”顶点。
我为此编写的代码非常混乱。但如果这正是您要查找的内容，我会尝试将其清理干净并 post 放在这里。
我有一个充满圆圈的大矩形。这些圆圈可能相互重叠，但它们的直径都相同。我需要找到“边界”圈子。如果这些边界圆之间存在间隙 - 并且间隙大于圆直径 - 内部的那个也应该包括在内。
这里有些例子：
我需要做的是让这些外圆不能移动，这样当内圆移动时——它们永远不会离开矩形。如何制作，是否有任何已知的算法？我是用 TypeScript 做的，但我想，任何命令式语言解决方案都可以应用
这可能太保守了，但肯定不会放出任何磁盘。
在圆心上计算 Delaunay triangulation。高质量的库是最好的，因为退化的情况和浮点测试很难正确处理。
在平面对偶上使用深度优先搜索，找到所有可以从无限面到达的面只穿过边长于（或等于？取决于它们是闭合的还是开放的）圆盘）直径的两倍。
所有入射到这些面上的点都对应于外圆盘。
我不太确定我是否找到了您问题的答案，但我使用 Tinfour Delaunay 三角剖分库（用 Java 编写）将两个简单示例放在一起。我不得不手动将你的点数字化，所以在所有情况下我都没有完全击中中心。
第一张图显示Delaunay Triangulation的边界是一个凸多边形。这很容易构建，只需将顶点（圆心）添加到 Tintfour 的 IncrementalTin class，然后向它询问边界多边形。几乎任何 Delaunay 图书馆都会支持这一点。所以你不一定需要 Tinfour。
问题是这可能包括对您的内部圈子无效的区域。我尝试了一些将凹面引入边界多边形的方法。正如你在下面看到的，右下角的顶点必须被完全切掉（如果我明白你在找什么的话）。然后我遍历周边边缘并引入凹面，其中与每个外边缘相对的顶点是一个“保护”顶点。
我为此编写的代码非常混乱。但如果这正是您要查找的内容，我会尝试将其清理干净并 post 放在这里。