我正在创建一个简单的游戏,在设计游戏AI时遇到了这个问题:给定笛卡尔坐标系中矩形内的N个点集,我需要找到通过该矩形的最宽直线路径。路径必须为空(即不包含任何点)。
我想知道是否有任何有效的算法来解决这个问题?您能否提供与此问题相关的关键词/论文/任何信息?
编辑:矩形总是由其四个角落的4个点定义。我添加了一张图片以进行说明。上述图片中的路径由两条红线确定。
我想知道是否有任何有效的算法来解决这个问题?您能否提供与此问题相关的关键词/论文/任何信息?
编辑:矩形总是由其四个角落的4个点定义。我添加了一张图片以进行说明。上述图片中的路径由两条红线确定。