WikiDer > Octree
EIN Octree ist ein Suchbaum für die Suche in a dreidimensional Platz. Jeder Taste (Englisch: Knoten) in diesem Baum stellt ein kubisches Volumen dar, das entweder Objekte enthält, die in diesem Würfel enthalten sind, oder wiederum acht Kindknoten. Diese untergeordneten Knoten enthalten zusammen denselben Platz wie der übergeordnete Knoten. Wenn Sie also wissen, dass der Bereich, den der übergeordnete Knoten einnimmt, nicht interessant ist, können Sie daraus schließen, dass auch die untergeordneten Knoten nicht interessant sind. Auf diese Weise können Sie schnell feststellen, welche Teile eines Raumes für einen bestimmten Betrieb interessant sind. Teile, die von der Bearbeitung nicht betroffen sind, können ignoriert werden.
Die 2-dimensionale Version eines Octrees ist a Quad-Baum. Es gibt auch ein Binärbaum und ein BSP-Baum.