Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #29413 > unrolled thread

Siatka/Topologia trójkątna/Wyszukiwanie obwiedni

Back to article view | Back to pl.comp.programming

Contents

  Siatka/Topologia trójkątna/Wyszukiwanie obwiedni Mateusz Bogusz <mabakay@o2.pl> - 2017-02-16 19:17 +0100
    Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni bartekltg <bartekltg@gmail.com> - 2017-02-16 22:52 +0100
      Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni bartekltg <bartekltg@gmail.com> - 2017-02-17 05:13 +0100
        Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni slawek <fake@fakeemail.com> - 2017-02-17 08:51 +0100
          Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni bartekltg <bartekltg@gmail.com> - 2017-02-17 14:07 +0100
            Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni slawek <fake@fakeemail.com> - 2017-02-17 15:32 +0100
        Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni "M.M." <mmarszik@gmail.com> - 2017-02-20 13:39 -0800
    Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni slawek <fake@fakeemail.com> - 2017-02-17 01:48 +0100
    Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni Wojciech Muła <wojtek.mula@gmail.com> - 2017-02-17 04:10 -0800
      Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni slawek <fake@fakeemail.com> - 2017-02-17 15:36 +0100
      Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni Mateusz Bogusz <mabakay@o2.pl> - 2017-02-20 21:24 +0100
        Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni bartekltg <bartekltg@gmail.com> - 2017-02-20 21:54 +0100
          Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni Mateusz Bogusz <mabakay@o2.pl> - 2017-02-20 23:01 +0100
            Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni bartekltg <bartekltg@gmail.com> - 2017-02-20 23:37 +0100

#29413 — Siatka/Topologia trójkątna/Wyszukiwanie obwiedni

1. Znajduję trójkąt w który trafiłem promieniem.
2. Liczę normalną trójkąta
3. Szukam wszystkich trójkątów, które mają tą samą normalną - O(n)
4. Wyszukuje spośród nich te, które mają wspólny wierzchołek z trójkątem 
który trafiłem lub z innym który do niego ma - O(n^2)
5. Wyszukuję tylko te krawędzie trójkątów, które należą tylko do jednego 
trójkąta - O(n)

Wiem że da się lepiej. Jakaś podpowiedź? :-)

-- 
Pozdrawiam,
Mateusz Bogusz

[toc] | [next] | [standalone]

#29416

On 16.02.2017 19:17, Mateusz Bogusz wrote:
> 1. Znajduję trójkąt w który trafiłem promieniem.
> 2. Liczę normalną trójkąta
> 3. Szukam wszystkich trójkątów, które mają tą samą normalną - O(n)
> 4. Wyszukuje spośród nich te, które mają wspólny wierzchołek z trójkątem
> który trafiłem lub z innym który do niego ma - O(n^2)
> 5. Wyszukuję tylko te krawędzie trójkątów, które należą tylko do jednego
> trójkąta - O(n)
>
> Wiem że da się lepiej. Jakaś podpowiedź? :-)

Nie opisałeś problemu, który chcesz roziązać.

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#29418

On 16.02.2017 22:52, bartekltg wrote:
> On 16.02.2017 19:17, Mateusz Bogusz wrote:
>> 1. Znajduję trójkąt w który trafiłem promieniem.
>> 2. Liczę normalną trójkąta
>> 3. Szukam wszystkich trójkątów, które mają tą samą normalną - O(n)
>> 4. Wyszukuje spośród nich te, które mają wspólny wierzchołek z trójkątem
>> który trafiłem lub z innym który do niego ma - O(n^2)

A tego w sumie to w ogóle nie rozumiem. Na poziomie gramatycznym.

"..lub z innym który do niego ma"

Co?

>> 5. Wyszukuję tylko te krawędzie trójkątów, które należą tylko do jednego
>> trójkąta - O(n)
>>
>> Wiem że da się lepiej. Jakaś podpowiedź? :-)
>
> Nie opisałeś problemu, który chcesz roziązać.

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#29419

On Fri, 17 Feb 2017 05:13:29 +0100, bartekltg <bartekltg@gmail.com> 
wrote:
> A tego w sumie to w ogóle nie rozumiem.

Przecież to oczywiste.

[toc] | [prev] | [next] | [standalone]

#29423

On 17.02.2017 08:51, slawek wrote:
> On Fri, 17 Feb 2017 05:13:29 +0100, bartekltg <bartekltg@gmail.com> wrote:
>> A tego w sumie to w ogóle nie rozumiem.
>
> Przecież to oczywiste.

