找到一个轴对齐矩形多边形内 [英] 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.

推荐答案

<一个href="http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/">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屋！