Точка в алгоритме литья полигональных лучей

Question

Учитывая, что матрица размера M, N и список точек образуют многоугольник, мне нужно вернуть двоичную матрицу, где она отмечает все точки внутри многоугольника. Вот код: используя горизонтальное сканирование линии, пересекайтесь с полигоном и отметьте все точки между пересечением, чтобы они были истинными.

import cv2 
import math 
import numpy as np 

def getABC(x1, y1, x2, y2): 
    A = y2 - y1 
    B = x1 - x2 
    C = A*x1 + B*y1 
    return (A, B, C) 

def polygon(M, N, poly): 
    """ 
    Return a mask matrix 
    Where points inside the polygon is 1, outside is 0 
    """ 
    out = np.zeros((M, N)). astype(bool) 

    n = len(poly) 
    for i in range(M): 

     # horizontal scanning 
     intersection_x = i 
     intersection_y = [] 

     # check through all edges 
     for edge in range(n + 1): 
      v1_x, v1_y = poly[edge % n] 
      v2_x, v2_y = poly[(edge + 1) % n] 

     v1_x = int(v1_x) 
     v1_y = int(v1_y) 
     v2_x = int(v2_x) 
     v2_y = int(v2_y) 

      assert (v1_x <= M and v2_x <= M and v1_y <= N and v2_y <= N) 

      A1, B1, C1 = getABC(v1_x, v1_y, v2_x, v2_y) 
      A2 = 1 
      B2 = 0 
      C2 = i 

      # find intersection 
      if intersection_x >= min(v1_x, v2_x) and intersection_x <= max(v1_x, v2_x): 
       det = A1*B2 - A2*B1 
       if (det != 0): 
        tmp = (A1 * C2 - A2 * C1)/det 
        intersection_y.append(math.ceil(tmp)) 

     intersection_y = sorted(list(set(intersection_y))) 



     if len(intersection_y) > 1: 
      for k in range(1, len(intersection_y), 2): 
       out[intersection_y[k - 1]:intersection_y[k], intersection_x] = True 

    return out 

if __name__ == "__main__": 
out = polygon(512, 512,   
    [[ 
     321.929203539823, 
     414.4070796460177 
    ], 
    [ 
     164.74414597854175, 
     512.0 
    ], 
    [ 
     0.0, 
     509.9846825337252 
    ], 
    [ 
     0.0, 
     221.4867256637168 
    ], 
    [ 
     170.60176991150445, 
     2.902654867256672 
    ], 
    [ 
     320.1592920353982, 
     91.39823008849561 
    ], 
    [ 
     271.4867256637168, 
     201.1327433628319 
    ], 
    [ 
     348.4778761061947, 
     228.56637168141594 
    ], 
    [ 
     359.98230088495575, 
     302.9026548672567 
    ], 
    [ 
     220.15929203539824, 
     329.4513274336283 
    ]]) 

    cv2.imwrite("polygon.png", out * 255) 

Он выполняет неправильно в случае угла, например, выше вход будет генерировать:

Я не был в состоянии решить эту проблему. В зависимости от числа пересечений, я буду назначать l0-l1 l2-l3 l4-l5 или l1-l2 l3-l4 l5-l6, чтобы быть истинным.

Answer 1

Вы можете исправить, применив следующий алгоритм:
1. Если линия пересекает ребро внутри него (а не в одной из конечных точек), всегда держите точку пересечения.
2. Если линия пересекает ребро в конечной точке, сохраните его тогда и только тогда, когда он левый конец ребра (с меньшей координатой x).
3. Если край вертикальный, просто игнорируйте его.

После этого просто сортируйте точки без удаления дубликатов.