-
Data: 2017-02-20 21:54:08
Temat: Re: Siatka/Topologia trójkątna/Wyszukiwanie obwiedni
Od: bartekltg <b...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 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-18 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-18 Warszawa => Software .Net Developer <=
- 2024-05-18 Warszawa => Mid/Senior QA Engineer <=
- 2024-05-18 Ulm => Solution Architect (sichere Kommunikation und IoT-Loesungen <=
- 2024-05-18 Katowice => Head of Virtualization Platform Management and Operating S
- 2024-05-18 Warszawa => SAP WM Consultant / Execution <=
- 2024-05-18 Wrocław => Consultant/Implementer Comarch ERP XL <=
- 2024-05-18 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-05-18 Warszawa => Account Manager (Recruitment Services) <=
- 2024-05-18 Łódź => Salesperson - CRM Systems <=
- 2024-05-18 Łódź => Handlowiec - Systemy CRM <=
- 2024-05-17 ZŁOMNIK o pracy w TVN TURBO, nowych przepisach i współczesnej motoryzacji. Turbo Taryfa!
- 2024-05-17 Białystok => DevOps Engineer Conexa First (Contractor) <=
- 2024-05-17 Warszawa => Starszy inżynier oprogramowania (Rust) <=
- 2024-05-17 Zabrze => Junior HelpDesk <=