V powierzchni - algorytm
-
- Użytkownik
- Posty: 64
- Rejestracja: 17 kwie 2005, o 10:51
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 3 razy
V powierzchni - algorytm
W jaki sposób w daną powierzchnie wpisać możliwy największy okrąg?
Wytłumaczę do czego miej więcej on jest potrzebny:
Więc gdy mamy tam jakąś powierzchnie to szukamy na niej punktu w którym będziemy mogli wpisać największy możliwy okrąg. Mając okrąg a konkretnie promień wyliczamy objętość kuli V = (4/3 pi r^3)3. Następnie ten obszar w którym jest ta kula przedstawiona jako okrąg zamalujemy. Zostaje nam wtedy obszar zmniejszony o pole powierzchni okręgu. Powtarzamy ten krok tz. szukamy znowu miejsca w którym można wpisać największy okrąg - znowu objętość i tak dalej. Pętla ma się kończym wtedy gdy okrąg czyli kula w tym przykadku będzie wynosiła 1 pixel. Myślę, że wytłumaczyłem w miare zrozumiale.
macie jakiś pomysł który to zrobi szybko bo zależy tu najbardziej na czasie wyszukiwania
dzięki wielkie za wszelkie opinie i pomoce
Wytłumaczę do czego miej więcej on jest potrzebny:
Więc gdy mamy tam jakąś powierzchnie to szukamy na niej punktu w którym będziemy mogli wpisać największy możliwy okrąg. Mając okrąg a konkretnie promień wyliczamy objętość kuli V = (4/3 pi r^3)3. Następnie ten obszar w którym jest ta kula przedstawiona jako okrąg zamalujemy. Zostaje nam wtedy obszar zmniejszony o pole powierzchni okręgu. Powtarzamy ten krok tz. szukamy znowu miejsca w którym można wpisać największy okrąg - znowu objętość i tak dalej. Pętla ma się kończym wtedy gdy okrąg czyli kula w tym przykadku będzie wynosiła 1 pixel. Myślę, że wytłumaczyłem w miare zrozumiale.
macie jakiś pomysł który to zrobi szybko bo zależy tu najbardziej na czasie wyszukiwania
dzięki wielkie za wszelkie opinie i pomoce
Ostatnio zmieniony 7 sty 2006, o 18:56 przez marsoft, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 545
- Rejestracja: 1 wrz 2004, o 22:47
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 53 razy
V powierzchni - algorytm
Zupełnie nie rozumiem. Okrąg jest tworem dwuwymiarowym, natomiast kula to bryła trójwymiarowa. ??????marsoft pisze:Ten okrąg jest kulą
-
- Użytkownik
- Posty: 971
- Rejestracja: 27 wrz 2005, o 22:56
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 11 razy
- Pomógł: 75 razy
V powierzchni - algorytm
Szukamy kolejno największych okręgów a później, mając już promienie, liczymy objętości kul - sumujemy.
Problem polega na znalezieniu największego koła, które można wpisać w dowolny wielokąt, nawet wklęsły.
Ekstremum funkcji:
\(\displaystyle{ f(r) = r}\)
oraz ograniczenie:
\(\displaystyle{ (x-a)^2 + (y-b)^2 < r^2}\)
Każdy (x, y) należy do figury o kolejnych wierzchołkach:
\(\displaystyle{ W_k(x_k, y_k),\ k=,\ W_1 = W_n}\)
Trzeba to teraz tak przekształcić, aby można było obliczyć pochodne i...
Problem polega na znalezieniu największego koła, które można wpisać w dowolny wielokąt, nawet wklęsły.
Ekstremum funkcji:
\(\displaystyle{ f(r) = r}\)
oraz ograniczenie:
\(\displaystyle{ (x-a)^2 + (y-b)^2 < r^2}\)
Każdy (x, y) należy do figury o kolejnych wierzchołkach:
\(\displaystyle{ W_k(x_k, y_k),\ k=,\ W_1 = W_n}\)
Trzeba to teraz tak przekształcić, aby można było obliczyć pochodne i...
-
- Użytkownik
- Posty: 64
- Rejestracja: 17 kwie 2005, o 10:51
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 3 razy
V powierzchni - algorytm
pomysł miałem taki:
1. Mając tą jakąś powierzchnie mamy zbiór punktów A_n(x,y) przy n-ilość pixeli (punktów) powierzchni.
2. Każdy punkt będzie reprezentował okrąg o promieniu r=1pixel
Zrobić pętke która:
a)będzie dodawała do tych A_n punktów dugość promienia zwiększoną o jeden pixel. Oczywiśćie ten A_n wtedy to okrąg.
b)Sprawdzamy czy okrąg reprezentowany prze dany A_n natrafił na krawędź powierzchni (obrys)reprezentowany przez (x,y). Jeśli tak to zapisujemy do tablicy A_n promień.
c) Pętla będzie się powtarzała dopóki wszystkie okręgi A_n natrafią na krawędź. Ostatni A_n będzie reprezentował największy okrąg.
d) Następnie zamalujemy go.
e)Później trzeba wykorzystań r zapisane w tablicach - Zaczynamy od największego i badamy czy nadal on jest największy. Jeśli nie to A_n reprezentowany przez mniejsze r i tak dalej...
------------------------------------------------------
hmm
1. Mając tą jakąś powierzchnie mamy zbiór punktów A_n(x,y) przy n-ilość pixeli (punktów) powierzchni.
2. Każdy punkt będzie reprezentował okrąg o promieniu r=1pixel
Zrobić pętke która:
a)będzie dodawała do tych A_n punktów dugość promienia zwiększoną o jeden pixel. Oczywiśćie ten A_n wtedy to okrąg.
b)Sprawdzamy czy okrąg reprezentowany prze dany A_n natrafił na krawędź powierzchni (obrys)reprezentowany przez (x,y). Jeśli tak to zapisujemy do tablicy A_n promień.
c) Pętla będzie się powtarzała dopóki wszystkie okręgi A_n natrafią na krawędź. Ostatni A_n będzie reprezentował największy okrąg.
d) Następnie zamalujemy go.
e)Później trzeba wykorzystań r zapisane w tablicach - Zaczynamy od największego i badamy czy nadal on jest największy. Jeśli nie to A_n reprezentowany przez mniejsze r i tak dalej...
------------------------------------------------------
hmm
-
- Użytkownik
- Posty: 971
- Rejestracja: 27 wrz 2005, o 22:56
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 11 razy
- Pomógł: 75 razy
V powierzchni - algorytm
Coś takiego prawie będzie działać, ale:
Zwiększanie od 1 do r dla w x h punktów i teraz bieganie po tych okręgach...
policzmy ile to operacji:
w = h = N - rozmiar bitmapy
idziemy z R od 1 do N/2 razy 2piR razy, i dla N*N punktów:
przybliżona liczba operacji: \(\displaystyle{ n = 2\pi(N/2)^3/3 N^2 = \frac{\pi}{12}N^5}\)
jeśli zmniejszmy to 20 razy (przy brzegach R < N/2) to wyjdzie około n = N^5/100,
dla N = 1000, n = 10^13 = 10000 mld,
gdyby: 1 rozkaz = 1 instrukcja, byłoby to 100000s > 1 doba, dla procesora 1GHz
Jest lepszy sposób, ale musiałbym pisać to z 3 godziny, a później jeszcze z 9 razy wyjaśniać... i tak do wakacji...
Zwiększanie od 1 do r dla w x h punktów i teraz bieganie po tych okręgach...
policzmy ile to operacji:
w = h = N - rozmiar bitmapy
idziemy z R od 1 do N/2 razy 2piR razy, i dla N*N punktów:
przybliżona liczba operacji: \(\displaystyle{ n = 2\pi(N/2)^3/3 N^2 = \frac{\pi}{12}N^5}\)
jeśli zmniejszmy to 20 razy (przy brzegach R < N/2) to wyjdzie około n = N^5/100,
dla N = 1000, n = 10^13 = 10000 mld,
gdyby: 1 rozkaz = 1 instrukcja, byłoby to 100000s > 1 doba, dla procesora 1GHz
Jest lepszy sposób, ale musiałbym pisać to z 3 godziny, a później jeszcze z 9 razy wyjaśniać... i tak do wakacji...
-
- Użytkownik
- Posty: 64
- Rejestracja: 17 kwie 2005, o 10:51
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 3 razy
V powierzchni - algorytm
[ Dodano: Wto Sty 10, 2006 1:07 pm ]
no wiec nici z sugestii lub jakiegoś złotego środka???????
no wiec nici z sugestii lub jakiegoś złotego środka???????
Ostatnio zmieniony 11 sty 2006, o 20:35 przez marsoft, łącznie zmieniany 1 raz.
- Tomasz Rużycki
- Użytkownik
- Posty: 2970
- Rejestracja: 8 paź 2004, o 17:16
- Płeć: Mężczyzna
- Lokalizacja: Suchedniów/Kraków
- Podziękował: 4 razy
- Pomógł: 293 razy
V powierzchni - algorytm
Jakiś błąd... Wyślij raz jeszcze, zapisało się w 'wysłanych', bądź zalega w 'do wysłania'.
Pozdrawiam,
--
Tomasz Rużycki
Pozdrawiam,
--
Tomasz Rużycki
-
- Użytkownik
- Posty: 64
- Rejestracja: 17 kwie 2005, o 10:51
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 3 razy
V powierzchni - algorytm
dalej nic nie mam :/Tomasz Rużycki pisze:Jakiś błąd... Wyślij raz jeszcze, zapisało się w 'wysłanych', bądź zalega w 'do wysłania'.
Tomasz Rużycki
Jeśli możesz to wyślij na maila
dbdariusz@wp.pl - wielkie dzięki
forum ma jakieś dziwne błędy - ADMIN DLACZEGO??????!
-
- Użytkownik
- Posty: 971
- Rejestracja: 27 wrz 2005, o 22:56
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 11 razy
- Pomógł: 75 razy
V powierzchni - algorytm
Wersja uproszczona.
Po zaznaczeniu obszaru otrzymasz punkty konturu, czyli taki wielokąt o wierzchołkach:
\(\displaystyle{ P_1, P_2, P_3, ...}\)
1. Dla każdego punktu wewnątrz obszaru (x,y) liczysz minimalną odległość do tego konturu
(należy liczyć dla kolejnych odcinków i wybrać najbliższy).
Te minimalne odległośći zapisujemy do tablicy: t[x][y] = r (lepiej r^2 - pierwiastek później)
2. Szukamy w t maksimum (można to zrobić już w trakcie wcześniejszych obliczeń - wtedy zaoszczędzimy sporo czasu) - to jest nasze największe koło - r < 2 to koniec, r >= 2 rysujemy i idziemy dalej
3. Korygujemy odległości w tablicy t, uwzględniając to poprzednie koło - liczymy odległość d od (x,y) do okręgu - prosta sprawa. Jeśli t[x,y] > d, to zmieniamy: t[x,y] = d, idziemy do 2.
var t : array[0..MAX_W-1, 0..MAX_H-1] of single; { albo integer }
MAX_H = MAX_W = 2048 - przykładowo, wtedy t ma rozmiar 16MB - nie deklaruj tego jako zmienną lokalną,
jako globalną też nie.
Zamiast sprawdzać kolor pixela bezpośrednio w obrazku - robimy tablicę:
pixele : array[0..MAX_W-1, 0..MAX_H-1] of byte;
pixele[x,y] := 1; zaznaczony obszar
pixele[x,y] := 0; poza obszarem
Teraz można ze 100 razy szybciej sprawdzić, czy punkt leży w zaznaczonym obszarze:
if pixele[x,y] 0 then jest...
Po zaznaczeniu obszaru otrzymasz punkty konturu, czyli taki wielokąt o wierzchołkach:
\(\displaystyle{ P_1, P_2, P_3, ...}\)
1. Dla każdego punktu wewnątrz obszaru (x,y) liczysz minimalną odległość do tego konturu
(należy liczyć dla kolejnych odcinków i wybrać najbliższy).
Te minimalne odległośći zapisujemy do tablicy: t[x][y] = r (lepiej r^2 - pierwiastek później)
2. Szukamy w t maksimum (można to zrobić już w trakcie wcześniejszych obliczeń - wtedy zaoszczędzimy sporo czasu) - to jest nasze największe koło - r < 2 to koniec, r >= 2 rysujemy i idziemy dalej
3. Korygujemy odległości w tablicy t, uwzględniając to poprzednie koło - liczymy odległość d od (x,y) do okręgu - prosta sprawa. Jeśli t[x,y] > d, to zmieniamy: t[x,y] = d, idziemy do 2.
var t : array[0..MAX_W-1, 0..MAX_H-1] of single; { albo integer }
MAX_H = MAX_W = 2048 - przykładowo, wtedy t ma rozmiar 16MB - nie deklaruj tego jako zmienną lokalną,
jako globalną też nie.
Zamiast sprawdzać kolor pixela bezpośrednio w obrazku - robimy tablicę:
pixele : array[0..MAX_W-1, 0..MAX_H-1] of byte;
pixele[x,y] := 1; zaznaczony obszar
pixele[x,y] := 0; poza obszarem
Teraz można ze 100 razy szybciej sprawdzić, czy punkt leży w zaznaczonym obszarze:
if pixele[x,y] 0 then jest...
-
- Użytkownik
- Posty: 64
- Rejestracja: 17 kwie 2005, o 10:51
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 3 razy
V powierzchni - algorytm
Chwile mnie nie było, ale widze, że pomoc jest
1. Może zacznijmy od pkt pierwszego tz kontur. Ja wycinek zalalowuje w ten sposób, że najpierw rysuje:
image1.Picture.Bitmap.Canvas.Pixels[X,Y]:=clREd;
a następnie zamalowuje
image1.Picture.Bitmap.Canvas.FloodFill(X,Y,clred,fsborder);
Mam problem jak z tego wyciąnąć kontury, bo kontury nie zawsze są tym - >Canvas.Pixels[X,Y]:=clREd; Jak to wyciąnąć już z zamalowanego lub może masz jakiś (zapewne tak) inny lepszy sposób.
2. Co do drugiego to czy dałoby radę wytłumaczyć bardziej ten 3 pkt bo jednak dla mnie troche to nie jasne - szczególne to że if t[x,y]>d to t[x,y]=d czy nie if t[x,y] ten pkt chyba właśńie ma to wykonywać, ale nie rozumiem w ogóle.
dzieki wielkie - pokłony oczywiście z góry[/quote]
1. Może zacznijmy od pkt pierwszego tz kontur. Ja wycinek zalalowuje w ten sposób, że najpierw rysuje:
image1.Picture.Bitmap.Canvas.Pixels[X,Y]:=clREd;
a następnie zamalowuje
image1.Picture.Bitmap.Canvas.FloodFill(X,Y,clred,fsborder);
Mam problem jak z tego wyciąnąć kontury, bo kontury nie zawsze są tym - >Canvas.Pixels[X,Y]:=clREd; Jak to wyciąnąć już z zamalowanego lub może masz jakiś (zapewne tak) inny lepszy sposób.
2. Co do drugiego to czy dałoby radę wytłumaczyć bardziej ten 3 pkt bo jednak dla mnie troche to nie jasne - szczególne to że if t[x,y]>d to t[x,y]=d czy nie if t[x,y] ten pkt chyba właśńie ma to wykonywać, ale nie rozumiem w ogóle.
dzieki wielkie - pokłony oczywiście z góry[/quote]
-
- Użytkownik
- Posty: 971
- Rejestracja: 27 wrz 2005, o 22:56
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 11 razy
- Pomógł: 75 razy
V powierzchni - algorytm
Kontur musisz mieć - ślad prowadzenia myszki.
Pewnie później tym FloodFill go wypełniasz.
2. Liczysz minimum, zatem źle kombinujesz.
Punkty na okręku.
W okręgu jest koło, a ono nas nie interesuje - zostało już wymazane.
Pewnie później tym FloodFill go wypełniasz.
2. Liczysz minimum, zatem źle kombinujesz.
Punkty na okręku.
W okręgu jest koło, a ono nas nie interesuje - zostało już wymazane.
-
- Użytkownik
- Posty: 64
- Rejestracja: 17 kwie 2005, o 10:51
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 3 razy
V powierzchni - algorytm
ok kontury mam. Licze minimum hmm dla każdego pixela mam rozumieć.Fibik pisze:Kontur musisz mieć - ślad prowadzenia myszki.
Pewnie później tym FloodFill go wypełniasz.
2. Liczysz minimum, zatem źle kombinujesz.
Punkty na okręku.
W okręgu jest koło, a ono nas nie interesuje - zostało już wymazane.
Jest koło, ale są pkt które znajdują się w kole a ich nie mammy brać pod uwage, ale one są w tablicy t[x,y] dla wszystkich pixeli w skład których wchodzą też współżędne znajdujące się wkole. Pytam zatem jak ma ta funkcja wyglądać aby ominąć te pkt t[x,y] i jak dalej wyliczyć następne największe koło które ma się zawierać w wycinku już wypełnionym kołem. Wchodzą wtedy tak jakby dodatkowe kontury nom nie? (koła) hmmm.....mógłbyś pojaśnić - thx dziękuje