我有一些二维多边形,每个多边形都是顺时针坐标列表。多边形是 simple (即它们可能是凹形的,但它们本身不相交)并且彼此不重叠。
我需要将这些多边形分割为更小的多边形以适应大小限制。就像原始的多边形一样,较小的多边形应该是简单的(非自相交的)并且约束是它们每个都应该适合一个“单位正方形”(为了简单起见,我可以假设为 1x1)。
问题是,我需要尽可能高效地执行此操作,其中“高效”意味着生成的(小)多边形数量最少。计算时间并不重要。
是否有一些智能算法?起初我想递归地分割每个多边形(将其分成两半,水平或垂直方向较大)这是有效的,但我似乎没有得到非常理想的结果。有什么想法吗?
最佳答案
画一个圆,圆心为初始多边形的初始点之一,半径为所需长度约束。
圆将在两点处至少与两条线相交。现在你有了第一个尽可能大的三角形。然后选择这些路口作为下一个目标。直到外面没有初始点为止。你的三角形尽可能大(尽可能少)
- 不要将已创建的三角形边视为交点。
- 生成的多边形并不总是三角形,它们也可以是四边形。也许还有更大的点数!
- 它们都几乎等于所需的大小。
微调内部零件需要一些计算。
关于将 2d 多边形最佳分割(即镶嵌/分区)到更小的多边形的算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12350581/