No to podziel się.

bartekltg

[toc] | [prev] | [next] | [standalone]

#29424

On Fri, 17 Feb 2017 14:07:03 +0100, bartekltg <bartekltg@gmail.com> 
wrote:
> No to podziel się.

Bartuś, śmieszny jesteś, grzecznie poprosić nie potrafisz.

[toc] | [prev] | [next] | [standalone]

#29432

On Friday, February 17, 2017 at 5:13:36 AM UTC+1, bartekltg wrote:
> On 16.02.2017 22:52, bartekltg wrote:
> > On 16.02.2017 19:17, Mateusz Bogusz wrote:
> >> 1. Znajduję trójkąt w który trafiłem promieniem.
> >> 2. Liczę normalną trójkąta
> >> 3. Szukam wszystkich trójkątów, które mają tą samą normalną - O(n)
> >> 4. Wyszukuje spośród nich te, które mają wspólny wierzchołek z trójkątem
> >> który trafiłem lub z innym który do niego ma - O(n^2)
> 
> A tego w sumie to w ogóle nie rozumiem. Na poziomie gramatycznym.
> 
> "..lub z innym który do niego ma"
> 
> Co?
> 
> >> 5. Wyszukuję tylko te krawędzie trójkątów, które należą tylko do jednego
> >> trójkąta - O(n)
> >>
> >> Wiem że da się lepiej. Jakaś podpowiedź? :-)
> >
> > Nie opisałeś problemu, który chcesz roziązać.
> 
> pzdr
> bartekltg

Ja też nie zrozumiałem zbyt wiele.

[toc] | [prev] | [next] | [standalone]

#29417

On Thu, 16 Feb 2017 19:17:12 +0100, Mateusz Bogusz <mabakay@o2.pl> 
wrote:
> 4. Wyszukuje spośród nich te, które mają wspólny wierzchołek z 
trójkątem 
> który trafiłem lub z innym który do niego ma - O(n^2)

Jeżeli trójkąty znają swoich sąsiadów powinno być szybciej.

[toc] | [prev] | [next] | [standalone]

#29422

On Thursday, February 16, 2017 at 7:17:16 PM UTC+1, Mateusz Bogusz wrote:
> 1. Znajduję trójkąt w który trafiłem promieniem.
> 2. Liczę normalną trójkąta
> 3. Szukam wszystkich trójkątów, które mają tą samą normalną - O(n)
> 4. Wyszukuje spośród nich te, które mają wspólny wierzchołek z trójkątem 
> który trafiłem lub z innym który do niego ma - O(n^2)
> 5. Wyszukuję tylko te krawędzie trójkątów, które należą tylko do jednego 
> trójkąta - O(n)
> 
> Wiem że da się lepiej. Jakaś podpowiedź? :-)

Struktura danych, która pozwoli ci w czasie stałym dowiedzieć się o sąsiadach.
Np. mógłbyś mieć listę wierzchołków, a trójkąty opisywać indeksami do tej
listy. Natomiast każdy wierzchołek miałby jeszcze listę trójkątów do których
należy. Wtedy stwierdzenie, które trójkąty mają wspólne wierzchołki byłoby
szybkie.

Ad 2. Możesz posortować trójkąty ze względu na normalną, wtedy masz O(nlgn),
albo nawet wrzucić do tablicy mieszającej: O(1) oczekiwany.

w.

[toc] | [prev] | [next] | [standalone]

#29425

On Fri, 17 Feb 2017 04:10:15 -0800 (PST), Wojciech 
Muła<wojtek.mula@gmail.com> wrote:
> Ad 2. Możesz posortować trójkąty ze względu na nor=
> malną, wtedy masz O(nlgn),
> albo nawet wrzucić do tablicy mieszającej: O(1) oczekiwany.

Też. Ale struktura która daje łatwy dostęp do sąsiadów pozwala 
odłożyć liczenie normalnych (lazy).

[toc] | [prev] | [next] | [standalone]

#29430

 > Struktura danych, która pozwoli ci w czasie stałym dowiedzieć się o 
sąsiadach.
 > Np. mógłbyś mieć listę wierzchołków, a trójkąty opisywać indeksami do tej
 > listy.

To mam, na wejściu dostaję trzy tablice: wierzchołków, trójkątów w 
postaci 3 kolejnych indeksów wierzchołków, normalnych wierzchołków.

