Un alt algoritm pentru determinarea intersecției a două segmente +6
- 09/29/15 12:31 •
- SemenovVV •
- # 267461 •
- Habrahabr •
- 19 •
- 12414
- la fel ca Forbes, doar mai bine.
Recent, a existat o publicație "Un algoritm simplu pentru determinarea intersecției a două segmente". Am decis să încerc să rezolv problema problemei trecerii a două segmente într-un mod diferit, mai geometric.
Găsiți punctul de intersecție al două segmente.
Avem coordonatele a 4 puncte în matricea P (0..3) a structurii punctului (x float, y float):
Pasul 1 - Transferați originea coordonatelor.
Pasul 2 - Rotiți originea
Rotim sistemul de coordonate astfel incat segmentul sa aiba o pozitie verticala (se afla pe axa Y). Să calculam lungimea unui segment ca:
L1 = SQRT ((P (1) .x) ^ 2 + (P (1) .y) ^ 2)
Sinus și cosinus al unghiului de rotație al axelor de coordonate:
Din nou, recalculează coordonatele punctelor P1, P2, P3:
Pasul 3 - găsiți punctul de intersecție al segmentelor.
P23X = P (2) .x + (P (3) .x-P (2) .x) * beta
P23Y = P (2) .y + (P (3) .y-P (2) Y) * beta
unde 0 <= beta <= 1
P (2) .x + (P (3) .x-P (2) .x) * beta = 0
Apoi există 2 opțiuni posibile în funcție de valoarea P (3) .x-P (2) .x: Dacă P (2) .x = P (3) .x, atunci aceasta înseamnă că segmentul este vertical și paralel cu segmentul. Intersecția segmentelor este posibilă numai dacă cel de-al doilea segment se află, de asemenea, pe axa Y, iar unul dintre capetele sale se află în primul segment (sau atinge) sau pe segmentele de acoperire. Vom presupune că pentru rezultat avem nevoie doar de un singur punct. Acesta va fi unul dintre punctele P0..P3.
Dacă punctul de intersecție CR este găsit de varianta 1 din pasul 3, atunci coordonatele sale sunt recalculate pentru sistemul de coordonate inițial. Utilizăm variabilele stocate în etapele 1 și 2. Porniți unghiul -alfa:
Dacă punctul de intersecție CR este găsit de condiția 2 din pasul 3, nu este necesară recalcularea coordonatelor. Cod exemplu pentru golang sub tăiere. Golang oh mi-am răsfățat, deci la codul pe care-l cer să fiu indulgent. Puteți rula codul pe golang.org:
Acum, am îngenuncheat literalmente metoda de verificare a intersecției.
Dacă în ecuația unei linii drepte, înlocuiți un punct, atunci semnul rezultat ne va arăta în ce jumătate de plan este acest punct situat în raport cu această linie.
Pentru ca segmentele care nu se află pe o singură linie să se intersecteze, este necesar ca capetele fiecăruia să se afle în diferite semi-planuri în raport cu o linie dreaptă care include un alt segment.
Complicitatea computerelor nu a estimat, dar, cred că, cu o optimizare adecvată ar trebui să fie bună.
Da, acesta este un mod bun. Dar trebuie să ținem seama și de cazul în care punctul de la sfârșitul unui segment se află pe linia celuilalt.
Dacă se formalizează, vom primi:
1. Sunt date două segmente (x11, y11) - (x12, y12) și (x21, y21) - (x22, y22)
2. Desenați prin aceste segmente liniile a1 * x + b1 * y + c1 = 0 și a2 * x + b2 * y + c2 = 0
3. Atunci segmentele intersectează dacă (a1 * x21 + b1 * y21 + c1) * (a1 * x22 + b1 * y22 + c1) <= 0 и
(a2 * x11 + b2 * y11 + c2) * (a2 * x12 + b2 * y12 + c2) <= 0
Totul este simplu și logic