根据密度函数将平面划分为相等质量的区域 [英] Dividing the plane into regions of equal mass based on a density function

问题描述

给定平面中的密度"标量场，如何将平面划分为良好的(低惯性矩)区域，以便每个区域包含相似数量的质量"?

这不是对我实际问题的最好描述，但这是我能想到的最简洁的措辞.

That's not the best description of what my actual problem is, but it's the most concise phrasing I could think of.

我有一张虚构的世界大地图，可以在游戏中使用.我对一个人一天可以从这张地图上任何给定点走多远有了一个很好的主意，并且这会因地形等因素而有很大差异.我想通过将地图分为多个区域来表示此信息，以便步行一天可以将您从任何地区带到其任何邻近地区.它不一定是完美的，但它比将地图简单地划分为六边形网格(许多游戏所做的事情)要好得多.

I have a large map of a fictional world for use in a game. I have a pretty good idea of approximately how far one could walk in a day from any given point on this map, and this varies greatly based on the terrain etc. I would like to represent this information by dividing the map into regions, so that one day of walking could take you from any region to any of its neighboring regions. It doesn't have to be perfect, but it should be significantly better than simply dividing the map into a hexagonal grid (which is what many games do).

我的想法是，我可以创建一个与地图具有相同尺寸的灰度图像，其中每个像素的颜色值表示一个像素可以在地图上相同位置穿过像素的速度.维护良好的道路将被编码为白色像素，无法逾越的悬崖将被编码为黑色或类似的颜色.

I had the idea that I could create a gray-scale image with the same dimensions as the map, where each pixel's color value represents how quickly one can travel through the pixel in the same place on the map. Well-maintained roads would be encoded as white pixels, and insurmountable cliffs would be encoded as black, or something like that.

我的问题是:没有人知道如何使用这样的灰度图像(密度"标量场)从上一段(相似质量"的区域)生成我的网格"吗?

My question is this: does anyone have an idea of how to use such a gray-scale image (the "density" scalar field) to generate my "grid" from the previous paragraph (regions of similar "mass")?

我考虑过使用灰度图像作为离散概率分布，从中可以生成一堆坐标，然后使用某种聚类算法创建区域，但是a)聚类算法会我认为，必须创建相似大小的集群才能使该想法起作用，但我认为它们通常不会这样做，并且b)我几乎不知道是否有任何想法是可行的.我在这里的舒适区.

I've thought about using the gray-scale image as a discrete probability distribution, from which I can generate a bunch of coordinates, and then use some sort of clustering algorithm to create the regions, but a) the clustering algorithms would have to create clusters of a similar size, I think, for that idea to work, which I don't think they usually do, and b) I barely have any idea if any of that even makes sense, as I'm way out of my comfort zone here.

很抱歉，如果这不属于这里，我的想法一直是以某种方式以编程方式解决它，所以这似乎是最明智的问题.

Sorry if this doesn't belong here, my idea has always been to solve it programatically somehow, so this seemed the most sensible place to ask.

更新: 只是以为我会分享到目前为止获得的结果，请尝试@samgak建议的第二种方法-将区域递归地细分为相似的质量，找到每个区域的质心，并从中创建一个voronoi图.

UPDATE: Just thought I'd share the results I've gotten so far, trying out the second approach suggested by @samgak - recursively subdividing regions into boxes of similar mass, finding the center of mass of each region, and creating a voronoi diagram from those.

我会继续进行调整，也许会尝试找到一种使其不像网格一样的方式(例如右上角)，但是这种方法比我预期的要好！

I'll keep tweaking, and maybe try to find a way to make it less grid-like (like in the upper right corner), but this worked way better than I expected!

推荐答案

一些粗略的想法:

您也许可以重新利用颜色量化算法，该算法可以对颜色空间进行分区到其中像素数大致相同的区域.您将必须进行某种有趣的映射，其中地图中的像素越暗，与您在临时图像中创建的像素位置相对应的颜色的像素数就越大.然后，您可以将该图像量化为x种颜色，并将其颜色值用作地图中区域中心的坐标，然后可以创建

You might be able to repurpose a color-quantization algorithm, which partitions color-space into regions with roughly the same number of pixels in them. You would have to do some kind of funny mapping where the darker the pixel in your map, the greater the number of pixels of a color corresponding to that pixel's location you create in a temporary image. Then you quantize that image into x number of colors and use their color values as co-ordinates for the centers of the regions in your map, and you could then create a voronoi diagram from these points to define your region boundaries.

另一种方法(类似于某些颜色量化算法在幕后的工作方式)可以通过获取每个矩形区域并选择最佳分割线(x 或 y)递归地将地图区域细分为轴对齐的框)和位置，以创建2个类似质量"的较小矩形.您最终将获得2个矩形区域计数的幂，并且可以通过获取每个矩形的质心(而不仅仅是边界框的中心)并从所有中心创建一个voronoi图来摆脱阻塞性.点.不能保证创建质量完全相等的区域，但是它们应该大致相等.通过允许沿任意方向的行(或有限数量的8、16、32等可能的方向)进行递归拆分，可以改进该算法，但当然会使它更加复杂.

Another approach (which is similar to how some color quantization algorithms work under the hood anyway) could be to recursively subdivide regions of your map into axis-aligned boxes by taking each rectangular region and choosing the optimal splitting line (x or y) and position to create 2 smaller rectangles of similar "mass". You would end up with a power of 2 count of rectangular regions, and you could get rid of the blockiness by taking the centre of mass of each rectangle (not simply the center of the bounding box) and creating a voronoi diagram from all the centre-points. This isn't guaranteed to create regions of exactly equal mass, but they should be roughly equal. The algorithm could be improved by allowing recursive splitting along lines of arbitrary orientation (or maybe a finite number of 8, 16, 32 etc possible orientations) but of course that makes it more complicated.

这篇关于根据密度函数将平面划分为相等质量的区域的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！