Получить ограничительную коробку с полигоном

Question

У меня много сложных многоугольников с 750 + точками. Есть ли быстрый и эффективный способ получить ограничительную коробку? Мне не хотелось бы перебирать каждую точку и расширять ограничительную рамку.

Решение должно быть в javascript или, возможно, есть функция Google Maps API v3, которую я пропустил.

---

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

Как многоугольники сделаны:

//Coordinates 
var coordinates = [ 
    new google.maps.LatLng(11,22), 
    new google.maps.LatLng(11,22), 
    new google.maps.LatLng(11,22), 

    //etc up to 200, 500 or even 800 points 
] 

//Options 
var options = { 
    path: coordinates, 
    strokeColor: "#222", 
    strokeOpacity: 1, 
    strokeWeight: 2, 
    fillColor: "#000", 
    fillOpacity: 0, 
    zIndex: 0 
} 

//Create polygon 
var polygon = new google.maps.Polygon(options); 

//Show it on map 
polygon.setMap(map); 

мне нужно сделать свою домашнюю работу, потому что живые расчеты исключены точно. Мне, вероятно, придется сделать это нелегко, но может быть, некоторые из вас знают какой-нибудь удобный онлайн-инструмент, который вычисляет граничную рамку на основе вставленных коордов?

Мне нужна как можно более простая форма, потому что мне нужно проверить, находится ли мой многоугольник в видовом экране, и, вероятно, это будет кошмар с 800 очками, потому что я не знаю другого пути, кроме прокрутки всех точек.

Answer 1

Polygon не имеет способа getBounds в API Карт Google v3. Вы можете реализовать его вручную. Но в нем есть fors. Кстати. Я применил метод getBounds. Это жестко закодированная версия. Ссылка для demo.

UPDATE

Чтобы получить единую границу окна для нескольких полигонов используют union метод getBounds метода.

var coordinates = [ 
    new google.maps.LatLng(10,15), 
    new google.maps.LatLng(12,16), 
    new google.maps.LatLng(11,18), 
    new google.maps.LatLng(11,19), 
    new google.maps.LatLng(13,21), 
    new google.maps.LatLng(12,22), 
    new google.maps.LatLng(13,24), 
    new google.maps.LatLng(11,25), 
    new google.maps.LatLng(8,23), 
    new google.maps.LatLng(7,23), 
    new google.maps.LatLng(8,21), 
    new google.maps.LatLng(6,17), 
    new google.maps.LatLng(9,16) 
] 

var coordinates_1 = [ 
    new google.maps.LatLng(15,28), 
    new google.maps.LatLng(16,30), 
    new google.maps.LatLng(17,30), 
    new google.maps.LatLng(16,31), 
    new google.maps.LatLng(16,32), 
    new google.maps.LatLng(14,29), 
] 

var options = { 
    path: coordinates, 
    strokeColor: "#222", 
    strokeOpacity: 1, 
    strokeWeight: 2, 
    fillColor: "#000", 
    fillOpacity: 0, 
    zIndex: 0, 
    map: map 
} 

var options_1 = { 
    path: coordinates_1, 
    strokeColor: "#222", 
    strokeOpacity: 1, 
    strokeWeight: 2, 
    fillColor: "#000", 
    fillOpacity: 0, 
    zIndex: 0 
} 

var polygon = new google.maps.Polygon(options); 
var polygon_1 = new google.maps.Polygon(options_1); 

if(!google.maps.Polygon.prototype.getBounds) 
google.maps.Polygon.prototype.getBounds = function() { 
    var bounds = new google.maps.LatLngBounds(); 
    var paths = this.getPaths();  
    for (var i = 0; i < paths.getLength(); i++) { 
     var path = paths.getAt(i); 
     for (var j = 0; j < path.getLength(); j++) { 
      bounds.extend(path.getAt(j)); 
     } 
    } 
    return bounds; 
} 

var rectangle = new google.maps.Rectangle({ 
    strokeColor: '#FF0000', 
    strokeOpacity: 0.8, 
    strokeWeight: 2, 
    fillColor: '#FF0000', 
    fillOpacity: 0.35, 
    map: map, 
    bounds: polygon.getBounds() 
    }); 

var rectangle_1 = new google.maps.Rectangle({ 
    strokeColor: '#FF0000', 
    strokeOpacity: 0.8, 
    strokeWeight: 2, 
    fillColor: '#FF0000', 
    fillOpacity: 0.35, 
    map: map, 
    bounds: polygon_1.getBounds() 
    }); 

var rectangle_single = new google.maps.Rectangle({ 
    strokeColor: '#FFC000', 
    strokeOpacity: 0.8, 
    strokeWeight: 2, 
    fillColor: '#FFF000', 
    fillOpacity: 0.35, 
    map: map, 
    bounds: polygon.getBounds().union(polygon_1.getBounds()) 
    }); 

Answer 2

Координаты X и Y в массиве, тогда x и y array min и max. Хотя нам нужно больше, чем картина, чтобы узнать, что именно вы хотите и как.

Answer 3

Если точки заданы Мы отсутствие априори структуры, нет не более эффективным способом, чем итерация точек и расширение ограничивающего параллелепипеда. Поскольку вы ничего не знаете заранее, любая точка может быть угловой точкой (или краевой точкой), и поэтому вы должны принять это во внимание. Ни один алгоритм не может сделать это более эффективно.

Если, однако, у вас есть контроль над сервером, который предоставляет координаты, вы можете заранее сохранить точки в виде данных, например, k-d tree. Скажем, например, все точки являются статическими, вы можете хранить их в таком дереве kd, а затем вы можете defintely ускорить все (хотя, насколько я знаю, проблема по-прежнему O (n), но у вас нет учитывать все моменты).

Проблема, однако, в том, что вы не предоставляете никакой информации о стороне сервера.

Answer 4

Более простой и компактный вариант кода:

google.maps.Polygon.prototype.getBounds = function() { 
     var bounds = new google.maps.LatLngBounds(); 
     this.getPath().forEach(function(element,index){ bounds.extend(element); }); 
     return bounds; 
    }