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