Obliczanie wspólnego pola

Odpowiedz Nowy wątek
2011-08-24 17:00
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?

Zawsze jest lepszy sposób, niż if'y! :P - Patryk27 2011-08-24 17:14
Nie wątpię. Chociaż jakaś podpowiedź? :) - Tigro 2011-08-24 17:28

Pozostało 580 znaków

2011-08-24 18:15
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 ;)


edytowany 1x, ostatnio: Patryk27, 2011-08-24 18:16

Pozostało 580 znaków

2011-08-24 18:42
0

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

Pozostało 580 znaków

2011-08-24 18:50
Rev

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.


edytowany 1x, ostatnio: Rev, 2011-08-24 18:51

Pozostało 580 znaków

2011-08-24 18:52
1

Odpowiednikiem Recordu będzie struktura:

struct Point
{
    double x;
    double y;
};
 
struct Rectangle
{
    Point A;
    Point B;
};

Pozostało 580 znaków

2011-08-24 18:59
0

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

edytowany 1x, ostatnio: simplex, 2011-08-25 00:09
nie union, a intersect jak już. i wywołanie metody z api będzie raczej bardziej kosztowne niż wykonanie zupełnie tego samego w miejscu - Rev 2011-08-24 19:09
wywołanie funkcji z WinAPI nie jest bardziej kosztowne od każdej innej funkcji. nie mamy tu chyba do czynienia z silnikiem grafiki 3D? - Azarien 2011-08-24 21:34
Oczywiście miało być IntersectRect, ale sam nie wiem czemu napisałem UnionRect. Przepraszam, mój błąd, a post poprawiłem - simplex 2011-08-25 00:11

Pozostało 580 znaków

2011-08-24 19:10
MiM
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

Mi się scyzoryk otwiera gdy widzę pomysł by w tym zadaniu stosować twierdzenie Pitagorasa. - bogdans 2011-08-24 20:03

Pozostało 580 znaków

2011-08-25 00:23
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.

edytowany 1x, ostatnio: Tigro, 2011-08-25 00:28

Pozostało 580 znaków

2011-08-25 08:40
Rev
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.


Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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