Obliczanie wspólnego pola

0

Mam takie zadanie:

Napisz program, który mając dane współrzędne dwóch prostokątów, których boki są równoległe do osi współrzędnych, policzy pole części wspólnej tych prostokątów.

W pierwszym wierszu wejścia znajdują się 4 liczby całkowite, oznaczające odpowiednio współrzędną x- ową i y- ową lewego górnego rogu i współrzędną x- ową i y- ową prawego dolnego rogu pierwszego prostokąta.

W drugim wierszu wejścia znajdują się 4 liczby całkowite, oznaczające odpowiednio współrzędną x- ową i y- ową lewego górnego rogu i współrzędną x- ową i y- ową prawego dolnego rogu drugiego prostokąta.

Jaki jest lepszy sposób niż ifowanie różnych możliwych ustawień współrzędnych? Bo wiadomo, że można ifować różne wzajemne ustawienia wierzchołków, a wewnątrz dawać, co wtedy trzeba od siebie odjąć i pomnożyć, żeby wyszło, ale to jest mordęga i nie wydaje mi się, żeby nie było prostszego sposobu. Mógłby ktoś pomóc?

0

Pewnie źle to zrobiłem, ale po godzinie myślenia wyskubałem takie coś (Delphi):

Type TRectangle = Record
                   A, B: TPoint;
                  End;
Function Pole(K1, K2: TRectangle): Integer;
Begin
 Result := (K1.B.X - K2.A.X) * (K1.B.Y - K2.A.Y);
End;

Jestem prawie pewien, że oblicza dobrze (nie mam jak sprawdzić, czy wyniki, które ona daje są poprawne).
Jeżeli ten kod, to bzdura to sorry ;)

0

Dzięki wielkie. A czy dałbyś radę napisać to w pseudokodzie/ceplusie? Bo nie wiem, jaką funkcję mają dwie pierwsze linijki.

3

Przepisane ze źródeł C# :). x i y to współrzędne lewego, górnego rogu.

a1 = max(a.x, b.x);
a2 = min(a.x + a.długość, b.x + b.długość);
a3 = max(a.y, b.y);
a4 = min(a.y + a.wysokość, b.y + b.wysokość);

jeżeli (a2 >= a1 && a4 >= a3)
    pole = (a2 - a1) * (a4 - a3)
inaczej
    pole = 0

http://stackoverflow.com/ques[...]rea-of-overlapping-rectangles
A tutaj masz opisany algorytm dynamiczny na wspólne pole nieskończonej ilości prostokątów.

1

Odpowiednikiem Recordu będzie struktura:

struct Point
{
    double x;
    double y;
};

struct Rectangle
{
    Point A;
    Point B;
};
0

Jeżeli programujesz pod Windows, to WinAPI zawiera funkcję IntersectRect
... tyle w temacie

0

scyzoryk się otwiera, zdaje się, nikt matematyki nie uczył? współrzędne kartezjańskie polegające na twierdzeniu pitagorasa powinny wystarczyć, a nie liczyć obszary, które się przeniakją :D

0

Rev - super, a algorytm, do którego zalinkowałeś już w ogóle :D Dzięki wielkie wszystkim.

Tylko jedno pytanie, odnośnie:
a4 = min(a.y + a.wysokość, b.y + b.wysokość);
Dlaczego dodajemy wysokość do y-owej wspólrzędnej lewego górnego wierzchołka? Przecież to wychodzi nam już ponad prostokąt.

0

Ah, zapomniałem wspomnieć - układ współrzędnych w GDI/C# zaczyna się w lewym górnym rogu od (0,0) i zwiększa się w dół i prawo.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0