V powierzchni - algorytm

marsoft · Post autor: **marsoft** » 7 sty 2006, o 14:35

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

W_Zygmunt · Post autor: **W_Zygmunt** » 7 sty 2006, o 17:09

marsoft pisze:Ten okrąg jest kulą

Zupełnie nie rozumiem. Okrąg jest tworem dwuwymiarowym, natomiast kula to bryła trójwymiarowa. ??????

Fibik · Post autor: **Fibik** » 7 sty 2006, o 18:23

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

marsoft · Post autor: **marsoft** » 7 sty 2006, o 19:31

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

Fibik · Post autor: **Fibik** » 8 sty 2006, o 02:08

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

marsoft · Post autor: **marsoft** » 8 sty 2006, o 11:21

[ Dodano: Wto Sty 10, 2006 1:07 pm ]
no wiec nici z sugestii lub jakiegoś złotego środka???????

Fibik · Post autor: **Fibik** » 10 sty 2006, o 20:03

Pisałem na PW - może nie działa?

marsoft · Post autor: **marsoft** » 11 sty 2006, o 20:33

nie nie otzymałem

Fibik · Post autor: **Fibik** » 12 sty 2006, o 11:56

Niemożliwe.
Gdzie jest kierownik tego lokalu?

Tomasz Rużycki · Post autor: **Tomasz Rużycki** » 12 sty 2006, o 12:36

Jakiś błąd... Wyślij raz jeszcze, zapisało się w 'wysłanych', bądź zalega w 'do wysłania'.

Pozdrawiam,
--
Tomasz Rużycki

marsoft · Post autor: **marsoft** » 12 sty 2006, o 15:52

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

dalej nic nie mam :/

Jeśli możesz to wyślij na maila

dbdariusz@wp.pl - wielkie dzięki

forum ma jakieś dziwne błędy - ADMIN DLACZEGO??????!

Fibik · Post autor: **Fibik** » 13 sty 2006, o 04:38

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

marsoft · Post autor: **marsoft** » 16 sty 2006, o 02:26

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]

Fibik · Post autor: **Fibik** » 16 sty 2006, o 12:34

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.

marsoft · Post autor: **marsoft** » 16 sty 2006, o 17:56

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.

ok kontury mam. Licze minimum hmm dla każdego pixela mam rozumieć.

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