**https://colab.research.google.com/drive/1MlMeEl7QEqPLVpnbQlzL_nFvLxRyg0Ql?usp=sharing**

Excute-Time
https://docs.google.com/spreadsheets/d/14f0dNELpFJ339camvHKpcwlFzEfhQgvLoCnvpzDz01k/edit?usp=sharing

def calc_dist(P1,P2):
  return abs(P1.x-P2.x)+abs(P1.y-P2.y)
def customsort(A,B):
  return (A[0]>B[0])

def make_polygon(P1,P2):
  offset1 = 0
  offset2 = 0
  if P1.y > P2.y:
    offset1 += 1
  else:
    offset1 -= 1
  if P1.x < P2.x:
    offset2 = -1
  else:
    offset2 = 1
  polygon = Polygon([(P1.x,P1.y),(P1.x,P1.y+offset1),(P2.x,P1.y+offset1),(P2.x,P2.y-offset1),(P2.x+offset2,P2.y-offset1),(P2.x+offset2,P1.y),(P1.x,P1.y)])
  return polygon

def special_case(P,polygons):
  B = P.buffer(1,cap_style=3, join_style=1)
  u = unary_union([])
  polygons2 = [u,polygons,B]
  u = unary_union(polygons2)
  return u
def connect(polygons):
  restore = list()
  for i in range(len(polygons)):
    for j in range(i+1,len(polygons)):
      data = nearest_points(polygons[i],polygons[j])
      dist = calc_dist(data[0],data[1])
      if dist == 0:
        if len(polygons) == 2:
          polygons = special_case(data[0],polygons)
          polygons = MultiPolygon([polygons])
        else:
          continue
      else:
        restore.append([dist,data])
  restore = sorted(restore,key=lambda restore: restore[0])
  a = make_polygon(restore[0][1][0],restore[0][1][1]) if len(restore) >= 1 else Polygon()

  u = unary_union([])
  polygons2 = [u,polygons,a]
  u = unary_union(polygons2)
  return u
def polygon_boundary(polygon):
    x = []
    y = []
    boundary = list(polygon.exterior.coords)
    for p in boundary:
        x.append(p[0])
        y.append(p[1])
    return x, y

def evaluate_score(recs, polys, numPolys):
  if(len(polys) != numPolys):
    print('Wrong polygon number')
    return -1
  area = 0
  for pol in polys:
    area += pol.area
    x, y = polygon_boundary(pol)
  for i in range(0, len(x)-1):
    x_1, y_1 = x[i], y[i]
    x_2, y_2 = x[i+1], y[i+1]
    if x_1 != x_2 and y_1 != y_2:
      print('The polygon', pol, 'is not rectilinear ornot in clockwise order')
      return -1
  for rec in recs:
    covered = False
    for pol in polys:
      if(pol.covers(rec)):
        covered = True
        break;
    if(covered):
      continue
    print('The rectangle', rec, 'is not contained by any polygons')
    return -1
  return area

input = open(inputFile, "r")
temp = input.readline()
numPoly = int(temp)
temp = input.readline()
numRec = int(temp)
inputRecs = []

while input:
  temp = input.readline()
  coords = temp.split(' ')
  if len(coords) < 2:
    break
  curr = []
  point = []
  for i in range(len(coords)):
    if coords[i] == '\n':
      continue
    if i%2 == 0:
      point.clear()
      point.append(float(coords[i]))
    else:
      point.append(float(coords[i]))
      curr.append(point[:])
  currPoly = Polygon(curr)
  inputRecs.append(currPoly)
print('Rectangles:')
u = unary_union([])
print(len(inputRecs))
for rec in inputRecs:
  #print(rec)
  polygons = [rec, u]
  u = unary_union(polygons)
while len(u) > numPoly:
  leng = len(u)
  u = connect(u)
  if leng == 2:
    u = MultiPolygon([u])
    break
print(u)
print(len(u))
print('Result:')
score = evaluate_score(inputRecs, u, numPoly)
print('Score =', score)

#parameters (outputFileName,MutiPolygon)
def writeFile(outputFile,u):
    # output the file
    f = open(outputFile, "w")
    for i in range(len(u)):
        x, y = polygon_boundary(u[i])
        for j in range(0, len(x) - 1):
            f.write(str(int(x[j]))+' ')
            f.write(str(int(y[j])))
            if j != (len(x) - 2):
                f.write(' ')
        f.write('\n')
    f.close()

writeFile(resultFile,u)


