从用圆圈填充的二维空间创建图
提问于 2018-05-07 02:52:48
我在用任意位置和半径的圆填充二维空间。
我还想要创建一个图，其中每个圆都是一个顶点，并有与其他相交圆的边。
我的问题是：是否有一种有效的方法来创建这类图？
很明显，有一种蛮力的方法，就是检查每个圆。我还想，我可以在二维平面上覆盖一个网格，并对圆圈进行散列，这样我就可以很容易地在特定的区域找到圆圈了。
下面是我工作的一个例子：
回答 1
Stack Overflow用户
发布于 2018-05-07 06:08:08
示例图像表明，在圆圈半径上可能有一个上界R，它比矩形的总边长小得多。如果是这样的话，您可能需要尝试以下方法：
Sort all circles by x coordinate of center
Maintain a list L of circles, sorted by y coordinate of center, initially empty
For each circle C1 in order of x coordinates:
Drop all elements C2 from L where x2 < x1 - 2*R (or x2 < x1 - r2 - R)
For each circle C2 in L where |y1 - y2| < r1 + R:
Check C1, C2 for intersection, possibly add to result
Add C1 to L, maintaining order by y coordinatesL可以是一棵红黑树，或者类似于执行范围查询(即y1 - r1 - R < y2 < y1 + r1 + R)很简单的东西。但是，要在元素超出范围时有效地删除它们，您可能需要第二种结构，很可能是堆栈(具有松散的- 2*R限制)或优先级队列(具有更严格的- r2 - R限制)。
如果R接近你的圆圈的典型大小，这应该是很好的工作。否则，四叉树可能会更好，只有当你遇到一个大圆圈时，你才会访问相邻的细胞，而不是仅仅因为还会有一个更大的圆圈而浪费工作。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50212496
复制相关文章
点击加载更多
腾讯云开发者
