Еще один комментарий об объединениях вместо пересечений. Основная идея заключается в том, что операция объединения будет выполняться в противоположном направлении по сравнению с операцией пересечения. То есть, если кто-то должен двигаться назад по многоугольнику для операции пересечения, то для операции объединения он будет двигаться вперед и наоборот.

Теперь об алгоритме: во-первых, давайте начнем с схемы алгоритма. Приведенный здесь алгоритм будет создавать только один полигон за операцию пересечения, поэтому вам придется адаптировать его для создания более одного полигона.

'''
  The following is an adaptation of the above Greiner-Hormann* algorithm to deal
  with degenerate cases. The adaptation was briefly described by Liu et al.**  
  *Greiner, G. and Hormann K., Efficient Clipping of Arbitrary Polygons, ACM
  Trans. on Graphics, 17(2), 1998, pp.71-83
  **Liu, Y. K., Wang X. Q., Bao S. Z., Gombosi M., and Zalik B, An Algorithm for
  Polygon Clipping and for Determining Polygon Intersections and Unions, Comp. &
  Geo, 33, pp. 589-598, 2007
'''
def clip(subject, constraint):
    subject, constraint = inside_outside(subject, constraint) #label vertices as inside or outside
    subject, constraint = poly_inters(subject, constraint) #find intersections
    subject, constraint = label(subject, constraint) #label intersections and entry or exit and possibly remove

    flag = True #loop flag

    #set our current location to the first point in subject
    current = subject.first
    #loop through our polygon until we have found the first intersection
    while flag:
        current = current.next
        #Either an intersection has been found or no intersections found
        if current.intersect or current.pt == subject.first.pt:
            flag = False

    #reset our flag for the new loop
    flag = True
    #If a point lies outside of c and there was an intersection clip s
    if current.intersect:
        append(clipped, current.pt) 
        While flag:
            #Entry
            if current.en:
                clipped, current = forward(clipped, current)
            #Exit
            else:
                clipped, current = backward(clipped, current)

            #Check to see if we have completed a polygon
            if current.pt == clipped.first.pt:
                #check if the polygon intersect at a point
                if clipped.num_vertices is not 1:
                    #remove the last vertex because it is also the first 
                    remove(clipped, clipped.last)
                #we have created our polygon so we can exit
                flag = .FALSE.

            #change to the neighbor polygon since we are at a new intersection
            current = current.neighbor

    #Check if one polygon is contained wholly within the other
    elif contained(subject, constraint):
        clipped = subject
    elif contained(subject, constraint):
        clipped = constraint

    return clipped

Теперь можно обсудить маркировку. Следующий код представляет собой цикл для маркировки пересечений как внутренних или внешних. Он не включает в себя логику определения внутри/снаружи и представляет собой только порядок операций.

  #label intersections as entry or exit
  def label(poly1, poly2):
      #cycle through first polygon and label intersections as en or ex
      current = poly1.first
      for i in range(0,poly1.num_vertices):
          if current.intersect:
              current = intersect_cases(current)
              #Make sure current is still an intersection
              if current.isect:
                  current.neighbor = intersect_cases(current.neighbor)
                  #if the intersection is en/en or ex/ex
                  if current.en == current.neighbor.en:
                      current = remove_inter(current)

          current = current.next #move to the next point

      return poly1, poly2

И, наконец, работа с различными случаями маркировки.

  #deal with the cases
  #on/on, on/out, on/in, out/on, out/out, out/in, in/on, in/out, in/in
  def intersect_cases(current):
      neighbor = current.neighbor
      #on/on
      if current.prev.intersect and current.next.intersect:
          #Determine what to do based on the neighbor
          #en tag is the opposite of the neighbor's en tag 
          if neighbor.prev.intersect and neighbor.next.intersect:
              current = remove_inter(current)
              current.en = True
              neighbor.en = True
          elif neighbor.prev.intersect and not neighbor.next.en:
              current.en = False
          elif neighbor.prev.intersect and neighbor.next.en:
              current.en = True
          elif not neighbor.prev.en and neighbor.next.intersect:
              current.en = False
          elif not (neighbor.prev.en or neighbor.next.en):
              current = remove_inter(current)
              current.en = True
              neighbor.en = False
          elif not neighbor.prev.en and neighbor.next.en:
              current.en = False
          elif neighbor.prev.en and neighbor.next.isect:
              current.en = True
          elif neighbor.prev.en and not neighbor.next.en:
              current.en = True
          elif neighbor.prev.en and neighbor.next.en:
              current = remove_inter(current)
              current.en = False
              neighbor.en = True
      #on/out
      elif current.prev.intersect and not current.next.en:
          current.en = False
      #on/in  
      elif current.prev.intersect and current.next.en:
          current.en = True
      #out/on  
      elif not current.prev.en and current.next.intersect:
          current.en = True
      #out/out  
      elif not (current.prev%en or current.next.en):
          if neighbor.prev%intersect and neighbor.next.intersect:
              current = remove_inter(current)
              neighbor.en = True
          elif neighbor.prev.en == neighbor.next.en:
              current = remove_inter(current)
          else:
              if neighbor.prev.en and not neighbor.next.en:
                  current.en = True
              else:
                  current.en = False
      #out/in  
      elif not current.prev.en and current.next.en:
          current.en = True
      #in/on
      elif current.prev.en and current.next.intersect:
          current.en = False
      #in/out
      elif current.prev.en and not current.next.en:
          current.en = False
      #in/in
      elif current.prev.en and current.next.en:
          if neighbor.prev.intersect and neighbor.next.intersect:
              current = remove_inter(current)
              neighbor.en = False
          elif neighbor.prev.en == neighbor.next.en:
              current = remove_inter(current)
          else:
              if neighbor.prev.en and not neighbor.next.en:
                  current.en = True
              else:
                  current.en = False

      return current

Приведенный выше код не тестировался и написан не для эффективности, а для удобочитаемости и понимания.