Algorytm.

Pytania o rozwiązania zadań.
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Artegor
Stały bywalec
Stały bywalec
Posty: 594
Rejestracja: 09 lis 2015, 19:25
Podziękowania: 364 razy
Płeć:

Algorytm.

Post autor: Artegor » 08 paź 2016, 11:32

Podaj algorytm wyliczający część wspólną dwóch zadanych prostokątów o bokach równoległych do osi układu współrzędnych.


No i od czego tutaj zacząć, takich możliwości jest kilkanaście.

Awatar użytkownika
panb
Expert
Expert
Posty: 3172
Rejestracja: 26 kwie 2010, 22:54
Lokalizacja: Nowiny Wielkie
Otrzymane podziękowania: 1086 razy
Płeć:

Post autor: panb » 08 paź 2016, 12:27

"...wyliczający część wspólną ..." - znaczy chodzi o pole powierzchni tej wspólnej części?
Wcale nie ma tak dużo możliwości.
Jak podajesz dane?

Artegor
Stały bywalec
Stały bywalec
Posty: 594
Rejestracja: 09 lis 2015, 19:25
Podziękowania: 364 razy
Płeć:

Post autor: Artegor » 08 paź 2016, 14:08

Zrobiłem 8 przypadków, może niektóre były te same, lecz przekonało mnie to o prawdziwości algorytmu.

Oznaczyłem, że lewe górne wierzchołki prostokątów to odpowiednio A, C i E.
Prawe dolne wierzchołki to B, D, F. Każdy z nich ma współrzędne np. \(A_.{x}\)

Więc wyliczenie współrzędnych E(x,y) i F(x,y) to zastosowanie operacji min, max.


No i właśnie... jeden z przypadków, który założyłem to taki gdy prostokąty nie mają części wspólnych. Wtedy algorytm nie wiem czy działa poprawnie. Więc może przed jego zastosowaniem należy sprawdzić, czy te prostokąty mają część wspólną?


Co do algorytmu to:

E.x = max(A.x, c,x)
E.y = min(A.y, C.y)
F.x = min(B.x, D.x)
F.y = max(B.y, D.y)

Awatar użytkownika
panb
Expert
Expert
Posty: 3172
Rejestracja: 26 kwie 2010, 22:54
Lokalizacja: Nowiny Wielkie
Otrzymane podziękowania: 1086 razy
Płeć:

Post autor: panb » 08 paź 2016, 16:33

Mnie uczono, że nazwy zmiennych powinny mieć cos wspólnego z tym, co te zmienne oznaczają.

Niech \(L_1,\,\, L_2\) - współrzędne lewych krawędzi prostokątów, \(P_1,\,\,\, P_2\) - współrzędne prawych krawędzi odpowiednio pierwszego i drugiego prostokąta.
Podobnie \(G_1, \,\,\, G_2\) oraz \(D_1,\,\,\, D_2\) - to współrzędne górnych i dolnych krawędzi prostokątów.
d - długość, s - szerokość, P - pole
  1. \(L_1\le L_2 \So d=P_1-L_2\) w przeciwnym razie \(d=P_2-L_1\)
  2. \(d\le0 \So P=0\) w przeciwnym razie
  3. \(G_1>G_2 \So s=G_2-D_1\) w przeciwnym razie \(s=G_1-D_2\)
  4. \(s\le0 \So P=0\) w przeciwnym razie \(P=d\cdot s\)
Sprawdź, czy to działa? Ewentualnie wprowadź poprawki.
Daj znać jakie poprawki były potrzebne, bo może ktoś będzie miał takie zadanie w przyszłości i mu się przyda.

Artegor
Stały bywalec
Stały bywalec
Posty: 594
Rejestracja: 09 lis 2015, 19:25
Podziękowania: 364 razy
Płeć:

Re: Algorytm.

Post autor: Artegor » 08 paź 2016, 20:18

Całkowicie zaburza to moją koncepcję, która jest dobra bo sprawdziłem wszystkie możliwości. No i na zajęciach mówili nam, aby użyć funkcji min, max.

Awatar użytkownika
panb
Expert
Expert
Posty: 3172
Rejestracja: 26 kwie 2010, 22:54
Lokalizacja: Nowiny Wielkie
Otrzymane podziękowania: 1086 razy
Płeć:

Post autor: panb » 08 paź 2016, 20:22

To się nie przejmuj moim sposobem. Zwłaszcza, że wymaga dopracowania.

Panko
Fachowiec
Fachowiec
Posty: 2939
Rejestracja: 20 gru 2013, 22:41
Lokalizacja: Radom
Otrzymane podziękowania: 1554 razy
Płeć:

Re: Algorytm.

Post autor: Panko » 08 paź 2016, 22:16

Czemu chcesz na siłę wyważać otwarte drzwi ?
Analizowałeś algorytm Sutherlanda-Hodgmana ?

jagodziaja123
Witam na forum
Witam na forum
Posty: 1
Rejestracja: 14 paź 2017, 16:47
Płeć:

Post autor: jagodziaja123 » 14 paź 2017, 17:10

Czy mógłby mi ktoś wytłumaczyć dlaczego w taki sposób wygląda ta funkcja min, max? dlaczego akurat te współrzędne są maksymalne i minimalne?