Witam

temat na pograniczu programowania i matematyki.

Mam w przestrzeni dwuwymiarowej 2 prostokąty. Wszystkie spółrzędne ich
wierzchołków są całkowite.

Chodzi o to, by przesunąć jeden z nich w kierunku drugiego po prostej
przechodzącej przez środki owych prostokątów tak, by zetknęły się bokami.

W pierwszej chwili problem wydaje się prosty, jednakże po wygenerowaniu
różnych złośliwych przypadków (prostokąty o bardzo dużych lub bardzo małych
proporcjach długości boków), każdy z wymyślonych przeze mnie algorytmów
odpada.

Oczywiscie nie chodzi o to, aby przesuwać prostokąt z małym krokiem i
sprawdzać, czy nastąpiła kolizja. Potrzebowałbym gotowy wektor.

Są na to gotowe algorytmy?

--
Michał Walenciak
gmail.com kicer86
http://kicer.sileman.net.pl
gg: 3729519

do góry

W dniu 2011-12-21 09:05, Kicer pisze:
> Witam
>
> temat na pograniczu programowania i matematyki.
>
> Mam w przestrzeni dwuwymiarowej 2 prostokąty. Wszystkie spółrzędne ich
> wierzchołków są całkowite.
>
> Chodzi o to, by przesunąć jeden z nich w kierunku drugiego po prostej
> przechodzącej przez środki owych prostokątów tak, by zetknęły się bokami.
[...]

Czy prostokąty mają boki równoległe do siebie (lub może lepiej - do osi
współrzędnych)? W ogólności możesz zetknąć wierzchołek do boku.

--
Paweł Kierski
n...@p...net

do góry

Kicer <...@...c> napisał(a):

> Witam
>
> temat na pograniczu programowania i matematyki.
>
> Mam w przestrzeni dwuwymiarowej 2 prostokąty. Wszystkie spółrzędne ich
> wierzchołków są całkowite.
>
> Chodzi o to, by przesunąć jeden z nich w kierunku drugiego po prostej
> przechodzącej przez środki owych prostokątów tak, by zetknęły się bokami.
>
> W pierwszej chwili problem wydaje się prosty, jednakże po wygenerowaniu
> różnych złośliwych przypadków (prostokąty o bardzo dużych lub bardzo małych
> proporcjach długości boków), każdy z wymyślonych przeze mnie algorytmów
> odpada.
>
> Oczywiscie nie chodzi o to, aby przesuwać prostokąt z małym krokiem i
> sprawdzać, czy nastąpiła kolizja. Potrzebowałbym gotowy wektor.
>
> Są na to gotowe algorytmy?
>
nie jest to raczej specjalnie trudne (ale szczerze mowiac nie
chce mi sie tego robic) trzeba troche pokombinowac,

np napisac jakies rownania x1-x2=C i (x1-x2)=D*(y1-y2)
(C i D stale; C=ax1/2+ax2/2 D=(x0-x2)/(y0-y2) )
[z tego wychodzi y1=C/D+y2] - to dla przypadku
jesli wiadomo ze prostokat 1 walnie w 2 w boczna scianke
(jesli w gorna to rownanie na y1-y2 itd]

i cos z tym pokombinowac + rozwazyc wczesniej
czy walnie w scianke gorna czy boczna)




--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

W dniu 2011-12-21 09:05, Kicer pisze:
> Witam
>
> temat na pograniczu programowania i matematyki.
>
> Mam w przestrzeni dwuwymiarowej 2 prostokąty. Wszystkie spółrzędne ich
> wierzchołków są całkowite.

I rozumiem boki pokrywają sie z osiami układu.
Ta całkowitość to złe założenie.

> Chodzi o to, by przesunąć jeden z nich w kierunku drugiego po prostej
> przechodzącej przez środki owych prostokątów tak, by zetknęły się bokami.

No to weźmy kwadraty o bokach 2. pozycja (środka) pierwszego
to (0,0), drugiego (3,1). Wektor, po którym się poruszamy
to wielokrotność -(3,1). Aby kwadraty się zetknąły
trzeba przesunąć ten po prawej o -1 w lewo.
Ale to oznacza też przesunięcie go o 1/3 w dół!

Albo wspolrzedne całkowite, albo przesuwanie się po prostej.
Pogodzić się tego nie da.

> Są na to gotowe algorytmy?

Na niemożliwe rzeczy? Niewiele.
Jeśli dopuścisz wspolrzedne rzeczywiste, to prosto.
Dwa równania na przesunięcie (x i y), wybierasz
to z mniejszym wynikiem.

pzdr
bartekltg

do góry

Paweł Kierski wrote:

>
> Czy prostokąty mają boki równoległe do siebie (lub może lepiej - do osi
> współrzędnych)?
>

tak, mają.


--
Michał Walenciak
gmail.com kicer86
http://kicer.sileman.net.pl
gg: 3729519

do góry

bartekltg wrote:

