在多边形内查找轴对齐的矩形 [英] Finding an axis-aligned rectangle inside a polygon

问题描述

我正在寻找一种好的算法来在(不一定是凸面的)多边形内找到一个轴对齐的矩形.一个最大的矩形会很好，但不是必需的 - 任何可以找到相当好的"矩形的算法都可以.

I am looking for a good algorithm to find an axis-aligned rectangle inside a (not necessarily convex) polygon. A maximal rectangle would be nice, but is not necessary - any algorithm that can find a "fairly good" rectangle would be fine.

多边形也可能有孔，但任何指向仅适用于凸多边形或简单多边形的算法的指针也会有所帮助.

The polygon may also have holes, but any pointers to algorithms that only work for convex or simple polygons would be helpful too.

在我的实现中，边的相交测试相当便宜，但多边形中的点"测试很昂贵，因此最好尽量减少.

In my implementation, intersection testing for sides is fairly cheap, but "point in polygon" tests are expensive, so ideally should be minimised.

推荐答案

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
有一个凸算法，参考资料可能值得一看.
不确定它是否可以扩展到非凸的.

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
Has an algorithm for convex, the references might be worth a look.
not sure if it could be extended to non-convex though.

这篇关于在多边形内查找轴对齐的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！