quadtrees

if ( mouse_check_button_pressed ( mb_left ) )
{
    // remove point
    var i = 0; var rebuild = -1;
    for ( i = 0; i < instance_number ( obj_point ); i++ )
    {
        var o = instance_find ( obj_point, i );
        if ( point_distance ( mouse_x, mouse_y, o.x, o.y ) < 3 )
        {
            rebuild = o.parent;
            o.parent.children[ o.childid ] = 0;
            with ( o ) { instance_destroy ( ); }; break;
        }
    }
    // nothing to remove - add point
    if ( rebuild < 0 )
    {
        var o = instance_create ( mouse_x, mouse_y, obj_point );
        rebuild = o;
    }

    // add new point
    if ( rebuild.object_index != obj_quadtree )
    {
        var quad = root_quad;
        var child = 0;
        while ( true )
        {
            if      ( rebuild.x <= quad.x && rebuild.y <= quad.y ) child = 0;
            else if ( rebuild.x >  quad.x && rebuild.y <= quad.y ) child = 1;
            else if ( rebuild.x <= quad.x && rebuild.y >  quad.y ) child = 2;
            else if ( rebuild.x >  quad.x && rebuild.y >  quad.y ) child = 3;

            // the child is empty = reached the bottom - insert point, return
            if ( !instance_exists ( quad.children [ child ] ) )
            {
                quad.children[ child ] = rebuild;
                rebuild.parent = quad;
                rebuild.childid = child;
                break;
            }
            // the child is a quad - go deeper
            else if ( quad.children[ child ].object_index == obj_quadtree )
                quad = quad.children[ child ];
            // the child is a point - replace with quad, go deeper
            else
            {
                // save current point
                var o = quad.children[ child ];
                // create new quad in place of point
                var xq = quad.xs / 2; if ( child == 0 || child == 2 ) xq = -xq;
                var yq = quad.ys / 2; if ( child == 0 || child == 1 ) yq = -yq;
                var q = instance_create ( quad.x + xq, quad.y + yq, obj_quadtree );
                q.xs = abs ( xq ); q.ys = abs ( yq ); q.parent = quad; q.childid = child;
                quad.children[ child ] = q;

                // put point into new quad
                var c = 0;
                if      ( o.x <= q.x && o.y <= q.y ) c = 0;
                else if ( o.x >  q.x && o.y <= q.y ) c = 1;
                else if ( o.x <= q.x && o.y >  q.y ) c = 2;
                else if ( o.x >  q.x && o.y >  q.y ) c = 3;
                o.parent = q; o.childid = c;
                q.children [ c ] = o;
                // go deeper
                quad = q;
            }
        }
    }
    // remove leaf
    else
    {
        while ( true )
        {
            // root quad has to stay in place
            if ( rebuild == root_quad )
                break;

            // the quad has no children - detroy it
            if ( !instance_exists ( rebuild.children[ 0 ] ) &&
                 !instance_exists ( rebuild.children[ 1 ] ) &&
                 !instance_exists ( rebuild.children[ 2 ] ) &&
                 !instance_exists ( rebuild.children[ 3 ] ) )
            {
                var p = rebuild.parent;
                rebuild.parent.children[ rebuild.childid ] = 0;
                with ( rebuild ) { instance_destroy ( ); };
                // upper level quad now may have no children as well
                rebuild = p;
            }
            else
                break;
        }
    }
}