-
X-Received: by 10.157.27.162 with SMTP id z31mr535713otd.7.1487333415735; Fri, 17 Feb
2017 04:10:15 -0800 (PST)
X-Received: by 10.157.27.162 with SMTP id z31mr535713otd.7.1487333415735; Fri, 17 Feb
2017 04:10:15 -0800 (PST)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!news.nask.pl!news.nask.org.pl!news.unit
0.net!news.glorb.com!e137no819442itc.0!news-out.google.com!15ni2770itm.0!nntp.g
oogle.com!e137no826523itc.0!postnews.google.com!glegroupsg2000goo.googlegroups.
com!not-for-mail
Newsgroups: pl.comp.programming
Date: Fri, 17 Feb 2017 04:10:15 -0800 (PST)
In-Reply-To: <o84qbb$f4m$1@node2.news.atman.pl>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=37.47.139.199;
posting-account=VFwkXwoAAADdT4-lLKRZrMYkTjizGoyn
NNTP-Posting-Host: 37.47.139.199
References: <o84qbb$f4m$1@node2.news.atman.pl>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <f...@g...com>
Subject: Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni
From: Wojciech Muła <w...@g...com>
Injection-Date: Fri, 17 Feb 2017 12:10:15 +0000
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:210250
[ ukryj nagłówki ]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.
Następne wpisy z tego wątku
- 17.02.17 14:07 bartekltg
- 17.02.17 15:32 slawek
- 17.02.17 15:36 slawek
- 20.02.17 21:24 Mateusz Bogusz
- 20.02.17 21:54 bartekltg
- 20.02.17 22:39 M.M.
- 20.02.17 23:01 Mateusz Bogusz
- 20.02.17 23:37 bartekltg
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-07 Chess
- 2024-05-07 Do czego nadaje się QDockWidget z bibl. Qt?
- 2024-05-07 Vitruvian Man - parts 7-11a
- 2024-05-07 Warszawa => International freight forwarder <=
- 2024-05-07 Zielona Góra => Inżynier R&D Mechanik <=
- 2024-05-07 ministranci
- 2024-05-07 Warszawa => Manager Sprzedaży <=
- 2024-05-07 Białystok => Inżynier DevOps (projekt JP) <=
- 2024-05-07 Ulm => IT Systems Administrator and Customer Support Engineer <=
- 2024-05-07 Warszawa => Junior Frontend Developer <=
- 2024-05-07 Ulm => Integration & Test Engineer <=
- 2024-05-07 Warszawa => Business Systems Sales Representative <=
- 2024-05-07 Białystok => Technical Lead ( (Java Background)) <=
- 2024-05-07 Białystok => React Native Developer <=
- 2024-05-07 Białystok => Technical Leader (Java Background) <=