这是一个创建于 545 天前的主题，其中的信息可能已经有所发展或是发生改变。
给定数据
- 一个点集，每个点形式为(x, y, area)，
x和y是点的坐标，area值后面再说； - 一个多边形，由一系列首尾相连的点组成。
上述点集所有的点都在这个多边形内，且上面点集中所有的点
area之和小于这个多边形的面积。
要求
- 根据点集的点生成小多边形，小多边形的面积为点的
area值; - 小多边形必须在多边形的范围内；
- 小多边形不能相互重叠。
请问这种问题有没有什么图形分割的相关算法推荐？
 |
1
misdake 2023-05-26 15:25:31 +08:00 via Android  1
帮你补一条要求就是每个点必须在自己对应的小多边形内部。
需求有点城市生成的感觉。还没什么思路。 |
 |
3
soar0712 2023-05-26 17:42:00 +08:00 1
具体的算法没有研究过，不过简单想了一下，有两个思路你可以试试是否可行，纯讨论，不一定有效：
1 、如果对小多边形的边数没有数量要求，或者不要求边数越少越好，可以将整个平面用 x 和 y 轴分割成很多小网格，然后用尝试生成法，从每个点开始扩散，不断蚕食周围的小网格，直到蚕食的区域达到 area 值； 2 、如果要求小多边形的边数越少越好，那就先计算一下每个点距离大多边形的边的距离，从离边最近的点开始尝试生成小多边形，一开始以三角形尝试，三角形的一条边顶到大多边形的边后就开始扩展另外两条边，直到凑够 area 范围，如果三条边都挨着其他点还凑不够 area ，就继续尝试四边形；按照离大多边形边界的距离，由近及远的尝试生成，最后生成最中心的小多边形。 |
Select Language