Ball Trees Otimizadas para Criação Interativa de Layouts em 2D com Formas Irregulares
Authors:
Autores
| Person role | Person | |
|---|---|---|
|
7147 |
2809,455
|
|
|
7148 |
2809,455
|
Informations:
Pesc publication
A criação interativa de layouts 2D envolvendo formas irregulares, como texto ou imagens, normalmente é realizada usando um dispositivo apontador para selecionar elementos e arrastá-los para novas posições em uma página. Propomos aumentar a interação do layout com duas operações: prevenção de sobreposição e agrupamento por distância. Como estes são computacionalmente caros e podem dificultar a fluidez da interação, examinamos várias técnicas que visam implementar esses recursos de maneira eficiente. Essas técnicas envolvem a aproximação de formas 2D por coleções de bolas (círculos) que são então organizadas em ball trees, uma hierarquia de volumes delimitadores. Em particular, discutimos um novo algoritmo para aproximar formas com um conjunto reduzido de bolas, bem como algoritmos aprimorados de construção de ball trees. Eles são usados para implementar algoritmos para agrupar formas hierarquicamente por distância e permitir arrastar com prevenção de colisões, no contexto de uma aplicação web de prova de conceito para layout de formas extraídas de imagens segmentadas.
The interactive creation of 2D layouts involving irregular shapes such as text or images is typically carried out using a pointing device to select elements and drag them to new positions on a page. We propose augmenting layout interaction with two operations: overlap avoidance and grouping by distance. Since these are computationally expensive and may hinder the fluidity of the interaction, we examine several techniques that aim at implementing these features in an efficient manner. These techniques involve the approximation of 2D shapes by collections of balls (circles) which are then organized in ball trees, a bounding volume hierarchy. In particular, we discuss a new algorithm for approximating shapes with a reduced set of balls, as well as enhanced ball tree construction algorithms. These are used to implement algorithms to group shapes hierarchically by distance and to allow dragging with collision avoidance, in the context of a proof-of-concept web application for laying out shapes extracted from segmented images.