ZFX + Developia

Code: Alles auswählen

regelmäßig:

        root
       /    \
     N1      N2
    /  \    /  \
  N11 N12 N21 N22
  
  
unregelmäßig:
      
        root
       /    \
     N1      N2
    /       /  \
  N11     N21 N22

Code: Alles auswählen

#nullable enable

using System;
using System.Collections.Generic;

namespace QuadtreeExample
{
    class Circle
    {
        public double mx = 0;
        public double my = 0;
        public double radius = 1;
    }

    class Quad
    {
        public double xpos = 0;
        public double ypos = 0;
        public double width = 0;
        public double height = 0;

        public Quad? parent = null;
        public Quad? q1 = null;
        public Quad? q2 = null;
        public Quad? q3 = null;
        public Quad? q4 = null;

        public List<Circle> circles = new List<Circle>();

        public bool HasChildren => q1 != null && q2 != null && q3 != null && q4 != null;

        public void GenerateChildren()
        {
            if (!HasChildren)
            {
                q1 = new Quad() { parent = this, xpos = this.xpos, ypos = this.ypos, width = this.width / 2, height = this.height / 2 };
                q2 = new Quad() { parent = this, xpos = this.xpos + this.width / 2, ypos = this.ypos, width = this.width / 2, height = this.height / 2 };
                q3 = new Quad() { parent = this, xpos = this.xpos, ypos = this.ypos + this.height / 2, width = this.width / 2, height = this.height / 2 };
                q4 = new Quad() { parent = this, xpos = this.xpos + this.width / 2, ypos = this.ypos + this.height / 2, width = 800, height = 800 };
            }
        }

        public bool IsCircleOverlappingThisQuad(Circle c)
        {
            bool xOverlap = c.mx + c.radius >= xpos && c.mx - c.radius < xpos + width;
            bool yOverlap = c.my + c.radius >= ypos && c.my - c.radius < ypos + height;
            return xOverlap && yOverlap;
        }

        public void AddCircle(Circle c)
        {
            if (IsCircleOverlappingThisQuad(c))
            {
                if (HasChildren)
                {
                    q1?.AddCircle(c);
                    q2?.AddCircle(c);
                    q3?.AddCircle(c);
                    q4?.AddCircle(c);
                }
                else
                {
                    circles.Add(c);
                }
            }
        }

        public void GetCollisionCandidates(Circle circle, SortedSet<Circle> collisionCandidates)
        {
            if (IsCircleOverlappingThisQuad(circle))
            {
                if (HasChildren)
                {
                    q1?.GetCollisionCandidates(circle, collisionCandidates);
                    q2?.GetCollisionCandidates(circle, collisionCandidates);
                    q3?.GetCollisionCandidates(circle, collisionCandidates);
                    q4?.GetCollisionCandidates(circle, collisionCandidates);
                }
                else
                {
                    foreach (var c in circles)
                    {
                        collisionCandidates.Add(c);
                    }
                }
            }
        }
    }

    class MainClass
    {
        static void Main(string[] args)
        {
            //test1
            {
                var root = new Quad() { xpos = 0, ypos = 0, width = 1600, height = 1600 };
                root.GenerateChildren();
                var circleForTheQuadtree = new Circle() { mx = 1000, my = 200, radius = 150 };
                root.AddCircle(circleForTheQuadtree);

                var circleForCollisionDetection = new Circle() { mx = 200, my = 200, radius = 300 };
                var collisionCandidates = new SortedSet<Circle>();
                root.GetCollisionCandidates(circleForCollisionDetection, collisionCandidates);
            }
            //test2
            {
                var root = new Quad() { xpos = 0, ypos = 0, width = 1600, height = 1600 };
                root.GenerateChildren();
                var circleForTheQuadtree = new Circle() { mx = 850, my = 200, radius = 150 };
                root.AddCircle(circleForTheQuadtree);

                var circleForCollisionDetection = new Circle() { mx = 600, my = 200, radius = 300 };
                var collisionCandidates = new SortedSet<Circle>();
                root.GetCollisionCandidates(circleForCollisionDetection, collisionCandidates);
            }

            return;
        }
    }
}

Code: Alles auswählen

1-------------+
|+-----+-----+|
||  2  |  3  ||
||     |     ||
|+-----+-----+|
||  4  |  5  ||
||     |     ||
|+-----+-----+|
+-------------+