Algorytm.

[Artegor]

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.

[panb]

"...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]

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)

[panb]

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]

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.

[panb]

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

[Panko]

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

[jagodziaja123]

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?