如何高效生成满足点包含与排除规则的Shapely多边形？

需要生成N个多边形，满足以下条件：

• 不得包含指定的最多50个外点中的任何一个；
• 必须包含指定的最多50个内点中的全部。

当前采用随机生成多边形后校验条件的策略，要生成100个多边形，但生成10个就耗时约1分钟，效率极低。同时该过程依赖于采样多边形位置的高斯分布均值与sigma参数。

使用环境：Shapely 1.8.5.post1、Python3

#!/usr/bin/python3
import random
from datetime import datetime
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches
from shapely.geometry import box, Point
from descartes import PolygonPatch
from shapely import affinity

def create_center_origin_rectangle(object_center, deg, object_length=0.06):
    # 从中心计算左下角坐标
    object_x_corner = object_center[0] - (object_length)/2.0
    object_y_corner = object_center[1] - (object_length)/2.0

    # 创建矩形patch（仅用于计算坐标）
    rectangle = patches.Rectangle((object_x_corner, object_y_corner), object_length, object_length,linewidth=1, edgecolor='none', facecolor='none', alpha=0.5)

    # 获取左下角和右上角坐标
    bottom_left = rectangle.get_xy()
    upper_right = (rectangle.get_x()+rectangle.get_width(), rectangle.get_y()+rectangle.get_height())

    # 创建Shapely矩形并旋转
    polygon_box = box(bottom_left[0], bottom_left[1], upper_right[0], upper_right[1])
    polygon = affinity.rotate(polygon_box, deg)
    patch = PolygonPatch(polygon, facecolor='none', edgecolor='grey', alpha=0.3, zorder=-1)
    return patch, polygon

random.seed(100)
np.random.seed(100)

fig, ax = plt.subplots()
ax.set_xlim(-0.1,0.1)
ax.set_ylim(-0.1,0.1)

# 指定外点
outside_points = np.asarray([(0.01,0.05), (0.023,0.06), (-0.03, 0.02), (-0.04, -0.02), (-0.03,-0.03), (0.012, -0.03)])
ax.plot(outside_points[:,0], outside_points[:,1], marker='*', linestyle='', color='black', label='外点')

# 指定内点
inside_points = np.asarray([(0.02, 0.04), (0.03, 0.03), (0.02,0.06)])
ax.plot(inside_points[:,0], inside_points[:,1], marker='*', linestyle='', color='red', label='内点')

num_cube = 0

print("开始时间:", datetime.now().strftime('%d_%m_%Y_%H_%M_%S'))

while num_cube < 10:
    inside_points_check = []
    outside_points_check = []

    # 随机采样中心坐标和旋转角度
    cube_center_x = np.random.normal(loc=0.0, scale=0.06)
    cube_center_y = np.random.normal(loc=0.0, scale=0.06)
    deg = np.random.randint(0,359)
    patch_1, polygon_1 = create_center_origin_rectangle(object_center=(cube_center_x, cube_center_y), deg=deg)

    # 校验条件1：不包含任何外点
    for outside_point in outside_points:
        outside_points_check.append(polygon_1.contains(Point(outside_point[0], outside_point[1])))

    # 校验条件2：包含所有内点
    for inside_point in inside_points:
        inside_points_check.append(polygon_1.contains(Point(inside_point[0], inside_point[1])))
    
    # 满足双条件则保留
    if np.all(np.asarray(outside_points_check) == False) and np.all(np.asarray(inside_points_check) == True):
        num_cube += 1
        ax.add_patch(patch_1)

print("结束时间:", datetime.now().strftime('%d_%m_%Y_%H_%M_%S'))

plt.legend()
plt.show()

1. 直接构造满足条件的多边形，而非随机生成后校验 #

随机生成后校验本质是碰运气，约束严格时命中率极低，直接基于内点、外点位置计算合法范围：

• 先计算所有内点的最小包围矩形，再将矩形扩大（扩大尺寸大于多边形半长，确保内点全被包含）；
• 同时让扩大后的矩形与所有外点保持足够距离（大于多边形半长），避免包含外点；
• 在合法的中心区域内采样坐标，再随机旋转，生成的多边形天然符合条件，无需事后校验。

示例代码片段：

# 计算内点的最小包围矩形边界
inside_min_x, inside_min_y = inside_points.min(axis=0)
inside_max_x, inside_max_y = inside_points.max(axis=0)
half_len = 0.03  # 多边形半长（object_length/2）

# 初始化合法中心区域：确保生成的矩形能包含所有内点
valid_center_min_x = inside_min_x
valid_center_max_x = inside_max_x
valid_center_min_y = inside_min_y
valid_center_max_y = inside_max_y

# 调整合法区域，排除会包含外点的中心范围
for px, py in outside_points:
    # 外点不能在矩形范围内，缩小合法中心区域
    valid_center_max_x = min(valid_center_max_x, px - half_len)
    valid_center_min_x = max(valid_center_min_x, px + half_len)
    valid_center_max_y = min(valid_center_max_y, py - half_len)
    valid_center_min_y = max(valid_center_min_y, py + half_len)

# 在合法区域内均匀采样中心坐标
cube_center_x = np.random.uniform(valid_center_min_x, valid_center_max_x)
cube_center_y = np.random.uniform(valid_center_min_y, valid_center_max_y)

2. 优化点包含的判断逻辑 #

• 提前将外点、内点转换为Shapely的Point对象，避免循环中重复创建；
• 一旦发现不符合条件的点（如内点未被包含、外点被包含），直接终止当前多边形的校验，减少不必要的计算。

优化后的校验代码：

# 提前转换所有点为Shapely Point对象
inside_shapely = [Point(p) for p in inside_points]
outside_shapely = [Point(p) for p in outside_points]

# 校验条件
valid = True
# 先检查内点：有一个未包含则无效
for p in inside_shapely:
    if not polygon_1.contains(p):
        valid = False
        break
if valid:
    # 再检查外点：有一个被包含则无效
    for p in outside_shapely:
        if polygon_1.contains(p):
            valid = False
            break
if valid:
    num_cube += 1
    ax.add_patch(patch_1)

3. 减少不必要的对象创建 #

原代码通过patches.Rectangle计算坐标完全多余，直接用中心和长度计算边界即可，节省开销：

def create_center_origin_rectangle(object_center, deg, object_length=0.06):
    half_len = object_length / 2.0
    # 直接计算矩形的四个边界
    min_x = object_center[0] - half_len
    min_y = object_center[1] - half_len
    max_x = object_center[0] + half_len
    max_y = object_center[1] + half_len
    polygon_box = box(min_x, min_y, max_x, max_y)
    polygon = affinity.rotate(polygon_box, deg)
    patch = PolygonPatch(polygon, facecolor='none', edgecolor='grey', alpha=0.3, zorder=-1)
    return patch, polygon

4. 调整采样策略，摆脱高斯分布依赖 #

高斯分布采样的区域若大部分不符合条件，会产生大量无效尝试。改用合法区域内均匀采样，既能保证生成的多边形100%符合条件，又无需依赖高斯分布参数，效率大幅提升。

内容的提问来源于stack exchange，提问作者goldfinch