Несколько раз в данном клубе возникали вопросы о том как уменьшить колличество вершин в полигоне, чтобы он не тормозил.
Сам яндекс это умеет делать для полигонов загруженых через YMapsML и делает это автоматически.
Но никто никогда не расказывал как это сделать самому для полигонов созданых своими же ручками.
Основы
- Берем полигон, переводим его из координат в пиксели карты на заданом зуме.
- Производим упрошение полигона по фактически отображаемым данным,
- Переводим результат обратно в координаты,
- Отображаем, и не забываем радоваться.
Реализация
Создаем врапер над полигоном, который биндиться на ивенты изменения зума, чтобы каждый раз выбирать лучшее представление.
Алгоритм
- Берем отрезок полигона, точки 1,2,3 и 4.
- Будем считать что нам требуется убрать точку 2 и оставить точку 3.
- Оконечные точки 1 и 4 всегда будут.
- Требуется построить вектора из точки 1 в точку 2, из 1 в 3, высчитать растояние от точки 2 до прямой 1-3.
Если это расстояние меньше некой дельты, мы считаем что данная точка не обеспечивает "значимый" сдвиг и мы ее выкидываем.
Если посмотреть на картинку и произвести операции для 1-3, 1-4 можно увидеть что для нее перпендикуляр p будет сильно более значим чем для пары 1-2-3
Это и даст нам право оставить данную точку..
Код данного алгоритма:
var resultset=[];
var L=dataset.length;
resultset.push(dataset[0]);
dataset.push(dataset[L-1]);
var cur=0;
var j=0;
for(j=1;j<L;j++)
{
var x1=dataset[cur].x;
var y1=dataset[cur].y;
var x2=dataset[j ].x;
var y2=dataset[j ].y;
var x3=dataset[j+1].x;
var y3=dataset[j+1].y;
//first points must be different in screen space
if(!(((Math.round(x1)==Math.round(x2)) && (Math.round(y1)==Math.round(y2))) ||
((Math.round(x2)==Math.round(x3)) && (Math.round(y2)==Math.round(y3)))))
{
/*
goal - create two vectors -
from current to test point
and from current to next point
we need to drop a perpendicular from test point to cur-last vector
just simple mathematics
*/
var vx1=x2-x1;
var vy1=y2-y1;
var len=(vy1*vy1+vx1*vx1);
var v1=this._norm(vx1,vy1,len);
var vx2=x3-x1;
var vy2=y3-y1;
var v2=this._norm(vx2,vy2);
var dot=this._dot(v1,v2);
var sa=Math.sin(Math.acos(dot));
var perp=sa*len;
//so if perpendicular is bigger than delta, and length of vector is bigger than delta
//add point to result set
if(Math.abs(perp)>=delta && len>=delta)
{
cur=j;
resultset.push(dataset[j]);
}
}
}
Живой пример упрощения полигона, но на гугл картах
Сам скрипт , хоть скрипт создан для гугл карт, он создан таким образом что только в двух местах оперирует с ней( класс CoordinateMapper,создание GPolygon и add/remove Overlay )
Я надеюсь на две веши.
1. что местные начальники не будут сильно ругаться на пример с гугл картами, тут же главное принципы
2. что это комунибудь будет полезно
3. что кто-нибудь подскажет решение более элегантное и красивое :)
и будем считать это очередным началом моих опусов