使用Pyclipper库求解容器与多边形的NFP问题求助

我正在使用Pyclipper库生成多边形在容器内的无适配多边形（NFP），以此展示多边形在容器内的可行放置位置，但代码未得到预期结果。我的需求是求解polygon_a在container内的NFP，以下是我的代码，恳请有该库使用经验的人士帮忙排查问题。

import pyclipper
import matplotlib.pyplot as plt
from matplotlib.patches import Polygon as MplPolygon
from matplotlib.collections import PatchCollection


# 检查并补全多边形闭合
def close_poly(polygon):
    if not polygon:
        return []
    if len(polygon) < 2:
        return polygon
    if polygon[0] != polygon[-1]:
        return polygon + [polygon[0]]
    return polygon


# 调整多边形方向（顺时针/逆时针）
def orient_poly(polygon, ccw=False):
    if len(polygon) < 3:
        return polygon

    area = sum(
        (x1 * y2) - (x2 * y1)
        for (x1, y1), (x2, y2) in zip(polygon, polygon[1:] + [polygon[0]])
    )

    is_currently_ccw = area < 0
    return list(reversed(polygon)) if (ccw ^ is_currently_ccw) else polygon


# 反射多边形（原错误实现：基于质心反射）
def reflect_poly(polygon):
    # 计算质心
    centroid = (
        sum(x for x, y in polygon) / len(polygon),
        sum(y for x, y, in polygon) / len(polygon),
    )

    # 返回基于质心反射的多边形
    return [(2 * centroid[0] - x, 2 * centroid[1] - y) for x, y in polygon]


# 多边形缩放（适配Pyclipper整数运算）
def scale_poly(polygon, scale=100):
    return [(int(x * scale), int(y * scale)) for x, y in polygon]


# 计算容器与多边形的NFP（原错误实现）
def nfp_container_poly(cont, poly):
    SCALE = 1000

    cont = close_poly(cont)
    poly = close_poly(poly)

    cont = orient_poly(cont, ccw=True)
    poly = orient_poly(poly, ccw=False)

    r_poly = reflect_poly(poly)

    c_scaled = scale_poly(cont, SCALE)
    r_scaled = scale_poly(r_poly, SCALE)

    pc = pyclipper.Pyclipper()
    pc.AddPath(c_scaled, pyclipper.PT_SUBJECT, closed=True)
    pc.AddPath(r_scaled, pyclipper.PT_CLIP, closed=True)

    # 原错误：使用了交集运算而非差集
    solution = pc.Execute(
        pyclipper.CT_INTERSECTION,
        pyclipper.PFT_NONZERO,
        pyclipper.PFT_NONZERO,
    )
    if not solution:
        return None

    nfp_scaled = solution[0]
    nfp = scale_poly(nfp_scaled, 1 / SCALE)

    return nfp


def vizualize_poly(cont, poly, nfp):
    fig, ax = plt.subplots(figsize=(10, 8))
    ax.set_aspect("equal")
    ax.grid(True)

    cont = close_poly(cont)
    poly = close_poly(poly)

    patches = []
    # 原错误：容器透明度设为0.0，无法看到容器边界
    patches.append(MplPolygon(cont, closed=True, color="blue", alpha=0.0))
    patches.append(MplPolygon(poly, closed=True, color="green", alpha=0.5))

    if nfp:
        nfp = close_poly(nfp)
        patches.append(MplPolygon(nfp, closed=True, color="red", alpha=0.5))

    for patch in patches:
        ax.add_patch(patch)

    legend_elements = [
        plt.Rectangle((0, 0), 1, 1, fc="blue", alpha=0.5, label="容器"),
        plt.Rectangle((0, 0), 1, 1, fc="green", alpha=0.5, label="多边形"),
    ]

    if nfp:
        legend_elements.append(
            plt.Rectangle((0, 0), 1, 1, fc="red", alpha=0.5, label="NFP")
        )

    ax.legend(handles=legend_elements, loc="upper right")

    all_points = cont + poly
    if nfp:
        all_points += nfp

    x_coords, y_coords = zip(*all_points)
    ax.set_xlim(min(x_coords) - 1, max(x_coords) + 1)
    ax.set_ylim(min(y_coords) - 1, max(y_coords) + 1)

    plt.title("无适配多边形可视化")
    plt.show()


container = [(0, 0), (600, 0), (600, 600), (0, 600)]
polygon_a = [(0, 0), (200, 0), (200, 200), (0, 200)]

nfp = nfp_container_poly(container, polygon_a)
print(nfp)
vizualize_poly(container, polygon_a, nfp)

核心错误与修正方案 #