> Natomiast każdy wierzchołek miałby jeszcze listę trójkątów do których
> należy. Wtedy stwierdzenie, które trójkąty mają wspólne wierzchołki byłoby
> szybkie.

Jakbym to dostawał za free, to tak :-) Większość razy liczę obwiednię 
dla nowego zestawu tablic, a cachowanie wszystkiego w pamięci też nie 
wchodzi w grę. Ale dzięki za pomysł, pogłówkuję.

> Ad 2. Możesz posortować trójkąty ze względu na normalną, wtedy masz O(nlgn),
> albo nawet wrzucić do tablicy mieszającej: O(1) oczekiwany.

Też zawsze jakiś zysk.

-- 
Pozdrawiam,
Mateusz Bogusz

[toc] | [prev] | [next] | [standalone]

#29431

On 20.02.2017 21:24, Mateusz Bogusz wrote:
>> Struktura danych, która pozwoli ci w czasie stałym dowiedzieć się o
> sąsiadach.
>> Np. mógłbyś mieć listę wierzchołków, a trójkąty opisywać indeksami do tej
>> listy.
>
> To mam, na wejściu dostaję trzy tablice: wierzchołków, trójkątów w
> postaci 3 kolejnych indeksów wierzchołków, normalnych wierzchołków.


A jednak dobre marudziłem, że nie opisałeś tego porządnie;>
W opisie mówiłeś o normalnych trójkąta, i tam wydawało się oczywiste,
że normalne to normalne powierzchni trójkąta. Mogło jedynie dziwić,
jak chcesz znaleść trójkąty o identycznej normalnej, bo przeszkadza
precyzja obliczeń.

Ty piszesz o normalnych wierzchołków. Znów "oczywistym jest*)"
czyli się domyślam, że masz gładką powierzchnię i interpolujesz
sobie normalną na trójkącie (jak to w grafice się robi).

Ale wtedy
 >>>3. Szukam wszystkich trójkątów, które mają tą samą normalną - O(n)
Oznacza, że szukasz tych, które gdzieś na swojej powierzchni mają
normalną taką jak wyznaczona?

Dla samego zadania nie ma to wielkiego znaczenia, ale cały czas może
si,e to zmienić, bo zajmujemy się domyśleniami jak w (*), a jeden
domyśli się jednego, drugi czego innego, a trzeci uzna, żę równie
dobrze mogą być to  obie wersje, więc nie bedzie nic pisał, póki
się nie wyjaśni;>


>> Natomiast każdy wierzchołek miałby jeszcze listę trójkątów do których
>> należy. Wtedy stwierdzenie, które trójkąty mają wspólne wierzchołki
>> byłoby
>> szybkie.
>
> Jakbym to dostawał za free, to tak :-) Większość razy liczę obwiednię
> dla nowego zestawu tablic, a cachowanie wszystkiego w pamięci też nie
> wchodzi w grę. Ale dzięki za pomysł, pogłówkuję.

Zrobienie tablicy to kodującej to 3*liczba trójkątów + liczba punktów
(na tablicę indeksów, gdzie w głownej tablicy są wpisy dodanego
trójkąta).
Włąśnie dlatego, że ta struktura jest statyczna, raz tworzona,
to nie trzeba się bawić w hashmapy.


>> Ad 2. Możesz posortować trójkąty ze względu na normalną, wtedy masz
>> O(nlgn),
>> albo nawet wrzucić do tablicy mieszającej: O(1) oczekiwany.
>
> Też zawsze jakiś zysk.

Przygotowanie tak danych zajmuje wiecej czasu niż ich przejrzenie
w poszukiwaniu zadanej normalnej.
Jeśli robisz to tylko raz, nie ma żadnego zysku.
Co innego, jeśli takich operacji 'gdzie na powierzchni jest zadana 
normalna' robisz dla wiekszej lioczby wektorów.

No i znów napotykamy problem, czy ta "normlana trójkąta" to normalna
do powierzchni, czy jakaś funkcja norlanlych przypisanych wierzchołkom.

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#29433