> W dniu 2011-12-21 09:05, Kicer pisze:
>> Witam
>>
>> temat na pograniczu programowania i matematyki.
>>
>> Mam w przestrzeni dwuwymiarowej 2 prostokąty. Wszystkie spółrzędne ich
>> wierzchołków są całkowite.
>
> I rozumiem boki pokrywają sie z osiami układu.

tak

> Ta całkowitość to złe założenie.

nie do konca założenie, tylko tak musi być ;)

>
> No to weźmy kwadraty o bokach 2. pozycja (środka) pierwszego
> to (0,0), drugiego (3,1). Wektor, po którym się poruszamy
> to wielokrotność -(3,1). Aby kwadraty się zetknąły
> trzeba przesunąć ten po prawej o -1 w lewo.
> Ale to oznacza też przesunięcie go o 1/3 w dół!

można wprowadzić kolejne założenie mowiące, że prosta składa się
tylko i wyłącznie z punktów o współrzędnych całkowitych.

Inaczej - przesuwam sobie prostokąt o wektor o wartościach rzeczywistych po
ich zaokrągleniu :)

> Albo wspolrzedne całkowite, albo przesuwanie się po prostej.
> Pogodzić się tego nie da.
>
>> Są na to gotowe algorytmy?
>
> Na niemożliwe rzeczy? Niewiele.
> Jeśli dopuścisz wspolrzedne rzeczywiste, to prosto.

jw. mogę dopuścić a potem sobie zaokrąglę.

> Dwa równania na przesunięcie (x i y), wybierasz
> to z mniejszym wynikiem.

mogę prosić ciutkę jaśniej? jak wyznaczam te dwa równania?

>
> pzdr
> bartekltg

pozdrawiam

--
Michał Walenciak
gmail.com kicer86
http://kicer.sileman.net.pl
gg: 3729519

do góry

On 2011-12-21, Kicer <...@...c> wrote:
> Paweł Kierski wrote:
>
>>
>> Czy prostokąty mają boki równoległe do siebie (lub może lepiej - do osi
>> współrzędnych)?
>>
>
> tak, mają.

To algorytm ustalania jakie powinno być przesunięcie jest prosty.

1. Prostokąty A i B mają współrzędne:
* xA1, xA2, yA1, yA2
* xB1, xB2, yB1, yB2
2. Upewniasz się, że xA1 < xA2, xB1 < xB2, yA1 < yA2, yB1 < yB2.
Chodzi o to, żeby mieć lewy bok i dolny bok zawsze we współrzędnej *1
3. Upewniasz się, że xA1 < xB1.
Chodzi o to, żeby wiedzieć, który prostokąt jest lewy, a który prawy.
4. Jeśli to prawy prostokąt jest przesuwany, liczysz wektor przesunięcia
równoległego do osi x między xA2 i xB1. Jeśli lewy prostokąt jest
przesuwany, wektor ma przeciwny zwrot.
5. Obliczasz wektor przesunięcia wzdłuż osi y. Może być za pomocą
proporcji. Możesz nawet sprawdzić, czy udało się tak przesunąć
prostokąt, żeby dowolny bok poziomy jednego prostokąta znajdował się
między bokami drugiego prostokąta (wystarczą dwie proste alternatywy).

Nie wiem czemu uważasz, że to jakieś czary. Co najwyżej, jak ktoś
w innej odpowiedzi zauważył, wynik z punktu piątego może nie być liczbą
całkowitą.

--
Secunia non olet.
Stanislaw Klekot

do góry

Stachu 'Dozzie' K. wrote:

> On 2011-12-21, Kicer <...@...c> wrote:
>> Paweł Kierski wrote:
>>
>>>
>>> Czy prostokąty mają boki równoległe do siebie (lub może lepiej - do osi
>>> współrzędnych)?
>>>
>>
>> tak, mają.
>
> To algorytm ustalania jakie powinno być przesunięcie jest prosty.
>
> 1. Prostokąty A i B mają współrzędne:
> * xA1, xA2, yA1, yA2
> * xB1, xB2, yB1, yB2


niechę będzie że mam:

+---+
| |
| |
| |
| |
| |
+---+

+-----------------+
| |
+-----------------+

> 2. Upewniasz się, że xA1 < xA2, xB1 < xB2, yA1 < yA2, yB1 < yB2.
> Chodzi o to, żeby mieć lewy bok i dolny bok zawsze we współrzędnej *1

upewnione ;)

> 3. Upewniasz się, że xA1 < xB1.
> Chodzi o to, żeby wiedzieć, który prostokąt jest lewy, a który prawy.

ten na dole jest prawy

> 4. Jeśli to prawy prostokąt jest przesuwany, liczysz wektor przesunięcia
> równoległego do osi x między xA2 i xB1. Jeśli lewy prostokąt jest
> przesuwany, wektor ma przeciwny zwrot.

no to wyszedł wektor o długości 0, bo odlegość na osi odciętych (x) między
prawym bokiem górnego a lewym bokiem dolnego == 0.

