Lui*_*igo 12 algorithm optimization geometry
我正在做一个小房子设计项目,其中一个最重要的部分是用户可以提供一些关于他如何想要他的房间的信息(例如,一个10 x 10米的房子,有一个3x3的起居室,一个3x3厨房,两个4 x 5卧室和一个4x2浴室),然后该程序根据所做的requeriments生成房子的地图.
现在,我并不担心绘制地图,只是以不重叠的方式安排房间(是的,输出可能非常难看).我已经做了一些搜索,发现我想要的东西与打包问题非常相似,它有一些算法可以很好地处理这个问题(尽管这是一个NP完全问题).
但后来又有了一个限制:用户可以指定房间之间的"链接",例如,他可能希望房间必须有一个"门"到浴室,客厅可以直接到厨房等(也就是说,房间必须并排放置,这就是事情变得复杂的地方.
我很确定我想要的是配置NP问题,所以我要求提供一些好的,但不一定是最佳实现的技巧.我的想法是使用图表来表示房间之间的关系,但我无法找到如何调整现有的打包算法以适应这个新的限制.谁能帮我？
我没有完整的答案给你，但我确实有一个提示：你的连接约束将形成所谓的平面图（如果没有，单层房屋的解决方案是不可能的）。最终解决方案中的房间将对应于约束图的对偶中的边缘包围的区域，因此您需要做的就是采用所述对偶，并调整其边缘的形状，而不引入交叉点，以适应尺寸约束。请注意，您需要引入一个顶点来表示约束图中的“外部”，并确保它不被对偶包围。您可能还需要在约束图中引入额外的边，以确保所有房间都连接（并为走廊添加房间等）。