Próbuję napisać program C ++, który pobiera następujące dane wejściowe od użytkownika do budowy prostokątów (od 2 do 5): wysokość, szerokość, x-pos, y-pos. Wszystkie te prostokąty będą istnieć równolegle do osi xi y, to znaczy wszystkie ich krawędzie będą miały nachylenie 0 lub nieskończoność.
Próbowałem wdrożyć to, o czym mowa w tym pytaniu, ale nie mam dużo szczęścia.
Moja obecna implementacja wykonuje następujące czynności:
// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2
// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2];
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];
int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;
Nie jestem jednak do końca pewien, czy (a) poprawnie zaimplementowałem algorytm, z którym się łączyłem, czy też dokładnie, jak to interpretować?
Jakieś sugestie?
Odpowiedzi:
lub używając współrzędnych kartezjańskich
(X1 jest lewą współrzędną, X2 jest prawą współrzędną, zwiększa się od lewej do prawej, a Y1 jest górną współrzędną, a Y2 jest dolną współrzędną, rośnie od dołu do góry - jeśli nie w taki sposób układ współrzędnych [np. Większość komputerów ma Kierunek Y odwrócony], zamień porównania poniżej ) ...
Załóżmy, że masz Rect A, a Rect B. Dowód jest sprzeczny. Każdy z czterech warunków gwarantuje, że nie może zachodzić na siebie nakładanie się :
Zatem warunkiem braku nakładania się jest
Dlatego wystarczający warunek nakładania się jest odwrotny.
Prawo De Morgana mówi, że
Not (A or B or C or D)
to samo, coNot A And Not B And Not C And Not D
przy użyciu De Morgana, mamy
Jest to równoważne z:
RectA.Left < RectB.Right
] iRectA.Right > RectB.Left
] iRectA.Top > RectB.Bottom
] iRectA.Bottom < RectB.Top
]Uwaga 1 : Jest dość oczywiste, że tę samą zasadę można rozszerzyć na dowolną liczbę wymiarów.
Uwaga 2 : Powinno być również dość oczywiste policzyć nakładanie się tylko jednego piksela, zmienić
<
i / lub>
na tej granicy na a<=
lub a>=
.Uwaga 3 : Ta odpowiedź, przy użyciu współrzędnych kartezjańskich (X, Y), oparta jest na standardowych algebraicznych współrzędnych kartezjańskich (x zwiększa się od lewej do prawej, a Y zwiększa się od dołu do góry). Oczywiście, gdy system komputerowy może inaczej mechanizować współrzędne ekranu (np. Zwiększenie Y od góry do dołu lub X od prawej do lewej), należy odpowiednio dostosować składnię /
źródło
źródło
B.height
powinien byćA.height
#undef min
i#undef max
, lub używając różnych nazw parametrów.#define BETWEEN(value,min,max) \ (\ value > max ? max : ( value < min ? min : value )\ )
xOverlap
odbywa się w jednym wymiarze;rectOverlap
jest dwuwymiarowy. Można go rozszerzyć do N wymiarów za pomocą pętli.źródło
Łatwiej jest sprawdzić, czy prostokąt jest całkowicie poza drugim, więc jeśli tak jest
po lewej...
lub po prawej ...
lub na górze ...
lub na dole ...
drugiego prostokąta nie może się z nim zderzyć. Aby więc mieć funkcję, która zwraca wartość logiczną mówiącą, że zderzają się prostokąty, po prostu łączymy warunki logicznymi ORami i negujemy wynik:
Aby uzyskać pozytywny wynik tylko po dotknięciu, możemy zmienić „<” i „>” za pomocą „<=” i „> =”.
źródło
Zadaj sobie odwrotne pytanie: jak ustalić, czy dwa prostokąty w ogóle się nie przecinają? Oczywiście prostokąt A całkowicie na lewo od prostokąta B nie przecina się. Także jeśli A jest całkowicie po prawej stronie. Podobnie, jeśli A jest całkowicie powyżej B lub całkowicie poniżej B. W każdym innym przypadku przecinają się A i B.
Poniższe informacje mogą zawierać błędy, ale jestem pewien algorytmu:
źródło
Załóżmy, że zdefiniowałeś położenia i rozmiary prostokątów w następujący sposób:
Moja implementacja C ++ wygląda następująco:
Przykładowe wywołanie funkcji zgodnie z powyższym rysunkiem:
Porównania wewnątrz
if
bloku będą wyglądały jak poniżej:źródło
Oto jak to się robi w API Java:
źródło
W pytaniu łączysz się z matematyką dotyczącą tego, kiedy prostokąty mają dowolne kąty obrotu. Jeśli jednak rozumiem fragment pytania o kątach, interpretuję, że wszystkie prostokąty są do siebie prostopadłe.
Ogólna wiedza na temat formuły nakładania się jest następująca:
Korzystając z przykładu:
1) zbierz wszystkie współrzędne x (lewą i prawą) do listy, a następnie posortuj je i usuń duplikaty
2) zbierz wszystkie współrzędne Y (górne i dolne) na listę, a następnie posortuj je i usuń duplikaty
3) utwórz tablicę 2D według liczby odstępów między unikalnymi współrzędnymi x * liczba odstępów między unikalnymi współrzędnymi y.
4) namaluj wszystkie prostokąty na tej siatce, zwiększając liczbę każdej komórki, w której występuje:
5) Kiedy malujesz prostokąty, łatwo jest przechwycić nakładki.
źródło
źródło
Nie uważaj współrzędnych za wskazujące, gdzie są piksele. Pomyśl o nich jako między pikselami. W ten sposób pole prostokąta 2x2 powinno wynosić 4, a nie 9.
źródło
Najłatwiej jest
przede wszystkim pamiętaj, że w komputerach układ współrzędnych jest odwrócony. oś x jest taka sama jak w matematyce, ale oś y zwiększa się w dół i zmniejsza wraz z poruszaniem się w górę ... jeśli prostokąt jest rysowany od środka. jeśli współrzędne x1 są większe niż x2 plus jego połowa szerokości. oznacza to, że przejście do połowy dotknie się. i w ten sam sposób schodząc w dół + połowa jego wysokości. zderzy się ..
źródło
Powiedzmy, że dwa prostokąty to prostokąt A i prostokąt B. Niech ich środkami będą A1 i B1 (współrzędne A1 i B1 można łatwo znaleźć), niech wysokości będą Ha i Hb, szerokość Wa i Wb, niech dx będzie szerokość (x) odległość między A1 a B1 i dy oznacza wysokość (y) odległość między A1 a B1.
Teraz możemy powiedzieć, że możemy powiedzieć, że A i B pokrywają się: kiedy
źródło
Zaimplementowałem wersję C #, łatwo ją przekonwertować na C ++.
źródło
Mam bardzo łatwe rozwiązanie
niech x1, y1 x2, y2, l1, b1, l2 będą odpowiednio kordynatami oraz ich długości i szerokości
rozważyć warunek ((x2
teraz jedynym sposobem, w jaki prostokąt będzie się nakładał, jest to, że punkt przekątny do x1, y1 będzie leżał wewnątrz drugiego prostokąta lub podobnie punkt przekątny do x2, y2 będzie leżał wewnątrz drugiego prostokąta. co implikuje dokładnie powyższy warunek.
źródło
A i B będą dwoma prostokątami. C będzie ich prostokątem okrywającym.
Dba o wszystkie możliwe przypadki.
źródło
Pochodzi z ćwiczenia 3.28 z książki Wprowadzenie do programowania Java - edycja kompleksowa. Kod sprawdza, czy dwa prostokąty są wcięte, czy jeden jest w drugim i czy jeden znajduje się poza drugim. Jeśli żaden z tych warunków nie jest spełniony, oba się pokrywają.
** 3,28 (Geometria: dwa prostokąty) Napisz program, który zachęci użytkownika do wprowadzenia środkowych współrzędnych x, y, szerokości i wysokości dwóch prostokątów i określi, czy drugi prostokąt znajduje się wewnątrz pierwszego, czy zachodzi na pierwszy, jak pokazano na rysunku 3.9. Przetestuj swój program na wszystkie przypadki. Oto przykładowe przebiegi:
Podaj współrzędne x1, y, szerokość i wysokość r1: 2,5 4 2,5 43 Podaj współrzędne x2, y, szerokość i wysokość r2: 1,5 5 0,5 3 r2 znajduje się wewnątrz r1
Podaj współrzędne x1, y, szerokość i wysokość r1: 1 2 3 5.5 Podaj współrzędne x2, y, szerokość i wysokość r3: 3 4 4,5 5 r2 nakłada się na r1
Wprowadź współrzędne x1, y, szerokość i wysokość r1: 1 2 3 3 Wprowadź współrzędne x2, y, szerokość i wysokość r2: 40 45 3 2 r2 nie zachodzi na r1
źródło
źródło
Dla tych z was, którzy używają punktów środkowych i połowy wielkości dla swoich danych prostokątnych, zamiast typowych x, y, w, h lub x0, y0, x1, x1, oto jak to zrobić:
źródło
źródło
Jeśli prostokąty nachodzą na siebie, wówczas obszar nakładania się będzie większy od zera. Teraz znajdźmy obszar nakładania się:
Jeśli nachodzą na siebie, to lewa krawędź zakładki-prostokąt będzie
max(r1.x1, r2.x1)
prawą krawędziąmin(r1.x2, r2.x2)
. Tak więc długość zakładki będzie wynosićmin(r1.x2, r2.x2) - max(r1.x1, r2.x1)
Tak więc obszar będzie:
Jeśli
area = 0
to nie pokrywają się.Proste, prawda?
źródło
„Jeśli wykonasz odejmowanie współrzędnych x lub y odpowiadających wierzchołkom dwóch zwróconych do każdego prostokąta, jeśli wyniki są tego samego znaku, dwa prostokąty nie nachodzą na osie, które” (przepraszam, nie jestem pewien, czy moje tłumaczenie jest poprawne )
Źródło: http://www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
źródło
Kod Java, aby dowiedzieć się, czy prostokąty stykają się lub nakładają na siebie
...
...
źródło