Клуб API Карт

Как уменьшить количество вершин в полигоне?

Пост в архиве.
thekashey
10 марта 2010, 16:29

Несколько раз в данном клубе возникали вопросы о том как уменьшить колличество вершин в полигоне, чтобы он не тормозил.

Сам яндекс это умеет делать для полигонов загруженых через YMapsML и делает это автоматически.

Но никто никогда не расказывал как это сделать самому для полигонов созданых своими же ручками.


Основы

  1. Берем полигон, переводим его из координат в пиксели карты на заданом зуме.
  2. Производим упрошение полигона по фактически отображаемым данным,
  3. Переводим результат обратно в координаты,
  4. Отображаем, и не забываем радоваться.


Реализация

Создаем врапер над полигоном, который биндиться на ивенты изменения зума, чтобы каждый раз выбирать лучшее представление.


Алгоритм

 

  1. Берем отрезок полигона, точки 1,2,3 и 4.
  2. Будем считать что нам требуется убрать точку 2 и оставить точку 3.
  3. Оконечные точки 1 и 4 всегда будут.
  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. что кто-нибудь подскажет решение более элегантное и красивое :)

и будем считать это очередным началом моих опусов

 
11 комментариев
Я думаю, что ваш алгоритм пригодится кому-нибудь ;)

Однако, лучше учитывать, что при уменьшении детализации внешний вид не должен страдать. У вас получается на мелком масштабе круг превращается в треугольник.
установите дельтафактор в 1.
точнее в корень из двух.
в данном случае визуально всегда будет точное представление.

по дефолту дельта стоить в 20, что обозначает что "значимый" сдвиг должен быть около 20 пикселей.

а на мелком маштабе весь полигон меньше этого размера :)
Что-то не подумал поменять этот параметр...

delta factor: 1.4142135623730950488016887242097

Полигон немножко все равно не похож на себя, но в целом гораздо лучше)
polygon reduced from 1000 to 38
polygon reduced from 1000 to 20

Я подумаю. Возможно, что напишу в блог про другой вариант level of detail.
о! мой предсказаный пункт номер 3 :)
кстати - в первичной реализации был баг с нормированием верктора v1
он нормировался на квадрат своей длины.
сейчас поправил и стало работать еще лучше

dataset.push(dataset[L-1]); - по-моему тут доджно быть dataset.push(dataset[0]);

а то получается на последнем шаге проверяется предпоследняя и 2 раза последнии точки. А должно быть предпоследняя - последняя - первая

последная точка замыкается  сама на себя.


полигон же и так замкнут зам на себя.


приведеный алго работает также и просто на линии

Все, извиняюсь ) в куске кода приведенного здесь нету финальной части:

if(cur resultset.push(dataset[L-1]);

увидел его в скрипте)

Алгоритм Дугласа-Пекера хорош, но у него есть большой недостаток: в результате упрощения полигона могут возникнуть самопересечения границы.
Use convex hull изначально Люк!
А если мне надо не convex? Например граница региона такая?