[Delphi]Para najbliżej leżących siebie punktów w układzie

Odpowiedz Nowy wątek
Snatch
2007-01-15 23:13
Snatch
0

W jaki sposób można sprawdzić jaka jest najmniejsza odległość między dwoma z pośród wileu punktów, których współrzędne zawiera tablica w(w[i,1]=x, w[i,2]=y gdzie i <1,10000>). Znam [URL=http://upload.wikimedia.org/m[...]f25a2c56ed7ae04b8e68.png]wzór na wyznaczanie odległości między dwoma punktami[/URL], ale w jaki sposób sprawdzić wszystkie kombinacje (skonstruować pętle) i wybrać parę punktów najbliżej siebie leżących?

Pozostało 580 znaków

2007-01-16 09:14

Rejestracja: 15 lat temu

Ostatnio: 1 tydzień temu

Lokalizacja: Gdańsk

0

robisz petle która po kolei dla kazdego indeksu tablicy liczy odległości i zapisuje to do innej tablicy: odległość i indeksy z tej wczesniejszej (? ale brzmi). Potem przeszukujesz powstałą tablice i znajdujesz najmniejszą odległość i masz wtedy indeksy pkt najblizej siebie lezących. Teraz to juz tylko znaleźć je w tej pierwszej tablicy

Pozostało 580 znaków

2007-01-16 09:18

Rejestracja: 17 lat temu

Ostatnio: 3 tygodnie temu

0

no zasadniczo musisz sprawdzic wszystkie kombinacje:/

ale moznaby zrobic cos takiego:

for i := 1 to 10000 do begin
  for j := 1 to 10000 do begin
    if (abs(tab[i,1]-tab[j,1]) < minOdleglosc) OR (abs(tab[i,2]-tab[j,2]) < minOdleglosc) then begin
      if i <> j then begin
        odl :=  pow(x1-x2,2)+pow(y1-y2,2);
        if odl < min then begin 
          min := odl
          minOdleglosc := sqrt(min);
          X1 := tab[i,1];
          Y1 := tab[i,2];
          X2 := tab[i,1];
          Y2 := tab[i,2];
        end;
      end;
    end;
  end;
end; 

spowoduje to pewne ograniczenie ilosci potegowan i pierwiastkowan
trzeba sobie teraz odpowiedziec na bardzo wazne pytanie

Co chcialbys robic w zyciu, i zaczac to robic! //żarcik:P

czy koszt sprawdzania tego warunku jest mniejszy od zaoszczedzonego kosztu potegowan i pierwiastkowan
(mi sie wydaje ze tak)

[!!!]
Pomysl przedstawiony przez SebaZ jest nie najlepszy gdyz wymaga tych samych (jesli nie wiekszych) obliczen co moj + koszt wyszukania minimalnej wartosci w tablicy + dodatkowej pamieci na nowa tablice o wymiarach 10000 x 10000!! [!!!]


Pozostało 580 znaków

Sir Daban
2007-01-16 10:15
Sir Daban
0

if (abs(tab[i,1]-tab[j,1]) < min) and (abs(tab[i,2]-tab[j,2]) < min) then begin

Jonny jeśli widzę dobrze to robisz poważny matematyczny błąd.
zakąłdasz że odległość pomiędzy punktami bedzie najmniejsza, a dokładnie wyrażenie
a2+b2 wtedy gdy: a<amin i b<bmin co nie jest zgodne z prawdą.
Weżmu punkty (1,1000) i (1,1001) mamy więc warunek w którym odległości na osiach to 0 i 1000, czyli odległość to sqrt(010+10001000) =1000.
Bierzemy drugą parę (1,1) i (4,5) wówczas odległości na osiach to 3 i 4, czyli sqrt(33+44)=5
Wg. Twojego algorytmu nawet nie dojdzie do obliczeń dla drugiego punktu.

Co do rozwiązania problemu:
Nie musisz robić drugiej tablicy, wystarczy jak zapamiętasz najniższy wynik i miejsce odpowiednich punktów w tablicy. Pętlę robićz od elemntu pierwszego do ostatniego w tablicy dla pobrania pierwszego elementu pary, a wewnątrz niej pętlę od elementu pierwszego+1 do ostatniego w tablicy dla pobrania elementu drugiego. Zaczynasz od ustawienai odległości na ujemną i zaczynasz sprawdzanie czy pierwsza odległość jest wieksza (musi być przynajmniej zerem więc będzie), a następnei wpisujesz jej wynik i zapamiętujesz punkty. Bierzesz następną parę i porównujesz, zawsze z wartościąminimalną, jeśli bedzie mniejsza to ponownei zapisujesz, jak nie bierzesz następną i tak aż do skończenia par punktów.
Jonny ma rację, można to przyspieszyć:
1) jeśli odległość wyniesie zero - to już mniejszej się nie da i przerywamy pętlę.
2) warunkiem podobnym do tego Jonnego, ale jeśli obydwie odległości na osiach są większe od odpowiadających im dla odległości minimalnej, to możemy mieć pewność że odległość miedzy punktami będzie wieksza, ale tylko w tym przypadku.

