凹点法求解矩形可行域问题研究

摘要：

提出一种采用凹点法求解矩形可行域问题的算法.首先根据坐标判断多边形各顶点的凹凸性;然后采用对顶点中的凹点进行搜索的方法,逐步去除多边形中矩形无法放置的区域,获得所有的有效顶点;最后通过简单计算,即可得到矩形在多边形布局空间中的可行域.分析和实例表明,该算法简洁、高效,有着较广泛的理论和应用前景.

关键词：凹点法、可行域、顶点形态、角点序列

所属期刊栏目：17

分类号：TP391.72(计算技术、计算机技术)

资助基金：天津市教委资助项目20060802

在线出版日期：2008-05-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：40-44,67