폴리곤 레이 캐스팅 알고리즘의 포인트

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-1 l1-13 l4-15 또는 l1-12 l3-14 l15-16을 true로 지정합니다.

Answer 1

다음 알고리즘을 적용하여 수정할 수 있습니다.
1. 선이 내부의 모서리와 교차하는 경우 (끝점 중 하나가 아닌 경우) 항상 교차점을 유지하십시오.
2. 선이 끝점의 가장자리와 교차하는 경우 선의 왼쪽 끝 (작은 x 좌표가있는 경우)에 한해 선을 유지합니다.
3. 가장자리가 수직이면 무시하십시오.

그 후에는 중복을 제거하지 않고 포인트를 정렬하십시오.