最小面积四边形算法 [英] Minimum area quadrilateral algorithm

问题描述

有几个算法可以找到包含给定（凸）多边形的最小边界矩形。

有没有人知道寻找最小区域的算法边界四边形（任何四边形，而不仅仅是矩形）？

我现在搜索了几个小时的网络，但是当我发现一些关于这个问题的理论文章时，我没有找到一个单一的执行... ...编辑：Mathoverflow的人指出我与一个数学解决方案的文章（我的文章），但是我没有找到实际的实现。我决定采用卡尔的蒙特卡洛方法，但是当我有时间的时候，我会潜入报纸并报告......

谢谢大家！

p>

解决方案

蒙特卡洛方法

感谢您对问题的澄清评论。我已经拿走了所需要的不是一个数学上正确的结果，而是一个适合，比其他形状的任何可比较的适合都好。

与其浇注了很多在这个问题上算法智力，我会让计算机担心它。生成4个随机点的组;检查凸连接这4个点形成的四边形不与多边形相交，并计算四边形的面积。重复100万次，检索面积最小的四边形。

您可以应用一些约束条件使点不完全随机;这可以显着改善融合。

---

蒙特卡洛，改进

我一直坚信，即使在暴力解决方案中，在飞机上随机扔4分也是非常低效的开始。因此，下面的细化：

• 对于每个试验，随机选择 p 不同的顶点和 q 多边形的不同侧面，使得 p + q = 4。


• 对于每个 q 边，构建一条穿过该边的端点的直线。


• 对于每个 p 顶点，构造一条穿过该顶点并随机
  
• 验证4条线确实构成一个四边形，并且该四边形包含（并且不相交！）多边形。如果这些测试失败了，不要再追求这个迭代。
  
• 如果这个四边形的面积是迄今为止所看到的所有面积的最小值，记住面积和四边形顶点的坐标。





重复任意次数，并返回找到的最佳四边形。与总是需要8个随机数（4点中的每一个的x和y坐标）相反，该解决方案仅需要（4 + p ）随机数。此外，生成的线条并不是在平面上一味地挣扎，而是分别接触多边形。这确保四边形从一开始就至少非常接近多边形。




There are a few algorithms around for finding the minimal bounding rectangle containing a given (convex) polygon.

Does anybody know about an algorithm for finding the minimal-area bounding quadrilateral (any quadrilateral, not just rectangles)?

I've searched the internet for several hours now, but while I found a few theoretical papers on the matter, I did not find a single implementation...

EDIT: People at Mathoverflow pointed me to an article with a mathematical solution (my post there), but for which I did not find an actual implementation. I decided to go with the Monte Carlo Method from Carl, but will dive into the paper and report here, when I have the time...

Thanks all!

解决方案

The Monte Carlo approach

Thanks for the clarifying comments on the problem. I've taken away that what's required is not a mathematically correct result but a "fit" that's better than any comparable fits for other shapes.

Rather than pouring a lot of algorithmic brain power at the problem, I'd let the computer worry about it. Generate groups of 4 random points; check that the quad formed by convexly joining those 4 points does not intersect the polygon, and compute the quad's area. Repeat 1 million times, retrieve the quad with the smallest area.

You can apply some constraints to make your points not completely random; this can dramatically improve convergence.

---

Monte Carlo, improved

I've been convinced that throwing 4 points randomly on the plane is a highly inefficient start even for a brute-force solution. Thus, the following refinement:

• For each trial, randomly select p distinct vertices and q distinct sides of the polygon such that p + q = 4.
• For each of the q sides, construct a line passing through that side's endpoints.
• For each of the p vertices, construct a line passing through that vertex and with a randomly assigned slope.
• Verify that the 4 lines indeed form a quadrilateral, and that this quadrilateral contains (and does not intersect!) the polygon. If these tests fail, don't pursue this iteration any further.
• If this quadrilateral's area is the minimum of all areas seen so far, remember the area and the coordinates of the quadrilateral's vertices.
• Repeat an arbitrary number of times, and return the "best" quadrilateral found.

As opposed to always requiring 8 random numbers (x and y coordinates for each of 4 points), this solution requires only (4 + p) random numbers. Also, the lines produced are not blindly floundering in the plane but are each touching the polygon. This ensures that the quadrilaterals are from the outset at least very close to the polygon.

这篇关于最小面积四边形算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！