Python: sprawdzanie, czy punkt jest wewnątrz wielokąta

Question

Mam klasę opisującą punkt (ma 2 współrzędne x i y) i klasę opisującą wielokąt, który ma listę punktów, które odpowiadają rogom (self.corners) I trzeba sprawdzić, czy punkt jest w wielokącie

Oto funkcja, która ma sprawdzić, czy punkt w wielokącie. Używam Ray Casting Metoda

def in_me(self, point): 
     result = False 
     n = len(self.corners) 
     p1x = int(self.corners[0].x) 
     p1y = int(self.corners[0].y) 
     for i in range(n+1): 
      p2x = int(self.corners[i % n].x) 
      p2y = int(self.corners[i % n].y) 
      if point.y > min(p1y,p2y): 
       if point.x <= max(p1x,p2x): 
        if p1y != p2y: 
         xinters = (point.y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x 
         print xinters 
        if p1x == p2x or point.x <= xinters: 
         result = not result 
      p1x,p1y = p2x,p2y 
     return result 

uruchomić test z następujących kształt i punkt:

PG1 = (0,0), (0,2), (2,2), (2,0) 
point = (1,1) 

Skrypt szczęśliwie False chociaż punkt to w wierszu. Jestem w stanie znaleźć błąd

Answer 1

chciałbym zaproponować kilka innych zmian tam:

def contains(self, point): 
    if not self.corners: 
     return False 

    def lines(): 
     p0 = self.corners[-1] 
     for p1 in self.corners: 
      yield p0, p1 
      p0 = p1 

    for p1, p2 in lines(): 
     ... # perform actual checks here 

Uwagi:

• Wielokąt z 5 rogach posiada 5 linii ograniczającej, a nie 6 Twoja pętla jest jednorazowa.
• Użycie osobnego wyrażenia generatora wyjaśnia, że ​​sprawdzasz kolejno po kolei.
• Sprawdzanie pustej liczby linii zostało dodane. Jednak sposób traktowania linii o zerowej długości i wielokątów za pomocą jednego rogu jest nadal otwarty.
• Zastanowiłabym się również nad tym, aby funkcja lines() działała jako normalny element członkowski zamiast zagnieżdżonego narzędzia.
• Zamiast wielu zagnieżdżonych struktur if, możesz również sprawdzić odwrotność, a następnie continue lub użyć and.

Answer 2

Sugerowałbym użyciu klasy Path z matplotlib

import matplotlib.path as mplPath 
import numpy as np 

poly = [190, 50, 500, 310] 
bbPath = mplPath.Path(np.array([[poly[0], poly[1]], 
        [poly[1], poly[2]], 
        [poly[2], poly[3]], 
        [poly[3], poly[0]]])) 

bbPath.contains_point((200, 100)) 

(Istnieje również contains_points funkcję, jeśli chcesz przetestować dla wielu punktów)

Answer 3

Kroki:

• Powtórz po wszystkich segmentach wielokąta:
• Sprawdź, czy przecinają się one z ray idą w zwiększeniu-x kierunku

Korzystanie z funkcji intersect z This SO Question

def ccw(A,B,C): 
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x) 

# Return true if line segments AB and CD intersect 
def intersect(A,B,C,D): 
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D) 

def point_in_polygon(pt, poly, inf): 
    result = False 
    for i in range(len(poly.corners)-1): 
     if intersect((poly.corners[i].x, poly.corners[i].y), (poly.corners[i+1].x, poly.corners[i+1].y), (pt.x, pt.y), (inf, pt.y)): 
      result = not result 
    if intersect((poly.corners[-1].x, poly.corners[-1].y), (poly.corners[0].x, poly.corners[0].y), (pt.x, pt.y), (inf, pt.y)): 
     result = not result 
    return result 

Należy pamiętać, że parametr inf powinien być maksymalny punkt na osi x w Twoja figura.