BSP: Finden aller Blätter in einer Region

DocJunioR

Also ich hab mir nen simplen bsp-baum gebastelt:

#ifndef CBSP_H_
#define CBSP_H_

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

class cBspNode {
    public:
        int         axis;
        bool        leaf; // true if it's a leaf, false if not
        double      lborder, rborder, posx, posy; // posx and posy describe this nodes center

        cBspNode    *top, *front, *back;

        /* Methods to be implemented*/
        /**
         * initial constructor
         * @param xmax width of the map
         * @param ymax height of the map
         */ 
        cBspNode         (double xmax, double ymax);

        /**
         * leaf constructor
         * @param root entry to sort this
         * @param xpos x-position of the leaf
         * @param ypos y-position of the leaf
         */ 
        cBspNode         (cBspNode *root, double xpos, double ypos);

        /**
         * constructor of the standard node
         * @param parent pointer to parent node
         */ 
        cBspNode         (cBspNode *parent);

        /**
         * destructor method
         */ 
        virtual ~cBspNode();

        /**
         * add the given Item to this tree
         * @param item item to be added
         */ 
        void addItem     (cBspNode *item);

        /**
         * add some new child nodes to this 
         * and add the given item after
         * @param item item do be added
         */ 
        void shiftLeaf   (cBspNode *item);

        /**
         * move leaf to new coordinates and 
         * reorganize it
         * @param x x difference
         * @param y y difference
         */ 
        void moveLeaf (double x, double y);

        /**
         * set leaf to new coordinates and 
         * reorganize it
         * @param x new x coordinate
         * @param y new y coordinate
         */ 
        void setLeaf (double x, double y);

        /**
         * checks if the given coordinates are inside 
         * this bounding box
         * @param x x coordinate
         * @param y y coordinate
         * @return true if coordinates are inside 
         * this node, otherwise false
         */ 
        bool testCoord (double x, double y);

        /**
         * just for testing -> prints tree to stdout
         */ 
        void print (void);

        /**
         * calculate this nodes center
         */ 
        void calcCenter(void); 
};

#endif /*CBSP_H_*/

Nun ist die Frage, wie ich am dümmsten alle Endknoten herausfinde, die innerhalb eines bestimmten dreieckigen, bzw. quadratischen Bereichs liegen.
Hab da momentan wohl ne geistige blockierung..

David_pb

Hi!

Die dümmste Möglichkeit? Ganz einfach:

Pseudocode:

for each node
  wenn im oder zum teil im bereich
    markieren

Der Test is ja einfach. Du könntest z.B. die Kanten des Dreiecks nehmen und das Skalarprodukt bilden! Das muss dann immer < 0 sein wenn alle Kanten nach aussen zeigen!

grüße

DocJunioR

hmm.. klar.
Wenn der Bereich zumindest teilweise im Knoten liegt, dann wird er angenommen. Am Ende bleiben dann nur noch die Blätter übrig, die innerhalb des Ganzen sind.

Manchmal denke ich einfach zu kompliziert...