Как отобрать 2D полигон?

Question

У меня есть многоугольники, которые определяют контур округов в Великобритании.Эти фигуры очень детализированы (от 10 до 20 тысяч точек каждая), что делает связанные с этим вычисления (является ли точка X в многоугольнике P?) Довольно вычислительно дорогими.

Таким образом, я хотел бы «отбирать» мои многоугольники, чтобыполучить похожую форму, но с меньшим количеством очков.Какие существуют разные методы для этого?

Тривиально было бы брать один балл каждые N баллов (таким образом, используя подвыборку с коэффициентом N), но это кажется слишком "грубым".Я бы предпочел сделать усреднение баллов или что-то в этом роде.Есть указатель?

Answer 1

На ум приходят два решения:

1) поскольку карта Великобритании достаточно квадратная, вы можете выбрать рендеринг с графствами. Присвойте каждому определенный цвет, а затем визуализируйте границы с помощью черной линии толщиной 1 или 2 пикселя. Это означает, что вам придется выполнять дорогостоящий расчет интерьера / экстерьера только в том случае, если образец окажется на границе. Чем больше растровое изображение, тем реже это происходит.

2) упростить планы округа. Вы можете использовать рекурсивный алгоритм Ramer – Douglas – Peucker для рекурсивного упрощения границ. Просто убедитесь, что вы кешируете результаты. Вам может также придется решить эту проблему не для границ всего округа, а только для общих границ, чтобы не было пропусков. Это может быть довольно сложно.

Answer 2

Здесь вы можете найти проект, касающийся именно ваших проблем.Хотя он в основном работает с областью, «заполненной» точками, вы можете настроить его для работы с определением типа «периметр», как у вас.

Он использует подход k-ближайших соседей для расчета региона.

Образцы:

Здесь Вы можете запросить копию статьи,

Похоже, они планировали предложить онлайн-сервис для запроса расчетов, но я не проверял его и, вероятно, он не работает.

НТН!

Answer 3

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

Поскольку у вас есть все алгоритмы, которые вам нужны для полигонов, не только для треугольников, вы также можете объединить несколько слишком маленьких треугольников после триангуляции или, если количество треугольников становится слишком большим.