Построение многоугольника будет производиться алгоритмом 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, которые формируют многоугольник.
крутяк!
ОтветитьУдалить