Monday 3 December 2012

TypeScript QuadTree part 3

This is the third part of my series on implementing a QuadTree in TypeScript, the first post can be found here and the second post can be found here. This posts focuses on starting to implement the QuadTree itself since the previous post addressed the prerequisites. As mentioned previously the pseudo code is from an example of a QuadTree found here. In this post have implemented a basic foundation that is capable of being constructed and sub-dived.


///
///

// Interfaces
interface IQuadTree {
    insert(quad: IQuad);
    queryRange(quad: IQuad);
}

// Class
class QuadTree implements IQuadTree {
    private minSize = 1;
    private contents: IQuadList;
    private topLeft: IQuadTree;
    private topRight: IQuadTree;
    private bottomLeft: IQuadTree;
    private bottomRight: IQuadTree;

    constructor (private quad: IQuad) {
        this.contents = new QuadList();
    }

    isSubdivided(): bool {
        return this.topLeft !== null;
    }

    subdivide() {
        this.topLeft = new QuadTree(this.getTopLeft());
        this.topRight = new QuadTree(this.getTopRight());
        this.bottomLeft = new QuadTree(this.getBottomLeft());
        this.bottomRight = new QuadTree(this.getBottomRight());
    }

    getTopLeft(): IQuad {
        var point = new Shapes.Point(this.quad.getLeft(), this.quad.getTop());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());

        return quad;
    }

    getTopRight(): IQuad {
        var point = new Shapes.Point(this.quad.getLeft() + this.quad.getHalfWidth(), this.quad.getTop());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());

        return quad;
    }

    getBottomLeft(): IQuad {
        var point = new Shapes.Point(this.quad.getLeft(), this.quad.getTop() + this.quad.getHalfHeight());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());

        return quad;
    }

    getBottomRight(): IQuad {
        var point = new Shapes.Point(this.quad.getLeft() + this.quad.getHalfWidth(),this. quad.getTop() + this.quad.getHalfHeight());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());

        return quad;
    }

    insert(quad: IQuad) {
        // To be implemented
    }

    queryRange(quad: IQuad) {
        // To be implemented
    }
}

Now I run tsc.exe over the TypeScipt and I get a whole bunch of JavaScript that isn't actually that different.

var QuadTree = (function () {
    function QuadTree(quad) {
        this.quad = quad;
        this.minSize = 1;
        this.contents = new QuadList();
    }
    QuadTree.prototype.isSubdivided = function () {
        return this.topLeft !== null;
    };
    QuadTree.prototype.subdivide = function () {
        this.topLeft = new QuadTree(this.getTopLeft());
        this.topRight = new QuadTree(this.getTopRight());
        this.bottomLeft = new QuadTree(this.getBottomLeft());
        this.bottomRight = new QuadTree(this.getBottomRight());
    };
    QuadTree.prototype.getTopLeft = function () {
        var point = new Shapes.Point(this.quad.getLeft(), this.quad.getTop());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());
        return quad;
    };
    QuadTree.prototype.getTopRight = function () {
        var point = new Shapes.Point(this.quad.getLeft() + this.quad.getHalfWidth(), this.quad.getTop());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());
        return quad;
    };
    QuadTree.prototype.getBottomLeft = function () {
        var point = new Shapes.Point(this.quad.getLeft(), this.quad.getTop() + this.quad.getHalfHeight());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());
        return quad;
    };
    QuadTree.prototype.getBottomRight = function () {
        var point = new Shapes.Point(this.quad.getLeft() + this.quad.getHalfWidth(), this.quad.getTop() + this.quad.getHalfHeight());
        var quad = new Shapes.Quad(point, quad.getHalfWidth(), quad.getHalfHeight());
        return quad;
    };
    QuadTree.prototype.insert = function (quad) {
    };
    QuadTree.prototype.queryRange = function (quad) {
    };
    return QuadTree;
})();

Now that we have got the basic class implemented my next post I will get down and dirty implementing the insert and queryRange methods.