1. Minkowski运算类型错误
   计算容器内NFP需要使用Minkowski差，对应Pyclipper的CT_DIFFERENCE，而非代码中使用的CT_INTERSECTION。

2. 多边形反射逻辑错误
   NFP计算要求多边形关于原点反射，而非自身质心。修正后的反射函数应为：

   def reflect_poly(polygon):
       return [(-x, -y) for x, y in polygon]
   

3. 可视化容器不可见
   原代码中容器的alpha=0.0导致无法看到容器边界，建议改为alpha=0.2以便观察。

修正后的完整代码 #

import pyclipper
import matplotlib.pyplot as plt
from matplotlib.patches import Polygon as MplPolygon
from matplotlib.collections import PatchCollection


# 检查并补全多边形闭合
def close_poly(polygon):
    if not polygon:
        return []
    if len(polygon) < 2:
        return polygon
    if polygon[0] != polygon[-1]:
        return polygon + [polygon[0]]
    return polygon


# 调整多边形方向（顺时针/逆时针）
def orient_poly(polygon, ccw=False):
    if len(polygon) < 3:
        return polygon

    area = sum(
        (x1 * y2) - (x2 * y1)
        for (x1, y1), (x2, y2) in zip(polygon, polygon[1:] + [polygon[0]])
    )

    is_currently_ccw = area < 0
    return list(reversed(polygon)) if (ccw ^ is_currently_ccw) else polygon


# 修正：多边形关于原点反射（NFP计算标准方式）
def reflect_poly(polygon):
    return [(-x, -y) for x, y in polygon]


# 多边形缩放（适配Pyclipper整数运算）
def scale_poly(polygon, scale=100):
    return [(int(x * scale), int(y * scale)) for x, y in polygon]


# 修正：正确计算容器与多边形的NFP
def nfp_container_poly(cont, poly):
    SCALE = 1000

    cont = close_poly(cont)
    poly = close_poly(poly)

    cont = orient_poly(cont, ccw=True)
    poly = orient_poly(poly, ccw=False)

    r_poly = reflect_poly(poly)

    c_scaled = scale_poly(cont, SCALE)
    r_scaled = scale_poly(r_poly, SCALE)

    pc = pyclipper.Pyclipper()
    pc.AddPath(c_scaled, pyclipper.PT_SUBJECT, closed=True)
    pc.AddPath(r_scaled, pyclipper.PT_CLIP, closed=True)

    # 使用Minkowski差运算
    solution = pc.Execute(
        pyclipper.CT_DIFFERENCE,
        pyclipper.PFT_NONZERO,
        pyclipper.PFT_NONZERO,
    )
    if not solution:
        return None

    nfp_scaled = solution[0]
    nfp = scale_poly(nfp_scaled, 1 / SCALE)

    return nfp


def vizualize_poly(cont, poly, nfp):
    fig, ax = plt.subplots(figsize=(10, 8))
    ax.set_aspect("equal")
    ax.grid(True)

    cont = close_poly(cont)
    poly = close_poly(poly)

    patches = []
    # 修正：设置容器可见的透明度
    patches.append(MplPolygon(cont, closed=True, color="blue", alpha=0.2))
    patches.append(MplPolygon(poly, closed=True, color="green", alpha=0.5))

    if nfp:
        nfp = close_poly(nfp)
        patches.append(MplPolygon(nfp, closed=True, color="red", alpha=0.5))

    for patch in patches:
        ax.add_patch(patch)

    legend_elements = [
        plt.Rectangle((0, 0), 1, 1, fc="blue", alpha=0.5, label="容器"),
        plt.Rectangle((0, 0), 1, 1, fc="green", alpha=0.5, label="多边形"),
    ]

    if nfp:
        legend_elements.append(
            plt.Rectangle((0, 0), 1, 1, fc="red", alpha=0.5, label="NFP")
        )

    ax.legend(handles=legend_elements, loc="upper right")

    all_points = cont + poly
    if nfp:
        all_points += nfp

    x_coords, y_coords = zip(*all_points)
    ax.set_xlim(min(x_coords) - 1, max(x_coords) + 1)
    ax.set_ylim(min(y_coords) - 1, max(y_coords) + 1)

    plt.title("无适配多边形可视化")
    plt.show()


container = [(0, 0), (600, 0), (600, 600), (0, 600)]
polygon_a = [(0, 0), (200, 0), (200, 200), (0, 200)]

nfp = nfp_container_poly(container, polygon_a)
print(nfp)
vizualize_poly(container, polygon_a, nfp)

效果说明 #

修正后，红色的NFP区域代表多边形原点可以放置的位置——当多边形的原点落在NFP内部时，整个多边形会完全处于容器（蓝色区域）内，符合你对可行放置位置的需求。

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