如何制作voronoi图的网格变体？

Question

我有一个让我想起Voronoi的问题,但是我希望我的变化能让我避免使用Voronoi算法,并且更快地写一些东西.

这是我在Paint中制作的可怕图像来说明我的问题:

说我有一张地图区域.每个点代表一个商店.每个方块代表一个社区.voronoi图显示了最接近每个商店的区域.

如果其中一个区域占据了一个广场,那么整个广场都属于那个商店.

是否有可能确定哪个方块属于哪个商店,而无需计算中间voronoi图？似乎,因为这就像voronoi图的非常粗略的近似,应该有一个超快的快捷方式来生成它.

Answer 1

也许我误解了，但是你不能找到最接近每个正方形质心的顶点吗？

@user2615897 指出这通常是不正确的（请参阅评论）。尽管如此，我认为这对于看起来像您的示例的网格来说是一个很好的近似（具体来说：大致相等面积的单元格，间距与正方形大小相当）。

我的直觉是，如果没有明确构建图表，任何方法都只是一个近似值......但我不确定。

配置的这个（片段）说明了这一点：红色顶点最接近中心正方形的中心，而绿色顶点拥有最大面积。