gpt4 book ai didi

划分区域的算法,使每个给定点在其绘图中居中

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:02:57 25 4
gpt4 key购买 nike

假设您有 n 个点的位置。您想要分割 Canvas ,使每个点位于其自己的分区内,大致位于中心。

我听说算法是这样的:“同时绘制从每个点发出的圆圈。当它们接触到另一个点的圆圈时,接触/交叉点被绘制到 Canvas 上并且圆圈继续增长.最终,这些新绘制的点变成了边界线。”

given green dots and blue generated lines

这个算法叫什么?我很想找到它的动画。是否有另一种算法可以产生相同的除法?

此外,您将如何编写代码? Java、python 或 C# 更可取,但伪代码或任何其他语言都可以。

最佳答案

根据您绘制的点集将平面划分为多个区域称为 Voronoi 图。有两种流行的生成它们的算法

  1. Fortune's algorithm

    一种扫掠线算法,当扫掠线穿过数据集时构建区域,并且是 O(n log n) 时间和 O(n) 空间

  2. Lloyd's Algorithm

    一种类似于 k-means 的迭代算法,但适用于连续的几何区域。

如果您已经对点进行了 Delaunay 三角剖分,那么您可以使用 Bowyer–Watson 计算 Vonoroi 图(因为它们是对偶的)算法

关于划分区域的算法,使每个给定点在其绘图中居中,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31497378/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com