JavaScript: Построение выпуклого многоугольника по конечному однородному множеству точек

Построение многоугольника будет производиться алгоритмом QuickHull. Код можно брать и использовать. Я его проверял на массивах до 30000 точек, не лагало. Если найдете баги, пишите в коменты.

// Построение выпуклого многоугольника по массиву однородных точек
function Point() {
    this.x = 0;
    this.y = 0;
}

Point.prototype.init_by_building = function (building) {
    this.x = building.lng;
    this.y = building.lat;

    return this;
}

Point.prototype.init = function (x, y) {
    this.x = x;
    this.y = y;

    return this;
}

// Отрезок
function Line(x1, y1, x2, y2) {
    this.start = new Point().init(x1, y1);
    this.end = new Point().init(x2, y2);

    // Расчет дистанции до точки
    this.distanceToPoint = function (point) {
        var Vy = this.end.x - this.start.x;
        var Vx = this.start.y - this.end.y;

        return Vx * (point.x - this.start.x) + Vy * (point.y - this.start.y);
    };

    this.findMostDistantPoint = function (points) {
        var max_dist = 0;
        var max_point = null;
        var new_points = [];

        for (var idx in points) {
            var pt = points[idx];
            var d = this.distanceToPoint(pt);

            if (d > 0) new_points.push(pt);
            else continue;

            if (d > max_dist) {
                max_dist = d;
                max_point = pt;
            }
        }

        return {'maxPoint':max_point, 'newPoints':new_points}
    };
}

function QuickHull(points) {
    this.points = points;

    this.all_lines = [];

    this._getBaseLine = function () {
        var max_x = -10000;
        var min_x = 10000;
        var max_point, min_point;

        for (var idx in points) {
            var pt = points[idx];
            if (pt.x > max_x) {
                max_point = pt;
                max_x = pt.x;
            }

            if (pt.x < min_x) {
                min_point = pt;
                min_x = pt.x;
            }
        }

        return new Line(min_point.x, min_point.y, max_point.x, max_point.y);
    };

    this._buildConvexHull = function(line, points) {
        this.all_lines.push(line);

        var convex_hull_base_lines = [];

        var t = line.findMostDistantPoint(points);

        // Если есть точка за пределами линии
        if (t.maxPoint != null) {
            var pt = t.maxPoint;
            convex_hull_base_lines = convex_hull_base_lines.concat(this._buildConvexHull(new Line(line.start.x, line.start.y, pt.x, pt.y), t.newPoints));
            convex_hull_base_lines = convex_hull_base_lines.concat(this._buildConvexHull(new Line(pt.x, pt.y, line.end.x, line.end.y), t.newPoints));

            return convex_hull_base_lines;
        }
        else { return [line]; }// Нет точки за пределами линии
    };


    this.Start = function () {
        var base_line = this._getBaseLine();

        return [].concat(this._buildConvexHull(base_line, this.points), this._buildConvexHull(new Line(base_line.end.x, base_line.end.y, base_line.start.x, base_line.start.y), this.points));
    };
}

Как использовать:

var qh = new QuickHull(points);
var cvx_lines = qh.Start();

Необходимо передать массив точек в конструктор QuickHull. Я использовал алгоритм для построения полигона на карте, поэтому у меня в объекте Point два конструктора: init_by_building, куда передается объект здания, который в свою очередь имеет свойства lat (широта) и lng (долгота); и init, куда передются координаты x и y точки.
После выполнения в массиве cvx_lines будут содержаться объекты типа Line, которые формируют многоугольник.