Как разделить нерегулярный многоугольник на равные места на карте Google V2

Я разрабатываю приложение для отбора проб Glebe для целей сельского хозяйства. В том, что пользователь может выбрать Glebe, нажав на карту, которая создаст многоугольник в соответствии с количеством кранов. Я могу создать этот многоугольник и получить область многоугольника. Но теперь мне нужно разделить его на равные.

Например, если область многоугольника равна 50 м ^ 2, то она будет разделена на 50 областей 1 м ^ 2. Такая же функциональность была выполнена в Agri Precision App. Найдите ниже изображение. Мне нужно разделить многоугольник так же, как показано ниже, и показать точки внутри него.

Для получения области я использую Google Map Utilty Lib. У него есть algo также для Grid Clustering. Я хочу, как и выше. В приведенном выше изображении они разделяли площадь на 5 гектаров. Так как вся площадь составляет 85 гектаров, то должны быть показаны полные точки 17. Это то, как это работает.

Итак, мой вопрос:

Как найти эти точки в зависимости от области многоугольника на карте, чтобы я мог нарисовать эти точки на карте?

Ответ 1

Никаких ограничений на форму glebes не было, так что вот решение, которое выполнит постановку задачи, построив звездообразную декомпозицию. Предполагается, что многоугольник выпуклый:

Произвольно выберите основную вершину.
Триангулировать многоугольник, соединяя главную вершину с каждым ребром по очереди, давая треугольники с областями A1, A2, A3...
Начните путешествие вокруг многоугольника, из главной вершины. Если первый треугольник больше требуемой области (A1 > A), найдите точку вдоль края так, чтобы она разделила треугольник в субтреугольнике нужной области. Продолжайте путешествие отсюда с оставшимся треугольником (с областью A1-A). В противном случае вычтите площадь первого треугольника из нужной области и продолжите отключение (A now A-A1).

Это очень похоже на разделение последовательности интервалов N на вещественной прямой на интервалы K равной длины.

Я предполагаю, что разложение звездной формы вам не подходит.

Ответ 2

Если ваш многоугольник выпуклый, решение может быть получено путем решения следующей подзадачи: "Для выпуклого многоугольника области A найдите горизонтальную линию, которая разбивает ее на две части соответствующих областей B и AB".

Это легко сделать, сканируя вершины сверху вниз с движущейся горизонталью и вычисляя покрытую область (это образует разложение полигона на трапеции). В какой-то момент вы превысите область B. Линейной интерполяцией между текущей и предыдущей вершинами вы определите точную ординату горизонтали.

Вы будете использовать решение подзадачи следующим образом:

1) вычислить целочисленный квадратный корень, пусть N, числа нужных фрагментов, пусть M.

2) срезайте многоугольник N раз, каждый раз получая область N плит. Остается M-N ^ 2 плитки.

3) срезайте каждый кусочек, используя вертикали, чтобы выделить финальные плитки.

Плитки будут иметь гораздо более приемлемую форму (прямоугольники, если они не соответствуют какому-либо краю).