Egy másik algoritmus meghatározására a kereszteződésekben a két szegmens
Egy másik algoritmus meghatározására a kereszteződésekben a két szegmens 6
- 29.09.15 00:31 •
- SemenovVV •
- • # 267461
- • Habrahabr
- 19 •
- 12414
- mint a Forbes, csak jobb.
Ez volt a közelmúltban megjelent „Egy egyszerű algoritmus határozza meg a kereszteződésekben a két szegmensben.” Úgy döntött, hogy megpróbálja megoldani a problémát a kereszteződés két szegmens egy kicsit más, geometriailag.
Megtalálása a metszéspontja a két szegmens.
4 van pontok koordinátáinak a tömbben P (0..3) szerkezete pont (x float, y float):
1. lépés - átvitele a származási.
2. lépés - Kapcsolja ki a származási
Forgatni a koordinátarendszert úgy, hogy a szegmens vett egy függőleges helyzetben (megállapítják az Y tengely). Kiszámítjuk a hossza a szegmens:
L1 = SQRT ((P (1) .x) ^ 2 + (P (1) .y) ^ 2)
Szinusz és koszinusz a szög alfa forgástengelyei:
Cnova újraszámolja a pontok koordinátáinak P1, P2, P3:
3. lépés - talál a metszéspontja szegmensek.
P23X = P (2) .x + (P (3) .x - P (2) .x) * béta
P23Y = P (2) .y + (P (3) .y - P (2) .y) * béta
ahol 0 <= beta <= 1
P (2) .x + (P (3) .x - P (2) .x) * béta = 0
További lehetséges kiviteli alak szerinti 2 értéket P (3) .x - P (2) .x: Ha P (2) .x = P (3) .x, ez azt jelenti, hogy a szegmens nem függőleges és párhuzamos a szegmens. A kereszteződésekben a szegmensek csak akkor lehetséges, ha a második szegmens is fekszik az Y-tengelyen, és az egyik végén van az első szegmens (vagy érinti) vagy szegmens fedelek. Feltesszük, hogy az eredmény akkor kell csak egy pontot. Ez lesz az egyik P0..P3 pontokat.
Ha a metszéspont talált egy kiviteli alakja szerinti CR 1 3. lépésnél, majd újraszámolja a koordinátáit az eredeti koordinátarendszer. A következő változók tárolják a 1. és 2. lépést. Forgatás szögben -alfa:
Ha a metszéspontja a CR által talált állapota 2. lépésben 3 koordináta konverzió nem szükséges. Példa kód golang cut alatt. Golang th csak pancsolás, így a kód kérését, hogy engedékeny. A kód is futtatható golang.org:
Most szó szerint térd becsült eljárás meglétének ellenőrzése a kereszteződés.
Ha az egyenes egyenlete, helyettesítheti azt a pontot, az eredmény a jel fogja mutatni, hogy mi van a félig sík, ezen a ponton képest ezen a vonalon.
A szegmensek, amelyek nem fekszenek egy egyenesen áthaladó szükségességét a végén mindegyik a különböző felezési síkoknak egy egyenes vonal, beleértve a többi szegmens.
Számítási komplexitás nem kíváncsi, de azt gondolom, hogy megfelelő optimalizálása az derül ki, jól.
Igen, ez egy jó út. De azt is figyelembe kell venni az esetben, ha a végén pont a szegmens fog feküdni a sorban a többi.
Ha formalizált, megkapjuk:
1. Mivel két szegmens (x11, Y11) - (X12, Y12) és (X21, Y21) - (x22, Y22)
2. Ezeken szegmensek közvetlen A1 * x + b1 * y + c1 = 0 és a2 * x + b2 * y + C2 = 0
3. Ezután a szegmenseket metszik, ha (a1 * X21 + b1 * Y21 + c1) * (a1 * x22 + b1 * Y22 + c1) <= 0 и
(A2 * x11 + B2 * Y11 + c2) * (a2 * x12 + B2 * Y12 + c2) <= 0
Minden egyszerű és logikus