Co to jest algorytm do wyznaczania całkowitej powierzchni dwóch prostokątów, które przecinają się i mogą być obracane poza osie współrzędnych?
Odpowiedzi:
18 dla odpowiedzi № 1Z grubsza to, co musisz zrobić, wyrażone tak ogólnie, jak to możliwe, ale obejmujące wszystkie możliwości:
- Wypracuj klasę skrzyżowania. To znaczy. Ile krawędzi ma obszar przecięcia? Może to być od 0 do 8.
- Znajdź wszystkie wierzchołki przecięcia. Będą to wszystkie przecięcia między krawędziami prostokątów i skojarzone rogi samych prostokątów. Praca nad tym bitem jest najbardziej skomplikowana / nużąca.
- Wyrównaj obszar przecięcia, dzieląc go na trójkąty, jeśli to konieczne.
Oto wszystkie sposoby, w jakie prostokąty mogą się przecinać:
Aktualizacja
Miałem pewne myśli i najlepszy sposóbkategoryzuj skrzyżowanie, aby prześledzić obwód każdego prostokąta i zliczać ile razy każda krawędź przecina inną krawędź. Dostaniesz wektor, np. Dla sześciostronnego obszaru przecięcia: {1,1,1,1}, {0,1,1,1} i dla 8: {2,2,2,2}, { 2,2,2,2} Dwa przypadki specjalne, które należy sprawdzić, to przypadki, gdy jeden prostokąt całkowicie zamyka drugi, a krawędzie są w jednej linii. Będziesz musiał dokładnie sprawdzać, ale to byłby punkt wyjścia dla funkcji kategoryzacji skrzyżowania.
3 dla odpowiedzi № 2
Obszar (R1 union R2) = Obszar (R1) + Obszar (R2) - Obszar (skrzyżowanie R1 R2), dzięki czemu można obliczyć obszar przecięcia, aby mieć obszar unii.
Przecięcia dwóch prostokątów (lub dwóch wypukłych wielokątów) są proste:
- Są to wypukłe wielokąty
- Ich punkty charakteryzują się następująco: punkty przecięcia dowolnej pary krawędzi i punkty jednego prostokąta znajdujące się w drugim.
Tak to wygląda tak:
- L jest początkowo pustą połączoną listą
- R1 ma krawędzie e1, e2, e3, e4, R2 ma krawędzie f1, f2, f3, f4. Oblicz punkty przecięcia ei i fj, dla wszystkich i, j = 1,2,3,4. Dodaj je do listy L.
- Dla każdego wierzchołka v R1, jeśli v znajduje się wewnątrz R2, dodaj je do L.
- Dla każdego wierzchołka w R2, jeśli w znajduje się wewnątrz R1, dodaj je do L.
Wypukły kadłub punktów w L jest twoim przecięciem. Ponieważ każdy punkt L znajduje się na granicy przecięcia, możesz go triangulować i obliczyć jego powierzchnię. Łatwy:
- L = [x0, x1, ...]
- Sortuj punkty w L zgodnie z kątem (xi - x0) w stosunku do linii poziomej przechodzącej przez x0
- Pierwszy trójkąt to x0, x1, x2
- Drugi trójkąt to x0, x2, x3
- n-ty trójkąt to x0, x (n + 1), x (n + 2)
Obszar trójkąta jest podany w formule Herona:
- a, b, c są długością krawędzi
- s = 0,5 * (a + b + c)
- area = sqrt (s * (s - a) * (s - b) * (s - c))
ale uważaj na komputery s - a, s - b i s - c niezależnie od tego, że możesz napotkać błąd zaokrągleń (co jeśli na przykład c ~ ai b << a?)
1 dla odpowiedzi nr 3
Ok, masz 3 możliwości: 1. Prostokąty nie krzyżują się 2. Jeden prostokąt jest całkowicie zawarty w drugim (lub pokrywają się) 3. Rezultatem przecięcia jest jakiś wypukły wielokąt. Obliczysz obszar wielokąta, dzieląc go na trójkąty (rysując segmenty od pierwszego wierzchołka do każdego innego, z wyjątkiem sąsiedniego raz). Podsumujesz obszary. Możesz użyć twierdzenia Herodota, aby skalibrować obszar trójkąta, i tam pojawia się geometria szkoły średniej.