在其他多边形之间找到最大的空矩形的算法 [英] Algorithm to find the largest empty rectangle amid other polygons

问题描述

场景:内部有一个矩形空间，其中任意放置了任意方向的多边形.目的是找到最大的可容纳在矩形空间的空白区域内的空白矩形.下图显示了这种情况，其中蓝色的多边形和虚线表示每种情况下可以安装的最大空白矩形.

The scenario : There is a rectangular space inside which there are arbitrarily placed polygons of arbitrary orientations. The aim is to find the largest empty rectangle that can be fitted inside the empty regions of the rectangular space. These images below illustrate the scenario with the polygons in blue and the dotted line representing the maximum empty rectangle that can be fitted in each scenario.

问题:显然，找到最大的空矩形是众所周知的问题，但是我在该领域发现的算法涉及在点(CGAL已实现)和线段之间找到空矩形.有没有办法针对我的情况调整这些现有技术?还是有一种更简单的方法来做到这一点?

The problem : Apparently, finding largest empty rectangles is a well known problem in computational geometry, but the algorithms I found in this area dealt with finding empty rectangles amid points (CGAL has implemented this) and line segments. Is there a way to adapt these existing techniques for my scenario? Or is there a simpler way to do this?

推荐答案

不幸的是，我所熟悉的大多数计算几何学文献似乎都在没有实际提供实现的情况下生成了算法的精美描述以及算法正确性的证明.也许这是因为通常都涉及到实现.

Unfortunately, most of the computational geometry literature with which I am familiar seems to generate beautiful descriptions of algorithms and proofs of their correctness without actually providing implementations. Perhaps this is because the implementations are generally rather involved.

您没有提及您可以容忍的误差程度.如果您有一定的容忍度，那么此答案适合您.

You don't mention what degree of inaccuracy you can tolerate. If you have some tolerance, this answer's for you.

我的建议是，您将这个难题转化为更简单的问题.

1. 找到多边形集合的边界框.
2. 将边界框划分为网格.网格越细，精度越高，但是找到解决方案所需的时间也就越长.
3. 找到每个网格有多少面积单元(以矩形多边形形式显示)与多边形集相交.
4. 如果重叠足够(大于您指定的某个最小值)，则将网格单元标记为零；否则，将网格单元标记为零.否则，用一个标记.
5. 您现在有了一个由零和一组成的矩形数组.这就构成了更简单问题的基础:该网格中最大的矩形子集是什么，它完全由一个子集组成?

1. Find the bounding box of your polygon collection.
2. Divide the bounding box into a grid. The finer the grid the better your accuracy, but the longer it will take to find a solution.
3. Find how much area of each grid cell (cast as a rectangular polygon) intersects with the polygon set.
4. If the overlap is sufficient (greater than some minimum value you specify), mark the grid cell with a zero; otherwise, mark it with a one.
5. You now have a rectangular array of zeros and ones. This forms the basis of the easier problem: what is the largest rectangular subset of this grid which is composed entirely of ones?

这个更简单的问题在整个Internet上都有许多可访问的解决方案(例如 1 ， 2 ， 3 ，

This easier problem has a number of accessible solutions all over the internet (e.g. 1, 2, 3, 4, 5, 6).

这篇关于在其他多边形之间找到最大的空矩形的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！