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

Groups > pl.comp.programming > #29422

Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni

Show all headers | View raw

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.

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web