问一个多边形的相关问题

[liplushe]

给定数据

1. 一个点集，每个点形式为(x, y, area)，x和y是点的坐标，area值后面再说；
2. 一个多边形，由一系列首尾相连的点组成。 上述点集所有的点都在这个多边形内，且上面点集中所有的点area之和小于这个多边形的面积。

要求

1. 根据点集的点生成小多边形，小多边形的面积为点的area值;
2. 小多边形必须在多边形的范围内；
3. 小多边形不能相互重叠。

请问这种问题有没有什么图形分割的相关算法推荐？

[misdake]

帮你补一条要求就是每个点必须在自己对应的小多边形内部。

需求有点城市生成的感觉。还没什么思路。

[liplushe]

@misdake 感谢补充，确实有这个要求

[soar0712]

具体的算法没有研究过，不过简单想了一下，有两个思路你可以试试是否可行，纯讨论，不一定有效：
1 、如果对小多边形的边数没有数量要求，或者不要求边数越少越好，可以将整个平面用 x 和 y 轴分割成很多小网格，然后用尝试生成法，从每个点开始扩散，不断蚕食周围的小网格，直到蚕食的区域达到 area 值；
2 、如果要求小多边形的边数越少越好，那就先计算一下每个点距离大多边形的边的距离，从离边最近的点开始尝试生成小多边形，一开始以三角形尝试，三角形的一条边顶到大多边形的边后就开始扩展另外两条边，直到凑够 area 范围，如果三条边都挨着其他点还凑不够 area ，就继续尝试四边形；按照离大多边形边界的距离，由近及远的尝试生成，最后生成最中心的小多边形。

[liplushe]

@soar0712 非常感谢，第一个思路很有用