Obliczanie przecięć między segmentami linii

Question

Istnieje wiele pytań na temat przecięć między segmentami linii tutaj w stackowerflow i tutaj jest jeszcze jeden! Przepraszamy, ale potrzebuję pomocy, aby zrozumieć, jak obliczyć skrzyżowania. Przeczytałem kilka pytań tutaj i przyjrzałem się kilku przykładom na innych stronach internetowych, ale nadal jestem zdezorientowany i nie rozumiem tego! Nie lubię kopiować i wklejać kodu bez działania.

Do tej pory wiem, że zamierzam porównać punkty każdego segmentu linii, jak Ax, Ay, Bx, By, Cx, Cy, Dx, Dy. Czy ktoś mógłby mi wyjaśnić, co mam zamiar obliczyć, jaki byłby wynik obliczeń, gdyby istniało skrzyżowanie?

To jeden z kodu przykładowego, który widziałem. Chyba nie potrzebuję punktu przecięcia, żeby wiedzieć, czy linie przecinają się, czy nie.

public static Point lineIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { 
    double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1); 
    if (denom == 0.0) { // Lines are parallel. 
    return null; 
    } 
    double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3))/denom; 
    double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3))/denom; 
    if (ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) { 
     // Get the intersection point. 
     return new Point((int) (x1 + ua*(x2 - x1)), (int) (y1 + ua*(y2 - y1))); 
    } 

    return null; 
    } 

Czy muszę również obliczyć jakąś medianę, jak w tym przykładzie kodu?

For lines through points (x0,y0) and (x1,y1), let xm = (x0+x1)/2, ym = (y0+y1)/2 (median of line segment). 
Then a = (y1-y0) and b = (x0-x1). 
If you evaluate c = a(x-xm)+b(y-ym), c=0 for (x,y) on the line, and the sign(c) tells you which side a point is on 

Answer 1

Pierwszy kawałek kodu, który show jest na podstawie wektora przekroju produktu, który został wyjaśniony tutaj How do you detect where two line segments intersect? w najdrobniejszych szczegółach.

IMO, łatwiejsze zrozumienie tego polega na rozwiązaniu układu równań. Najpierw spójrz na linie ogólnie, a następnie wyciąć z nich segmenty. Poniżej używam notacji dla danych segmentów ((x1, x2), (y1, y2)) i ((x3, x4), (y3, y4)).

1. Sprawdź, czy któryś z przewodów jest pionowa (x1 == x2 lub x3 == x4).

   a. Jeśli oba są pionowe i x1 != x3, to bez skrzyżowania.

   b. Jeśli oba są pionowe i x1 == x3, sprawdź, czy nakładają się (y1, y2) i (y3, y4).

   c. Jeśli tylko jedna jest pionowa (powiedzmy pierwsza), a następnie zbuduj równanie drugiej linii (jak opisano poniżej), znajdź punkt, w którym przecinają się dwie linie (zastępując równanie drugiej linii przez x1) i sprawdź, czy ten punkt znajduje się w obu segmentach (podobnie jak w kroku 5).

   d. Jeśli nie, kontynuuj.

2. Użyj współrzędnych punktów, aby zbudować równania linii w formularzu y = a*x + b (jak here).

   a1 = (y2-y1)/(x2-x1) 
   b1 = y1 - a1*x1 
   a2 = (y4-y3)/(x4-x3) 
   b2 = y3 - a2*x3 
   

3. Sprawdź, czy linie są równolegle (to samo nachylenie a). Jeśli tak, sprawdź, czy mają ten sam punkt przecięcia b. Jeśli tak, sprawdź, czy segmenty 1D (x1, x2) i (x3, x4) zachodzą na siebie. Jeśli tak, segmenty się pokrywają. Przypadek, w którym linie są równoległe, może być niejednoznaczny. Jeśli nakładają się, możesz uznać to za skrzyżowanie (może to być nawet jeden punkt, jeśli ich końce się dotykają) lub nie. Uwaga: jeśli pracujesz z pływakami, byłoby to nieco trudniejsze, sądzę, że zignorowałbyś to. W przypadku, gdy masz tylko liczby całkowite sprawdzenie czy a1 = a2 odpowiada:

   if((y2-y1)*(x4-x3) == (x2-x1)*(y4-y3)) 
   

4. Jeśli linie nie są równoległe. Punkt przecięcia jest równoważny rozwiązaniu układu równań reprezentujących dwie linie.Naprawdę, przecięcie y = a1*x + b1 i y = a2*x + b2 zasadniczo oznacza, że ​​oba te równania się utrzymują. Rozwiąż ten system przez zrównanie dwóch prawych stron i da ci punkt przecięcia. W rzeczywistości, trzeba tylko x współrzędna punktu przecięcia (wyciągnąć go, a zobaczysz dlaczego):

   x0 = -(b1-b2)/(a1-a2) 
   

5. Ostatnim krokiem jest sprawdzenie, czy w punkcie przecięcia x0 kłamstwa wewnątrz obu segmentach. To znaczy min(x1, x2) < x0 < max(x1, x2) i min(x3, x4) < x0 < max(x3, x4). Jeśli tak, twoje linie przecinają się!

Answer 2

public void fixData() 
{ 
    slope = (p2.getY() - p1.getY())/(p2.getX() - p1.getX()); 
    yInt = p1.getY() - slope * p1.getX(); 
    xInt = (-yInt)/slope; 
} 

Answer 3

Naprawdę @ odpowiedź sashkello i odkrywa, że ​​jest bardziej intuicyjne i łatwiejsze do wyjaśnienia niż realizacja wektorowych. Szczególnie przy dodawaniu tego rodzaju kodu do bazy kodu.

Zastanowię się, mówiąc, że można skorzystać z metody pomocniczej Java2 Line2D.

Line2D.linesIntersect(double x1, double y1, 
         double x2, double y2, 
         double x3, double y3, 
         double x4, double y4) 

Jedyną wadą jest to, że wymaga rozważenia segmenty do przecinających się nawet wtedy, gdy są one po prostu dotykając (na obu punktach końcowych i samej linii).

Na przykład poniższe wiersze są uważane za przecinające się, ponieważ mają one współrzędne punktu (1,1).

L1 = [(0,0),(1,1)] 
L2 = [(1,1),(2,3)] 

Jeśli to jest problem, możesz dodać 4 kontrole, aby sprawdzić, czy punkty są równe.

Jeśli masz obawy co do punktu, który spada na punkt w linii, wymaga to nieco więcej pracy i być może lepiej go wdrożysz sam, abyś mógł przeprowadzić sprawdzanie w samym algorytmie.

Jeśli żadna z tych poważnych spraw nie dotyczy Ciebie, to Line2D.linesIntersect jest dla Ciebie. :)