> 5. Obliczasz wektor przesunięcia wzdłuż osi y. Może być za pomocą
> proporcji. Możesz nawet sprawdzić, czy udało się tak przesunąć
> prostokąt, żeby dowolny bok poziomy jednego prostokąta znajdował się
> między bokami drugiego prostokąta (wystarczą dwie proste alternatywy).

tu przyznam, że nie do konca rozumiem. Z proporcji miedzy czym a czym?
Jeśli chodzi o jakieś proporcje związane z wektorem poziomym to i tak wyszło
0, wiec nie ma co liczyć.

> Nie wiem czemu uważasz, że to jakieś czary. Co najwyżej, jak ktoś
> w innej odpowiedzi zauważył, wynik z punktu piątego może nie być liczbą
> całkowitą.


rozważ taki przypadek:

+----------+
| |
+----------+

+----------+
| |
+----------+

wg punktu 3 dolny prostokąt jest prawy

wg punktu 4 wyjdzie mi wektor nakazujący przesunąć dolny prostokąt w prawo i
to o spory kawałek, bo liczę wektor o współrzędnej x = xB1 - xA2 co daje
niespodziewane liczbę ujemną.

Nie ważne co mówią kolejne punkty, bo i tak algorytm już poszedł w maliny,
bo oczekiwane przesunięcie (po prostej między środkami prostokątów) to 1 w
lewo i 1 w górę.

Poświęciłem naprawdę sporo czasu na rozwiązanie tego problemu i uwierz mi,
wszelkie algorytmy wymyślane "od ręki" mają jakieś błędy dla wymyślnych
przypadków.

pozdrawiam

--
Michał Walenciak
gmail.com kicer86
http://kicer.sileman.net.pl
gg: 3729519

do góry

On 2011-12-22, Kicer <...@...c> wrote:
> niechę będzie że mam:
>
> +---+
> | |
> | |
> | |
> | |
> | |
> +---+
>
> +-----------------+
> | |
> +-----------------+

>> 3. Upewniasz się, że xA1 < xB1.
>> Chodzi o to, żeby wiedzieć, który prostokąt jest lewy, a który prawy.
>
> ten na dole jest prawy
>
>> 4. Jeśli to prawy prostokąt jest przesuwany, liczysz wektor przesunięcia
>> równoległego do osi x między xA2 i xB1. Jeśli lewy prostokąt jest
>> przesuwany, wektor ma przeciwny zwrot.
>
> no to wyszedł wektor o długości 0, bo odlegość na osi odciętych (x) między
> prawym bokiem górnego a lewym bokiem dolnego == 0.

Słusznie. I tyle, jak rozumiem, powinien wyjść.

>> 5. Obliczasz wektor przesunięcia wzdłuż osi y. Może być za pomocą
>> proporcji. Możesz nawet sprawdzić, czy udało się tak przesunąć
>> prostokąt, żeby dowolny bok poziomy jednego prostokąta znajdował się
>> między bokami drugiego prostokąta (wystarczą dwie proste alternatywy).
>
> tu przyznam, że nie do konca rozumiem. Z proporcji miedzy czym a czym?

Elementarna planimetria. Przesuwasz wzdłuż prostej przechodzącej przez
środki, czyli o dwa wektory (równoległe do osi) składające się na wektor
łączący środki prostokątów albo coś proporcjonalnego. Jeśli masz
wyliczony wektor przesunięcia wzdłuż jednej osi, drugi się wylicza
prosto.

> Poświęciłem naprawdę sporo czasu na rozwiązanie tego problemu i uwierz mi,
> wszelkie algorytmy wymyślane "od ręki" mają jakieś błędy dla wymyślnych
> przypadków.

Jeśli wystarczy ci, że dowolne boki się zetkną, to możesz policzyć dwa
warianty i sprawdzić, przy którym prostokąty się rzeczywiście zetkną.
Algorytm ten sam. Chyba że wynajdziesz inny problem.

--
Secunia non olet.
Stanislaw Klekot

do góry

W dniu 2011-12-21 22:15, Kicer pisze:


>> Dwa równania na przesunięcie (x i y), wybierasz
>> to z mniejszym wynikiem.
>
> mogę prosić ciutkę jaśniej? jak wyznaczam te dwa równania?


Kurde. Brać się do matematyki a nie do programowania!

W = suma szerokości / 2
H = suma wysokości /2

Wektor od prostokąta A do B
[ X_B - X_A ; Y_B - Y_A ]

I teraz szukasz takiego t, aby była kolizja,
czyli albo

abs(X_B - X_A) * (1-t) = W

albo

abs( Y_B - Y_A ) (1-t) = H


Z obu równań wyznaczasz t (zamieniasz wzorek na t = ...,
nie trzeba rozwiązywać tego numerycznie;)) i bierzesz
to mniejsze. Jeśli początkowo prostokąty były
rozłączne, to t będzie w przedziale (0,1).

Wektorem, o który należy przesunać prostokąt B jest
[ X_B - X_A ; Y_B - Y_A ] * (-t)

Tyle, że t będzie jakąś liczba wymierną, a więc
i wektor nie musi być całkowity.

pzdr
bartekltg

do góry