Přejít k obsahu


Space subdivision to speed-up convex hull construction in E3

Citace:
SKALA, V., MAJDIŠOVÁ, Z., ŠMOLÍK, M. Space subdivision to speed-up convex hull construction in E3. Advances in Engineering Software, 2016, roč. 91, č. 1, s. 12-22. ISSN: 0965-9978
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Space subdivision to speed-up convex hull construction in E3
Rok vydání: 2016
Autoři: Prof. Ing. Václav Skala CSc. , Ing. Zuzana Majdišová , Ing. Michal Šmolík
Abstrakt CZ: Konvexní obálky jsou základním geometrickým nástrojem využívaným v mnoha algoritmech. Tento článek popisuje rychlý, implementačně jednoduchý a robustní Smart Convex Hull (S-CH) algoritmus pro určení konvexní obálky množiny bodů v E3. Algoritmus je založen na ?sférickém? dělení prostoru. Hlavní myšlenka S-CH algoritmu spočívá v eliminaci co nejvíce bodů předtím, než je konstruována konvexní obálka. Experimentální výsledky ukazují, že pouze malé množství bodů je použito při finálním výpočtu konvexní obálky. Provedené experimenty taktéž dokazují, že navržený S-CH algoritmus dosahuje v porovnání s jinými algoritmy pro E3 lepší časové složitosti.
Abstrakt EN: Convex hulls are fundamental geometric tools used in a number of algorithms. This paper presents a fast, simple to implement and robust Smart Convex Hull (S-CH) algorithm for computing the convex hull of a set of points in E3. This algorithm is based on ?spherical? space subdivision. The main idea of the S-CH algorithm is to eliminate as many input points as possible before the convex hull construction. The experimental results show that only a very small number of points are used for the final convex hull calculation. Experiments made also proved that the proposed S-CH algorithm achieves a better time complexity in comparison with other algorithms in E3.
Klíčová slova

Zpět

Patička