> A jednak dobre marudziłem, że nie opisałeś tego porządnie;>
> W opisie mówiłeś o normalnych trójkąta, i tam wydawało się oczywiste,
> że normalne to normalne powierzchni trójkąta. Mogło jedynie dziwić,
> jak chcesz znaleść trójkąty o identycznej normalnej, bo przeszkadza
> precyzja obliczeń.
>
> Ty piszesz o normalnych wierzchołków. Znów "oczywistym jest*)"
> czyli się domyślam, że masz gładką powierzchnię i interpolujesz
> sobie normalną na trójkącie (jak to w grafice się robi).
>
> Ale wtedy
>>>>3. Szukam wszystkich trójkątów, które mają tą samą normalną - O(n)
> Oznacza, że szukasz tych, które gdzieś na swojej powierzchni mają
> normalną taką jak wyznaczona?
>
> Dla samego zadania nie ma to wielkiego znaczenia, ale cały czas może
> si,e to zmienić, bo zajmujemy się domyśleniami jak w (*), a jeden
> domyśli się jednego, drugi czego innego, a trzeci uzna, żę równie
> dobrze mogą być to  obie wersje, więc nie bedzie nic pisał, póki
> się nie wyjaśni;>

Ponieważ mam normalne wierzchołków, to normalną trójkąta liczę tak: 
(n1+n2+n3)/3.

A trójkąty mają tą samą/podobną normalną, gdy ich iloczyn skalarny jest 
bliski 1 :-)

-- 
Pozdrawiam,
Mateusz Bogusz

[toc] | [prev] | [next] | [standalone]

#29434

On 20.02.2017 23:01, Mateusz Bogusz wrote:
>> A jednak dobre marudziłem, że nie opisałeś tego porządnie;>
>> W opisie mówiłeś o normalnych trójkąta, i tam wydawało się oczywiste,
>> że normalne to normalne powierzchni trójkąta. Mogło jedynie dziwić,
>> jak chcesz znaleść trójkąty o identycznej normalnej, bo przeszkadza
>> precyzja obliczeń.
>>
>> Ty piszesz o normalnych wierzchołków. Znów "oczywistym jest*)"
>> czyli się domyślam, że masz gładką powierzchnię i interpolujesz
>> sobie normalną na trójkącie (jak to w grafice się robi).
>>
>> Ale wtedy
>>>>> 3. Szukam wszystkich trójkątów, które mają tą samą normalną - O(n)
>> Oznacza, że szukasz tych, które gdzieś na swojej powierzchni mają
>> normalną taką jak wyznaczona?
>>
>> Dla samego zadania nie ma to wielkiego znaczenia, ale cały czas może
>> si,e to zmienić, bo zajmujemy się domyśleniami jak w (*), a jeden
>> domyśli się jednego, drugi czego innego, a trzeci uzna, żę równie
>> dobrze mogą być to  obie wersje, więc nie bedzie nic pisał, póki
>> się nie wyjaśni;>
>
> Ponieważ mam normalne wierzchołków, to normalną trójkąta liczę tak:
> (n1+n2+n3)/3.

Ja bym to jeszcze znormalizował. Bo tak dostaniesz normalną o dlugości
mniejszej niż jeden.

Za to wtedy nie trzeba dzielić przez 3 "wystarczy"
(n1+n2+n3)/|n1+n2+n3|


<dygresja>
Jak bardzo nie chcesz liczyć pierwiastka (ale karty graficzne,
bo dalej wygląda to na coś z grafiki, liczą przyblizony pierwiastek
sprawnie) można zrobić coś takiego.

n = n1+n2+n3
k = (1-n.*n)/2   //n'*n to suma kwadratów składowych

n = n * (1+k))

lub

n=n*(1+k + 3/2 *k^2)

To drugie daje błąd jak dokładność pojedynczej precyzji dla normalnych
różniących się o ~5 stopni.
<~dygresja>



> A trójkąty mają tą samą/podobną normalną, gdy ich iloczyn skalarny jest
> bliski 1 :-)

Ale wtedy, w zależności od przyjętego epsylona, może się zdarzyć, że
dwa sąsiednie trójkąty zostaną uznane za pasujące, albo żaden,
mimo, że interpolowana normalna odpowiadające szuknej na trójkącie
występuje.

Nie przeszkadza to?


Można by testować, czy normlana n występuje na trójkącie rozpisując
ją jako sumę a1 n1 + a2 n2 + a3 n3 (rozwiązanie układu rownań 3x3,
nie tak źle) i sprawdzić, czy wszytki a_i są dodatnie.

Problemem będą płaskie powierzchnie, gdzie co najmniej dwie n_i
są sobie równe.

pzdr
bartekltg

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web