W dniu 2011-12-22 10:53, bartekltg pisze:
> 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 ]

W innym poście widzę, że z tym są problemy:
X_A,Y_A to współrzędny x,y _środka_ prostokąta 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

Stachu 'Dozzie' K. wrote:

> 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ść.

nie ;) przesuwając dolny po prostej przechodzącej przez środki prostokątów,
powinien się on przesunąć lekko w lewo.

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

no dobra, pierwszy wyszedł mi 0 to drugi wyjdzie ile? 0?:>

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

tego narazie nie skomentuję, bo ciągle są braki w punktach powyżej ;)

pozdrawiam

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

do góry

bartekltg wrote:

> 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!

(4, 9)
+--+
| | prostokąt A; środek to punkt 2, 7; Ha = 4; Wa = 4
| |
+--+
(0, 5) (6,4)
++
||
|| prostokąt B; środek to punkt 5, 2; Hb = 4; Wb = 2
++
(4,0)

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

W = (Wa + Wb) / 2 = 3
H = (Ha + Hb) / 2 = 4;

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

jak napisales w poście niżej, chodzi o środki, więc:

[ 5 - 2; 2 - 7] = [3; -5]

>
> 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

abs(X_B - X_A) == 3;
t = (3 - W)/3 = 0

abs(Y_B - Y_A) == 5;
t = (5 - H)/5 = 1/5

>
>
> 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).
>

wygrywa zatem t = 0

[3; -5] * 0 = [0; 0]

wychodzi zatem, ze prostokątów nie trzeba przesuwać.

Jesli wezmę drugie t, które wychodzi 1/5, to wygląda sensowniej, bo wektor
ma postać:
[-3/5; -1], co już by się zgadzało.

pozdrawiam

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

do góry

On 2011-12-22, Kicer <...@...c> wrote:
> Stachu 'Dozzie' K. wrote:
>
>> 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ść.
>
> nie ;) przesuwając dolny po prostej przechodzącej przez środki prostokątów,
> powinien się on przesunąć lekko w lewo.
>
>>
>>>> 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.
>
> no dobra, pierwszy wyszedł mi 0 to drugi wyjdzie ile? 0?:>

Założyłem (niesłusznie), że to boki pionowe mają się zetknąć. A policz
teraz wariant dla boków poziomych i wyjaśnij, czemu uważasz że *to* nie
zadziała?

>>> 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.
>>
>
> tego narazie nie skomentuję, bo ciągle są braki w punktach powyżej ;)

Skomentuj, skomentuj. Bo algorytm wymaga _trywialnej_ poprawki w postaci
właśnie tego: liczysz wektor dla wariantu, gdy prostokąty mają się
zetknąć bokami pionowymi i dla wariantu z bokami poziomymi. Sprawdzasz,
w którym wariancie prostokąty rzeczywiście się zetkną i ten wybierasz.

Co to mówiłeś o swoim mnóstwie czasu spędzonym nad algorytmem?

--
Secunia non olet.
Stanislaw Klekot

do góry

W dniu 2011-12-22 11:50, Kicer pisze:
> bartekltg wrote:
>
>> 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!
>
> (4, 9)
> +--+
> | | prostokąt A; środek to punkt 2, 7; Ha = 4; Wa = 4
> | |
> +--+
> (0, 5) (6,4)
> ++
> ||
> || prostokąt B; środek to punkt 5, 2; Hb = 4; Wb = 2
> ++
> (4,0)
>
>>
>> W = suma szerokości / 2
>> H = suma wysokości /2
>
> W = (Wa + Wb) / 2 = 3
> H = (Ha + Hb) / 2 = 4;
>
>>
>> Wektor od prostokąta A do B
>> [ X_B - X_A ; Y_B - Y_A ]
>
> jak napisales w poście niżej, chodzi o środki, więc:
>
> [ 5 - 2; 2 - 7] = [3; -5]


>>
>> 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
>
> abs(X_B - X_A) == 3;
> t = (3 - W)/3 = 0
>
> abs(Y_B - Y_A) == 5;
> t = (5 - H)/5 = 1/5
>
>>
>>
>> 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).
>>
>
> wygrywa zatem t = 0

Aj, późniejszy (minus mi mieszał)

>
> [3; -5] * 0 = [0; 0]

[3; -5] * -1/5 = [-3/5; 1]

B podskakuje oczko w górę. Zetknął się.


> wychodzi zatem, ze prostokątów nie trzeba przesuwać.
>
> Jesli wezmę drugie t, które wychodzi 1/5, to wygląda sensowniej, bo wektor
> ma postać:
> [-3/5; -1], co już by się zgadzało.

Źle znaki:)

pzdr
bartekltg

do góry

Stachu 'Dozzie' K. wrote:

>>
>> no dobra, pierwszy wyszedł mi 0 to drugi wyjdzie ile? 0?:>
>
> Założyłem (niesłusznie), że to boki pionowe mają się zetknąć. A policz
> teraz wariant dla boków poziomych i wyjaśnij, czemu uważasz że to nie
> zadziała?

uważam, że drugi wariant nie zadziala? Tzn gdzie tak napisalem?

Reszty nie skomentuję, bo zaczynasz to w czym jesteś najlepszy: wycieczki
osobiste bez wdawania się w detale.

pozdrawiam,
z mojej strony EOT

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

do góry

bartekltg wrote:

>> wygrywa zatem t = 0
>
> Aj, późniejszy (minus mi mieszał)
>
>>
>> [3; -5] * 0 = [0; 0]
>
> [3; -5] * -1/5 = [-3/5; 1]
>
> B podskakuje oczko w górę. Zetknął się.
>
>
>> wychodzi zatem, ze prostokątów nie trzeba przesuwać.
>>
>> Jesli wezmę drugie t, które wychodzi 1/5, to wygląda sensowniej, bo
>> wektor ma postać:
>> [-3/5; -1], co już by się zgadzało.
>
> Źle znaki:)

no to by już wyjasniało wszystko, dzięki :)

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

do góry

On 2011-12-21 09:05, Kicer wrote:
> 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.

Hmm a ten problem jest rozwiązywalny ? Bo tak na moje oko założenie
liczb całkowitych na wierzchołkach i wektora łączącego środki który
będzie liczbą wymierną może powodować że nie będzie takiego wektora.

--
Tomek

do góry

Tomek Banach wrote:

>
> Hmm a ten problem jest rozwiązywalny ? Bo tak na moje oko założenie
> liczb całkowitych na wierzchołkach i wektora łączącego środki który
> będzie liczbą wymierną może powodować że nie będzie takiego wektora.


generalnie prostokaty są na tyle duże (szerokość i wysokośc idą w
milionach), że zaokrąglenie do wartości całkowitej nie ma żadnego znaczenia
:)

Rozwiązanie podane przez bartekltg działa wyśmienicie ;)

pozdrawiam

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

do góry

On 2011-12-30 09:44, Kicer wrote:
> Tomek Banach wrote:
>
>>
>> Hmm a ten problem jest rozwiązywalny ? Bo tak na moje oko założenie
>> liczb całkowitych na wierzchołkach i wektora łączącego środki który
>> będzie liczbą wymierną może powodować że nie będzie takiego wektora.
>
>
> generalnie prostokaty są na tyle duże (szerokość i wysokośc idą w
> milionach), że zaokrąglenie do wartości całkowitej nie ma żadnego znaczenia
> :)

dobra dobra wszyscy wiem jak czesto sprawdzają się szanse jedna na
milion. A potem spadają samoloty ;)

--
Tomek

do góry