Алгоритм вычисления покрытия + перекрытия из набора дуг

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

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

Я хочу создать набор полигонов, которые показывают:
1) общую площадь, на которой получено удобрение
2) области перекрытия, т. Е. Где два отдельных прохода были слишком близко друг к другу, так что некоторые части фермы получали вдвое правильную «дозу» «Удобрений.

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

Если это уместно, я использую TatukGIS VCL DK, но я действительно ищу алгоритм, а не конкретное решение.

Некоторые пояснения в ответ на обсуждение до сих пор:

1) Я не могу полагаться на векторные данные, имеющие какие-либо конкретные метаданные (например, журналы GPS или скорость распространения). Я разрешаю пользователю выбрать слой и указать ширину разворота, после чего отчет запускается.

2) Цель отчета - показать пользователю, насколько «опытным» был оператор транспортного средства, где «опытный» означает «достиг самого высокого охвата с наименьшим перекрытием».

3) Я чувствую себя более комфортно на векторной земле, чем на растровой, поэтому предпочитаю векторные решения.

Спасибо,

Даррен.

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

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

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

Нет решения, но некоторые входные данные:

Эта проблема похожа на проблему обнаружения слияния линий при обобщении карты . Это происходит, когда большой стиль применяется к извилистой линии (символ перекрывается):

Этот документ стр. 176-180 (на французском языке ... извините) дает алгоритмы для обнаружения таких самопересекающихся частей. Принцип, как предлагает scw , заключается в использовании одностороннего буфера каждого сегмента, состоящего из сегмента плюс 0, 1 или 2 дуг окружности. JTS содержит реализацию этого одностороннего буфера, который может быть полезен.

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

Данные о времени будут доступны в GPS-записи прогресса трактора. Склоны (пройденное расстояние, деленное на прошедшее время) будут оценивать скорости в каждой точке. В качестве альтернативы можно (в качестве приближения) принять постоянную скорость внутри поля и более медленную скорость в пределах разумного внутреннего буфера границы поля.

Растровое представление может справиться с этими проблемами. Растеризуйте путь трактора. Это устанавливает все ячейки, не пересекаемые трактором, в значения NoData (или в ноль). Если бы трактор двигался со стандартной постоянной скоростью, было бы достаточно поместить постоянное значение в каждую ячейку данных. Теперь, например, если бы трактор двигался с удвоенной скоростью, (предположительно) его норма внесения снизилась бы вдвое, и это можно представить, вдвое уменьшив значение в ячейках.

Как правило, значение, которое нужно поместить в любую ячейку, представляет собой норму внесения на единицу площади . Если трактор равномерно разбрасывает x кг удобрений в секунду до 15 м с каждой стороны во время движения со скоростью у м / сек, то он разбрасывает х / у кг / с / [м / с] / (2 * 15 м) = х / (30 г ) , кг / м ^ 2 удобрения. Таким образом, x / (30 y ) - это значение для каждой ячейки. x дано, а y вычислено по данным GPS.

Самопересечения в принципе не проблема . Если путь трактора пересекает себя, добавляйте вклады каждый раз, когда он пересекает ячейку. Для этого может потребоваться специальная обработка, в зависимости от того, как создается сетка и от возможностей программного обеспечения ГИС.

Сделав эту подготовку, все остальное быстро и легко: фокусная сумма этой сетки, используя круговую окрестность с радиусом 15 м, находит совокупное количество, распределенное на единицу площади в каждой ячейке.

Я не уверен на 100% в протоколе StackExchange, поэтому я публикую это как ответ на мой вопрос. Это ответ, который я все равно использовал.

Основной алгоритм:
1. Разбейте любую геометрию слоя на сегменты, длина которых не превышает 1/2 ширины разброса.
2. Для каждого сегмента:
- создайте «скользящий буфер», оглядываясь назад по фигуре и буферизуя все предыдущие сегменты, где совокупная длина этих сегментов меньше ширины спреда (радиус буфера = 1/2 ширины спреда)
- Создать «буфер следующего сегмента» только следующего сегмента (радиус буфера = 1/2 ширины разброса)
- вычтите «скользящий буфер» из «буфера следующего сегмента», чтобы получить «новый буфер»
- объедините все «новый буфер» многоугольники вместе, чтобы получить один многоугольник на форму.

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

Спираль выглядит так, как будто я хочу: