在一个区域中拟合二维多边形的算法? [英] Algorithm for fitting 2D polygons in an area?
问题描述
这有标准吗?算法名称?
Is there a standard for this? Algorithm name?
说:我有 10 个不同大小的多边形.我有一个特定大小的区域.
Say: I have 10 polygons of different sizes. I have an area of specific size.
我想知道如何填充该区域中最多的多边形,以及它们是如何拟合的.
I want to know how to fill the most polygons in that area, and how they are fitted.
注意:多边形可能会根据限制集进行旋转.
Note: Polygons may be rotated depending on the restriction set.
推荐答案
一个可能的名称是 包装问题.它与背包问题有关.这些问题往往是 NP-hard 问题,而且许多问题需要启发式方法.如果您可以限制多边形和区域的允许形式,则可能存在针对您的特殊情况的更有效的算法.
One possible name is a Packing Problem. It is related to the Knapsack Problem. These problems tend to be NP-hard, and many require heuristics. If you can constrain the allowed forms of polygons and of the area, there may exist a more efficient algorithm for your special case.
这篇关于在一个区域中拟合二维多边形的算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!