Formen ziehen Problem

Question

Ich muss eine Software entwerfen, wo Benutzer Formen in ein Fenster ziehen kann. Das Problem besteht darin, dass es Tausende von Formen geben kann, und es könnte einige Einschränkungen geben, z. eine Form kann nicht über eine andere Form sein.

Also muss ich wirklich wissen, wie man Datenspeicher und einige Algorithmen organisiert, um schnell zu bestimmen, ob eine Form in einer bestimmten Position platziert werden kann. Ich denke, dieses Problem wurde viele Male gelöst, aber ich weiß nicht, wie man es richtig googelt. Könnten Sie mir bitte einige Informationen zu diesem Thema geben? Danke!

Answer 1

Ein Quadtree (2D, Octree wenn 3D) wird oft bei der Kollisionserkennung verwendet. Idee ist, den Raum rekursiv in Quadrate/Würfel zu teilen und die Formen in die richtigen Quadrate/Würfel zu setzen. Wenn Sie eine Kollisionserkennung für eine bestimmte Form durchführen müssen, können Sie nur die Formen in demselben Quadrat/Cube testen.

Es gibt andere Strukturen, die je nach den Einschränkungen, die Sie haben, Vor- und Nachteile haben. Wenn die anderen Formen statisch sind, können BSP-Bäume auch eine gute Struktur sein.