-
X-Received: by 10.140.28.117 with SMTP id 108mr20503qgy.38.1414429624360; Mon, 27 Oct
2014 10:07:04 -0700 (PDT)
X-Received: by 10.140.28.117 with SMTP id 108mr20503qgy.38.1414429624360; Mon, 27 Oct
2014 10:07:04 -0700 (PDT)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!news.glorb.com!
peer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media
.com!r10no659687igi.0!news-out.google.com!u5ni12qab.1!nntp.google.com!u7no53032
8qaz.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Mon, 27 Oct 2014 10:07:04 -0700 (PDT)
In-Reply-To: <m2lp5j$q7o$1@node2.news.atman.pl>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=31.61.136.116;
posting-account=VFwkXwoAAADdT4-lLKRZrMYkTjizGoyn
NNTP-Posting-Host: 31.61.136.116
References: <m2lp5j$q7o$1@node2.news.atman.pl>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <4...@g...com>
Subject: Re: Łączenie wielokątów
From: Wojciech Muła <w...@g...com>
Injection-Date: Mon, 27 Oct 2014 17:07:04 +0000
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 3162
X-Received-Body-CRC: 604588584
Xref: news-archive.icm.edu.pl pl.comp.programming:206819
[ ukryj nagłówki ]On Monday, October 27, 2014 4:42:45 PM UTC+1, Borneq wrote:
> Pierwsza rzecz to szybka detekcja, czy wielokąty dotykają się czy też
> przecinają. Można dość szybko odrzucić gdy nie przecinają się prostokąty
> ograniczające wielokąty (niekoniecznie wypukłe)
Zamiast prostokątów możesz użyć wielokątów-otoczek wypukłych zbudowanych
w oparciu o wierzchołki wielokąta. Testy przecięcia wielokątów wypukłych
są całkiem proste, a masz dużo większą precyzję niż dla prostokątów.
Ale to tylko propozycja.
> Druga sprawa - gdy mamy dwa wielokąty, które się przecinają lub dotykają
> to jak je połączyć w jeden?
Chodzi Ci o sumę boolowską, tak? Potrzebujesz tak naprawdę policzyć
wszystkie przecięcia krawędzi obu wielokątów i je podzielić
w tych punktach na "pododcinki". W tym momencie każdy odcinek może
być jednoznacznie zakwalifikowany, czy leży wewnątrz wielokąta 1 lub 2
(albo jest krawędzią) - te, które leżą wewnątrz któregokolwiek
wielokąta kasujesz. Klasyfikację "pododcinków" możesz sprowadzić do
stwierdzenia, czy którykolwiek jego punkt (np. środkowy) należy do
wielokąta.
Policzenie wszystkich przecięć możesz zrobić metodą zamiatania,
tu masz opis: http://wazniak.mimuw.edu.pl/index.php?title=Zaawanso
wane_algorytmy_i_struktury_danych/Wyk%C5%82ad_12#prz
ecinanie_sie_zbioru_odcinkow
Chociaż, jeśli nie masz wielokątów o dużej liczbie krawędzi możesz
na początek zrobić naiwną metodą każdy-z-każdym.
Natomiast stwierdzenie, czy punkt należy do wielokąta można zrobić
na wiele sposobów: http://erich.realtimerendering.com/ptinpoly/
Prosty do zaprogramowania jest "Crossing test".
Generalnie nie jest to bardzo trudne, ale trzeba uważać w przypadkach
skrajnych. Rozważ użycie gotowca, np. http://www.cgal.org/.
w.
Następne wpisy z tego wątku
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-20 Fiat 125p wer. pikup - w PRL moszna było, w III Reczy [pospolitej] nie moszna
- 2024-05-19 Pożar salonu z chińskimi elektrykami
- 2024-05-18 LED
- 2024-05-19 ceny nieruchomości
- 2024-05-18 Szczecin => UX/UI Designer <=
- 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 <=