ネスティングツール(図形積み込み、bin packing)の svgnest.com では NFP ( No Fit Polygon ) を算出する際、ミンコフスキー和 or 差を使用しています。

当初、ミンコフスキー和 or 差の独自実装も考えましたが、 pyclipper の元である angus johnson's clipper を除くと、余りに手間を必要としますので、単に pyclipper を利用するだけにしました。

参考url

# -*- coding: utf-8 -*-

import pyclipper
import io
import matplotlib.pyplot as plt
import numpy             as np
import re
import sys
from matplotlib.path        import Path
from matplotlib.patches     import PathPatch
from matplotlib.collections import PatchCollection
from shapely.geometry   import Polygon


def main():
    # parts a
    shell_a_s = [
        [[ 0,0],[50,0],[50,50],[ 0,50]],
        [[ 0,0],[50,0],[50,30],[30,50],[0,50]],
        [[20,0],[50,0],[50,50],[ 0,50],[0,20]],
        [[ 0,0],[50,0],[50,10],[10,10],[10,40],[50,40],[50,50],[0,50]]
    ]
    # parts b
    shell_b=[[0,0],[15,0],[0,15]]

    for shell_a in shell_a_s:
        
        poly_a = Polygon( shell=shell_a,      holes=[])
        poly_b = Polygon( shell=shell_b,      holes=[])
        
        # https://github.com/fonttools/pyclipper/blob/main/tests/test_pyclipper.py
        # ミンコフスキー和
        # minkowskis = pyclipper.MinkowskiSum(shell_a, shell_b, False)
        # print( poly_mnkwskis )
        # poly_mnkwski = Polygon( shell=minkowski[0], holes=[])
        # plot_polygons(poly_mnkwski, poly_a, poly_b)
        
        # ミンコフスキー差
        minkowskis = pyclipper.MinkowskiDiff(shell_b, shell_a)
        print( minkowskis )
        poly_mnkwski = Polygon( shell=minkowskis[0], holes=[])
        plot_polygons(poly_mnkwski, poly_a, poly_b)

        
def plot_polygons(poly_mnkwski, poly_a, poly_b):
    fig, ax = plt.subplots()
    for [polygon,face,edge] in [[poly_mnkwski,'None',       'red'],
                                [poly_a,      'lightgray','black'],
                                [poly_b,      'lightblue','blue' ]
                                ]:

        plot_polygon(ax, polygon,
                     facecolor=face,
                     edgecolor=edge,
                     alpha=0.2)
    plt.show()


# Plots a Polygon to pyplot `ax`
# cf. https://stackoverflow.com/questions/55522395
def plot_polygon(ax, poly, **kwargs):
    path = Path.make_compound_path(
        Path(np.asarray(poly.exterior.coords)[:, :2]),
        *[Path(np.asarray(ring.coords)[:, :2]) for ring in poly.interiors])

    patch = PathPatch(path, **kwargs)
    collection = PatchCollection([patch], **kwargs)
    
    ax.add_collection(collection, autolim=True)
    ax.autoscale_view()
    return collection


if __name__ == '__main__':
    main()