Pozostało 580 znaków

Sir Daban
2007-01-16 10:39
Sir Daban
0

if (abs(tab[i,1]-tab[j,1]) < min) and (abs(tab[i,2]-tab[j,2]) < min) then begin

Jonny jeśli widzę dobrze to robisz poważny matematyczny błąd.
zakąłdasz że odległość pomiędzy punktami bedzie najmniejsza, a dokładnie wyrażenie
a2+b2 wtedy gdy: a<amin i b<bmin co nie jest zgodne z prawdą.
Weżmu punkty (1,1000) i (1,1001) mamy więc warunek w którym odległości na osiach to 0 i 1000, czyli odległość to sqrt(010+10001000) =1000.
Bierzemy drugą parę (1,1) i (4,5) wówczas odległości na osiach to 3 i 4, czyli sqrt(33+44)=5
Wg. Twojego algorytmu nawet nie dojdzie do obliczeń dla drugiego punktu.

Co do rozwiązania problemu:
Nie musisz robić drugiej tablicy, wystarczy jak zapamiętasz najniższy wynik i miejsce odpowiednich punktów w tablicy. Pętlę robićz od elemntu pierwszego do ostatniego w tablicy dla pobrania pierwszego elementu pary, a wewnątrz niej pętlę od elementu pierwszego+1 do ostatniego w tablicy dla pobrania elementu drugiego. Zaczynasz od ustawienai odległości na ujemną i zaczynasz sprawdzanie czy pierwsza odległość jest wieksza (musi być przynajmniej zerem więc będzie), a następnei wpisujesz jej wynik i zapamiętujesz punkty. Bierzesz następną parę i porównujesz, zawsze z wartościąminimalną, jeśli bedzie mniejsza to ponownei zapisujesz, jak nie bierzesz następną i tak aż do skończenia par punktów.
Jonny ma rację, można to przyspieszyć:
1) jeśli odległość wyniesie zero - to już mniejszej się nie da i przerywamy pętlę.
2) warunkiem podobnym do tego Jonnego, ale jeśli obydwie odległości na osiach są większe od odpowiadających im dla odległości minimalnej, to możemy mieć pewność że odległość miedzy punktami będzie wieksza, ale tylko w tym przypadku.

Pozostało 580 znaków

Snatch
2007-01-16 11:22
Snatch
0

Dzięki wszystkim za odpowiedzi czas zacząć działać coś z tym.

Pozostało 580 znaków

Snatch
2007-01-16 11:32
Snatch
0
 wynik:= sqrt(sqr(tab[2,1] - tab[1,1]) + sqr(tab[2,2] - tab[1,2]));
  for i:=1 to 10000 do
  for j:=i+1 to 10000 do
    begin
    if (wynik > sqrt(sqr(tab[j,1] - tab[i,1]) + sqr(tab[j,2] - tab[i,2]))) then
    wynik:= sqrt(sqr(tab[2,1] - tab[1,1]) + sqr(tab[2,2] - tab[1,2]));
    end;
  writeln(wynik);

Doszedłem do takiego rozwiązania ale prgram nie działa ;-( Może wie ktoś dlaczego tak jest?

Pozostało 580 znaków

Sir Daban
2007-01-16 11:41
Sir Daban
0

Bo w linijce przypisania nowego wyniku skopiowałeś linijkę poczatkową.

Pozostało 580 znaków

Snatch
2007-01-16 11:58
Snatch
0

Poprawiłem tą linijkę i dalej występuje ten sam kłopot. Aplikacja po otwarciu zaraz się zamyka. Może operacje zajmują za dużo pamięci?

Pozostało 580 znaków

2007-01-16 12:10

Rejestracja: 17 lat temu

Ostatnio: 3 tygodnie temu

0

wprowadzilem drobne poprawki do mojego algorytmu
mianowicie:
zadziej liczy sie pierwiastek
i w warunku zamiast AND jest OR

w tym warunku, ktory Sir Daban zakwestionowal
chodzi o to aby roznica odleglosci na osiach miedzy punktami
byla mniejsza od wyznaczonej odleglosci minimalnej

poniewaz gdy mamy juz ustalone minimum dla
A=(0,0) B=(3,4) minOdleglosc = 5
nie ma sensu liczyc juz dla punktow
A=(0,0) B=(2,5) bo odleglosc na osi OY jest 5 czyil rowna minOdleglosc ale trzeba jeszcze dodac czesc z osi OX czyli wyjdzie 5,39....

Ogolnie bedzie to wygladalo tak ze sie sprawdza tylko te punkty B, ktore leza wewnatrza kwadratu opisanego na okregu o srodku w punkcie A i promieniu r=minOdleglosc

mysle ze moj algorytm jest dobry:D


Pozostało 580 znaków

2007-01-16 12:18

Rejestracja: 17 lat temu

Ostatnio: 3 tygodnie temu

0

zrob moze cos zeby czekal na koncu na nacisniecie dowolnego klawisza np

readln;

(sorki jesli juz to zrobiles)


Pozostało 580 znaków

Odpowiedz

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