找到不与任何给定多边形相交的最大矩形

Question

我得到了一张图像，其中定义了多个（不一定是凸的）多边形，以及一个兴趣点。

我需要找到包含感兴趣点但不与任何多边形相交的最大矩形（平行于图像的轴 - 未旋转）。

如果该矩形没有唯一定义，我将采取任何合理的解决方案。一般来说，矩形太大比太小要好，有时太大也可以简化代码。

我可以使用什么算法来做到这一点？我正在使用 Python 工作，并且想使用

shapely

。

---

到目前为止我的粗略算法是：

xmin = 0
xmax = 1000 # Plane is 1000x1000 pixels
ymin = 0
ymax = 1000
while True:
  for each poly in polygons:
      intersection = poly.intersects(rect(xmin, xmax, ymin, ymax)
      if intersection:
           raise xmin or ymin, or lower xmax or ymax, to not include this point of intersection while still including the point of interest
  if we loop through all polygons and have no intersection, we are done    
           

Answer 1

要找到包含给定兴趣点但不与图像中任何多边形相交的最大矩形，您可以使用二分搜索方法以及 Python 中的 shapely 提供的几何操作。

# Define the point of interest
point_of_interest = Point(x, y)  # Replace x, y with the coordinates of your point of interest

# Define the bounding box of the image
xmin, ymin, xmax, ymax = 0, 0, 1000, 1000  # Adjust these values according to your image dimensions

def is_valid_rectangle(rectangle, polygons):
    """
    Check if the given rectangle does not intersect any of the polygons.
    """
    for poly in polygons:
        if rectangle.intersects(poly):
            return False
    return True

def find_largest_rectangle(point_of_interest, polygons, xmin, ymin, xmax, ymax):
    """
    Find the largest rectangle containing the point of interest
    and not intersecting any of the polygons.
    """
    while True:
        # Check if the current rectangle is valid
        rectangle = Polygon([(xmin, ymin), (xmin, ymax), (xmax, ymax), (xmax, ymin)])
        if is_valid_rectangle(rectangle, polygons):
            return rectangle

        # Binary search to adjust the boundaries of the rectangle
        mid_x = (xmin + xmax) // 2
        mid_y = (ymin + ymax) // 2

        # Determine in which direction to adjust the boundaries
        if point_of_interest.x < mid_x:
            xmax = mid_x
        else:
            xmin = mid_x
        if point_of_interest.y < mid_y:
            ymax = mid_y
        else:
            ymin = mid_y

使用示例

polygons = [...]  # List of shapely Polygon objects representing the polygons in the image
largest_rectangle = find_largest_rectangle(point_of_interest, polygons, xmin, ymin, xmax, ymax)

该算法的工作原理是使用二分搜索方法重复细分图像的边界框，并检查生成的矩形是否与任何多边形相交。 搜索将继续，直到找到包含感兴趣点且不与任何多边形相交的有效矩形。 然后将生成的矩形作为满足条件的最大矩形返回。

确保将

[...]

替换为代表图像中多边形的实际 Polygon 对象列表。 此外，调整

xmin

、

ymin

、

xmax

和

ymax

值以匹配图像的尺寸。