| dbo:abstract
|
- En informàtica, un Quadtree (o arbre quaternari) és un tipus d'arbre d'estructura de dades utilitzat en sistemes de simulació de partícules. La seva funció és reduir el cost computacional requerit al comprovar en tot moment i per cada partícula la posició de totes les altres partícules de la graella. Per fer-ho, l'algorisme divideix la graella en quatre regions o quadrants rectangulars (tot i que existeixen variants amb altres quantitats i mides) i cadascuna de les regions és tractada com una graella sencera, de manera recursiva, fins a assolir el nombre de partícules màxim per quadrant que busquem. D'aquesta manera, per cada partícula llavors es comprova la posició de les partícules d'aquell quadrant i no de tota la graella, estalviant així la part més feixuga de la computació. El seu cost computacional és O(n log n) on n és el nombre total de partícules, mentre que sense l'algorisme el cost és d'O(n²), molt més elevat. (ca)
- Ein Quadtree oder Quaternärbaum ist in der Informatik eine Baumstruktur, in der jeder innere Knoten genau vier Kindknoten hat. Quadtrees werden hauptsächlich zur Unterteilung eines zweidimensionalen Raumes genutzt, indem rekursiv in vier Bereiche (Quadranten) unterteilt wird. Die Bereiche können quadratisch oder rechteckig sein oder beliebige Formen haben. Eine ähnliche Aufteilung ist als Q-tree bekannt. Alle Formen von Quadtrees teilen bestimmte Merkmale:
* Sie zerlegen den Raum in anpassbare Bereiche
* Jeder Bereich hat eine Maximalkapazität. Wird diese erreicht, so wird der Bereich unterteilt.
* Das Baumverzeichnis folgt der räumlichen Unterteilung des Quadtrees. (de)
- Un quadtree ou arbre quaternaire (arbre Q) est une structure de données de type arbre dans laquelle chaque nœud a quatre fils. Les quadtrees sont le plus souvent utilisés pour partitionner un espace bidimensionnel en le subdivisant récursivement en quatre nœuds. Les quadtrees sont l'analogie bidimensionnelle des octrees. Le nom est formé à partir de quad et de tree (arbre, en anglais). Chaque nœud d'un quadtree subdivise l'espace qu'il représente en quatre sous-espaces. (fr)
- El término Quadtree, o árbol cuaternario, se utiliza para describir clases de estructuras de datos jerárquicas cuya propiedad común es que están basados en el principio de descomposición recursiva del espacio. En un QuadTree de puntos, el centro de una subdivisión está siempre en un punto. Al insertar un nuevo elemento, el espacio queda divido en cuatro. Al repetir el proceso, el cuadrante se divide de nuevo en cuatro, y así sucesivamente. Una gran variedad de estructuras jerárquicas existen para representar los datos espaciales. Una técnica normalmente usada es Quadtree. El desarrollo de estos fue motivado por la necesidad de guardar datos que se insertan con valores idénticos o similares. Este artículo trata de la representación de datos en el espacio bidimensional. Quadtree también se usa para la representación de datos en los espacios tridimensionales o con hasta 'n' dimensiones. El término Quadtree se usa para describir una clase de estructuras jerárquicas cuya propiedad en común es el principio de recursividad de descomposición del espacio. Estas clases, basan su diferencia en los requisitos siguientes: 1.
* El tipo del dato en que ellas actúan. 2.
* El principio que las guías del proceso de descomposición. 3.
* La resolución (inconstante o ninguna). La familia Quadtree se usa para representar puntos, áreas, curvas, superficies y volúmenes. La descomposición puede hacerse en las mismas partes en cada nivelado (la descomposición regular), o puede depender de los datos de la entrada. La resolución de la descomposición, en otros términos, el número de tiempos en que el proceso de descomposición es aplicado, puede tratarse de antemano, o puede depender de las propiedades de los datos de la entrada. El primer ejemplo de un Quadtree se relaciona a la representación de un área bidimensional. La región Quadtree que representa las áreas es el tipo más estudiado. Este ejemplo es basado en la subdivisión sucesiva del espacio en cuatro cuadrantes del mismo tamaño. El subcuadrante que contiene datos simplemente se denomina área Negra, y los que no contienen datos se denominan área Blanca. Un subcuadrante que contiene partes de ambos se denomina área Ceniza. Los subcuadrantes Ceniza, que contienen aéreas Blancas y Negras (Vacío y Datos), deben subdividirse sucesivamente hasta que solo queden cuadrantes Negros Y Blancos... (Datos y Vacíos). Cada cuadrante representa un nodo del Quadtree, los espacios negros y blancos siempre están en las hojas, mientras todos los nodos interiores representan los espacios grises. (es)
- A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a "unit of interesting spatial information". The subdivided regions may be square or rectangular, or may have arbitrary shapes. This data structure was named a quadtree by Raphael Finkel and J.L. Bentley in 1974. A similar partitioning is also known as a Q-tree. All forms of quadtrees share some common features:
* They decompose space into adaptable cells
* Each cell (or bucket) has a maximum capacity. When maximum capacity is reached, the bucket splits
* The tree directory follows the spatial decomposition of the quadtree. A tree-pyramid (T-pyramid) is a "complete" tree; every node of the T-pyramid has four child nodes except leaf nodes; all leaves are on the same level, the level that corresponds to individual pixels in the image. The data in a tree-pyramid can be stored compactly in an array as an implicit data structure similar to the way a complete binary tree can be stored compactly in an array. (en)
- Un albero quadramentale, spesso indicato con il termine inglese "quadtree", è una struttura dati ad albero non bilanciata nella quale tutti i nodi interni hanno esattamente quattro nodi figli. I quadtree sono spesso usati per partizionare uno spazio bidimensionale suddividendolo ricorsivamente in quattro quadranti, comunemente denotati come Nord-Est, Nord-Ovest, Sud-Est, Sud-Ovest. Utilizzi comuni di questo tipo di strutture sono i seguenti:
* Rappresentazione di immagini;
* Indicizzazione spaziale;
* in due dimensioni;
* Memorizzazione di dati sparsi, come la memorizzazione di informazioni di formattazione per un foglio elettronico o per calcoli su matrici. I alberi quadramentali sono i corrispondenti in due dimensione degli alberi ottali (chiamati anche "octree") . I quadtree sono strutture dati ad albero in cui l'immagine è divisa in 4 quadranti; procedendo in senso orario e partendo da quello in alto a sinistra, per ogni quadrante si controlla se è uniforme: se non lo è si ripete il procedimento per quel quadrante fino al raggiungimento di zone uniformi (al massimo si arriva al singolo pixel). (it)
- 四分木（しぶんぎ、英: Quadtree）は、各内部ノードが4個までの子ノードを持つ木構造のデータ構造である。四分木は主に、2次元空間を再帰的に4つの象限または領域に分割するのに使われる。領域は四角形または矩形の場合もあるし、任意の形状の場合もある。このデータ構造は1974年、Raphael Finkel と J.L. Bentley が四分木と名づけた。同様の分割手法はQ木 (Q-tree) とも呼ばれている。四分木に共通する特徴は以下の通りである。
* 空間を適応可能セルに分割する。
* 各セル（またはバケット）は容量の上限がある。容量が最大に達すると、バケットは分割される。
* 木構造ディレクトリは四分木の空間分割に従う。 (ja)
- Drzewo czwórkowe (ang. quadtree) – struktura danych będąca drzewem, używana do podziału dwuwymiarowej przestrzeni na mniejsze części, dzieląc ją na cztery równe ćwiartki, a następnie każdą z tych ćwiartek na cztery kolejne itd. Jest używana na przykład w procesie wykrywania kolizji w dwóch wymiarach. Umożliwia szybkie odrzucenie dużych przestrzeni – gdy zostanie stwierdzone, że któraś ćwiartka nie ma kolizji z danym obiektem, jej podćwiartki też nie mają z nim kolizji. Drzewa czwórkowe znalazły również zastosowanie w kompresji bitmap dwukolorowych (czarno-białych), gdzie obraz dzielony jest na mniejsze części dopóki nie będą one jednokolorowe, a wtedy wystarczy tylko zapisać kolor tego kwadratu, na co wystarcza pojedynczy bit. Trójwymiarowym odpowiednikiem drzew czwórkowych są drzewa ósemkowe. (pl)
- Дерево квадрантів (також квадродерево, 4-дерево, англ. quadtree) — дерево, в якому у кожного внутрішнього вузла рівно чотири нащадки. Дерева квадрантів можуть використовуватися для рекурсивного розбиття двовимірного простору по 4 квадранти (області). Області представляють собою квадрати, прямокутники або мають довільну форму. Англомовний термін quadtree був придуманий і в 1974 році. Аналогічне розділення простору відомо як Q-дерево. Загальні риси різних видів дерев квадрантів:
* розбиття простору на адаптивні секції (англ. adaptable cells)
* максимальний розмір кожної секції
* відповідність напряму дерева просторому розподіленню. Дерево-піраміда (англ. tree-pyramid, T-pyramid) це "повне" дерево; кожна вершина Д-піраміди має чотири дитини, окрім вершин-листів; усі листи знаходяться на одному рівні, де рівень відповідає за характерний піксель на зображенні. Дані в дереві-піраміді можна компактно зберігати в масиві як неявну структуру даних подібно до того, як повне двійкове дерево може бути компактно збережене в масиві. (uk)
- Дерево квадрантов (также квадродерево, 4-дерево, англ. quadtree) — дерево, в котором у каждого внутреннего узла ровно 4 потомка. Деревья квадрантов часто используются для рекурсивного разбиения двухмерного пространства по 4 квадранта (области). Области представляют собой квадраты, прямоугольники или имеют произвольную форму. Англоязычный термин quadtree был придуман Рафаэлем Финкелем и Джоном Бентли в 1974 году. Аналогичное разбиение пространства известно как Q-дерево. Общие черты разных видов деревьев квадрантов:
* разбиение пространства на адаптирующиеся ячейки (англ. adaptable cells),
* максимально возможный объём каждой ячейки,
* соответствие направления дерева пространственному разбиению. (ru)
- 四元樹是一種樹狀資料結構，在每一個節點上會有四個子區塊。四元樹常應用於二維空間資料的分析與分類。 它將資料區分成為四個象限。資料範圍可以是方形或矩形或其他任意形狀。這種資料結構是由 (Raphael Finkel) 與 在1974年發展出來 。 類似的資料分割方法也稱為 Q-tree。 所有的四元樹法有共同之特點:
* 可分解成為各自的區塊
* 每个区块都有节点容量。当节点达到最大容量时，节点分裂
* 樹狀資料結構依造四元樹法加以區分 (zh)
|
| rdfs:comment
|
- Un quadtree ou arbre quaternaire (arbre Q) est une structure de données de type arbre dans laquelle chaque nœud a quatre fils. Les quadtrees sont le plus souvent utilisés pour partitionner un espace bidimensionnel en le subdivisant récursivement en quatre nœuds. Les quadtrees sont l'analogie bidimensionnelle des octrees. Le nom est formé à partir de quad et de tree (arbre, en anglais). Chaque nœud d'un quadtree subdivise l'espace qu'il représente en quatre sous-espaces. (fr)
- 四分木（しぶんぎ、英: Quadtree）は、各内部ノードが4個までの子ノードを持つ木構造のデータ構造である。四分木は主に、2次元空間を再帰的に4つの象限または領域に分割するのに使われる。領域は四角形または矩形の場合もあるし、任意の形状の場合もある。このデータ構造は1974年、Raphael Finkel と J.L. Bentley が四分木と名づけた。同様の分割手法はQ木 (Q-tree) とも呼ばれている。四分木に共通する特徴は以下の通りである。
* 空間を適応可能セルに分割する。
* 各セル（またはバケット）は容量の上限がある。容量が最大に達すると、バケットは分割される。
* 木構造ディレクトリは四分木の空間分割に従う。 (ja)
- 四元樹是一種樹狀資料結構，在每一個節點上會有四個子區塊。四元樹常應用於二維空間資料的分析與分類。 它將資料區分成為四個象限。資料範圍可以是方形或矩形或其他任意形狀。這種資料結構是由 (Raphael Finkel) 與 在1974年發展出來 。 類似的資料分割方法也稱為 Q-tree。 所有的四元樹法有共同之特點:
* 可分解成為各自的區塊
* 每个区块都有节点容量。当节点达到最大容量时，节点分裂
* 樹狀資料結構依造四元樹法加以區分 (zh)
- En informàtica, un Quadtree (o arbre quaternari) és un tipus d'arbre d'estructura de dades utilitzat en sistemes de simulació de partícules. La seva funció és reduir el cost computacional requerit al comprovar en tot moment i per cada partícula la posició de totes les altres partícules de la graella. Per fer-ho, l'algorisme divideix la graella en quatre regions o quadrants rectangulars (tot i que existeixen variants amb altres quantitats i mides) i cadascuna de les regions és tractada com una graella sencera, de manera recursiva, fins a assolir el nombre de partícules màxim per quadrant que busquem. D'aquesta manera, per cada partícula llavors es comprova la posició de les partícules d'aquell quadrant i no de tota la graella, estalviant així la part més feixuga de la computació. El seu cos (ca)
- Ein Quadtree oder Quaternärbaum ist in der Informatik eine Baumstruktur, in der jeder innere Knoten genau vier Kindknoten hat. Quadtrees werden hauptsächlich zur Unterteilung eines zweidimensionalen Raumes genutzt, indem rekursiv in vier Bereiche (Quadranten) unterteilt wird. Die Bereiche können quadratisch oder rechteckig sein oder beliebige Formen haben. Eine ähnliche Aufteilung ist als Q-tree bekannt. Alle Formen von Quadtrees teilen bestimmte Merkmale: (de)
- El término Quadtree, o árbol cuaternario, se utiliza para describir clases de estructuras de datos jerárquicas cuya propiedad común es que están basados en el principio de descomposición recursiva del espacio. En un QuadTree de puntos, el centro de una subdivisión está siempre en un punto. Al insertar un nuevo elemento, el espacio queda divido en cuatro. Al repetir el proceso, el cuadrante se divide de nuevo en cuatro, y así sucesivamente. Estas clases, basan su diferencia en los requisitos siguientes: (es)
- A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a "unit of interesting spatial information". (en)
- Un albero quadramentale, spesso indicato con il termine inglese "quadtree", è una struttura dati ad albero non bilanciata nella quale tutti i nodi interni hanno esattamente quattro nodi figli. I quadtree sono spesso usati per partizionare uno spazio bidimensionale suddividendolo ricorsivamente in quattro quadranti, comunemente denotati come Nord-Est, Nord-Ovest, Sud-Est, Sud-Ovest. Utilizzi comuni di questo tipo di strutture sono i seguenti: I alberi quadramentali sono i corrispondenti in due dimensione degli alberi ottali (chiamati anche "octree") . (it)
- Drzewo czwórkowe (ang. quadtree) – struktura danych będąca drzewem, używana do podziału dwuwymiarowej przestrzeni na mniejsze części, dzieląc ją na cztery równe ćwiartki, a następnie każdą z tych ćwiartek na cztery kolejne itd. Trójwymiarowym odpowiednikiem drzew czwórkowych są drzewa ósemkowe. (pl)
- Дерево квадрантов (также квадродерево, 4-дерево, англ. quadtree) — дерево, в котором у каждого внутреннего узла ровно 4 потомка. Деревья квадрантов часто используются для рекурсивного разбиения двухмерного пространства по 4 квадранта (области). Области представляют собой квадраты, прямоугольники или имеют произвольную форму. Англоязычный термин quadtree был придуман Рафаэлем Финкелем и Джоном Бентли в 1974 году. Аналогичное разбиение пространства известно как Q-дерево. Общие черты разных видов деревьев квадрантов: (ru)
- Дерево квадрантів (також квадродерево, 4-дерево, англ. quadtree) — дерево, в якому у кожного внутрішнього вузла рівно чотири нащадки. Дерева квадрантів можуть використовуватися для рекурсивного розбиття двовимірного простору по 4 квадранти (області). Області представляють собою квадрати, прямокутники або мають довільну форму. Англомовний термін quadtree був придуманий і в 1974 році. Аналогічне розділення простору відомо як Q-дерево. Загальні риси різних видів дерев квадрантів: (uk)
|