def display_result(inputFile, outputFile):
    input = open(inputFile, "r")
    temp = input.readline()
    numPoly = int(temp)
    temp = input.readline()
    numRec = int(temp)
    inputRecs = []
    while input:
        temp = input.readline()
        coords = temp.split(' ')
        if len(coords) < 2:
            break
        curr = []
        point = []
        for i in range(len(coords)):
            if coords[i] == '\n':
                continue
            if i%2 == 0:
                point.clear()
                point.append(float(coords[i]))
            else:
                point.append(float(coords[i]))
                curr.append(point[:])
        currPoly = Polygon(curr)
        inputRecs.append(currPoly)
    with open(outputFile) as res:
        result = res.readlines()
    evalPolygons = []
    for line in result:
        coords = line.split(' ')
        curr = []
        point = []
        for i in range(len(coords)):
            if coords[i] == '\n':
                continue
            if i%2 == 0:
                point.clear()
                point.append(float(coords[i]))
            else:
                point.append(float(coords[i]))
                curr.append(point[:])
        if Polygon(curr).is_valid:
          currPoly = Polygon(curr)
          evalPolygons.append(currPoly)
    plt.figure(figsize=(8, 8))
    plt.axis('equal')
    for rec in inputRecs:
        x, y = polygon_boundary(rec)
        plt.plot(x, y, 'C2')
    for pol in evalPolygons:
        x, y = polygon_boundary(pol)
        plt.plot(x, y, 'C1')
    plt.show()
display_result(inputFile,resultFile)


MultiPolygon
[link](https://shapely.readthedocs.io/en/stable/manual.html#collections-of-polygons)

def readfile(inputfile):
  f = open(inputfile)
  lines = f.readlines()
  k = lines[0]
  n = lines[1]
  allPoly = []
  for l in lines[2:]:
    l = l[-1].split('')
    rec = []
    while len(l)>0:
      rec.append((int(l[0]),int(l[1]))
      l = l[2:]

    p1 = Polygon(rec)
    allPoly.append(p1)
  
  for i in range(len(allPoly)-1):
    for j in range(i+1,len(allPoly)):
      if allPoly[i].intersects(allPoly[j]):
        print("intersected!")
        polygons = [allPoly[i], allPoly[j]]
        u = unary_union(polygons)
        allPoly.append(u)
        del allPoly[i] #有問題
        del allPoly[j-1] #有問題
        
'''    newset = []
    while len(allPoly)>1:
        p0 = allPoly[0]
        catched = [p0]
        for j in range(1,len(allPoly)):
            if p0.intersects(allPoly[j]):
                print("intersected!",j)
                catched.append(allPoly[j])
                p0 = unary_union([p0,allPoly[j]])
                
        newset.append(p0)
        print(p0)
        for pi in catched:
            allPoly.remove(pi)
            print(len(allPoly),len(newset))
    newset += allPoly
    print(len(newset))'''

#display
#display
import sys
from shapely.geometry import Polygon
from shapely.ops import unary_union
import matplotlib.pyplot as plt
import matplotlib.patches as patches

def display_result(inputFile, outputFile):
    input = open(inputFile, "r")
    temp = input.readline()
    numPoly = int(temp)
    temp = input.readline()
    numRec = int(temp)
    inputRecs = []
    while input:
        temp = input.readline()
        coords = temp.split(' ')
        if len(coords) < 2:
            break
        curr = []
        point = []
        for i in range(len(coords)):
            if coords[i] == '\n':
                continue
            if i%2 == 0:
                point.clear()
                point.append(float(coords[i]))
            else:
                point.append(float(coords[i]))
                curr.append(point[:])
        currPoly = Polygon(curr)
        inputRecs.append(currPoly)
    with open(outputFile) as res:
        result = res.readlines()
    evalPolygons = []
    for line in result:
        coords = line.split(' ')
        curr = []
        point = []
        for i in range(len(coords)):
            if coords[i] == '\n':
                continue
            if i%2 == 0:
                point.clear()
                point.append(float(coords[i]))
            else:
                point.append(float(coords[i]))
                curr.append(point[:])
        if Polygon(curr).is_valid:
          currPoly = Polygon(curr)
          evalPolygons.append(currPoly)
    plt.figure(figsize=(8, 8))
    plt.axis('equal')
    for rec in inputRecs:
        x, y = polygon_boundary(rec)
        plt.plot(x, y, 'C2')
    for pol in evalPolygons:
        x, y = polygon_boundary(pol)
        plt.plot(x, y, 'C1')
    plt.show()

Find nearest points

from shapely.ops import nearest_points
from shapely.ops import shared_paths
from shapely.ops import snap
from shapely.geometry.polygon import LinearRing



print(nearest_points(u[0],u[2])[0].wkt,nearest_points(u[0],u[2])[1].wkt)

# x, y = polygon_boundary(u[0])

plt.show()

Write File
參數 (檔案名稱,MultiPolygon)

#parameters (outputFileName,MultiPolygon)
def writeFile(outputFile,u):
    # output the file
    f = open(outputFile, "w")
    for i in range(len(u)):
        x, y = polygon_boundary(u[i])
        for j in range(0, len(x) - 1):
            f.write(str(int(x[j]))+' ')
            f.write(str(int(y[j])))
            if j != (len(x) - 2):
                f.write(' ')
        f.write('\n')
    f.close()