Как отобрать 2D полигон?
У меня есть многоугольники, которые определяют контур округов в Великобритании. Эти фигуры очень детализированы (от 10 до 20 тысяч точек каждая), что делает соответствующие вычисления (точка X в многоугольнике P?) Довольно вычислительно дорогими.
Таким образом, я хотел бы "отбирать" мои полигоны, чтобы получить похожую форму, но с меньшим количеством точек. Какие существуют разные техники для этого?
Тривиальным было бы взять один каждый N баллы (таким образом, подвыбор N), но это кажется слишком "сырым". Я бы предпочел сделать усреднение баллов или что-то в этом роде. Любой указатель?
3 ответа
На ум приходят два решения:
1) поскольку карта Великобритании достаточно квадратная, вы можете выбрать отображение растровых изображений с графствами. Присвойте каждому определенный цвет, а затем визуализируйте границы с помощью черной линии толщиной 1 или 2 пикселя. Это означает, что вам придется выполнять дорогостоящий расчет интерьера / экстерьера только в том случае, если образец окажется на границе. Чем больше растровое изображение, тем реже это происходит.
2) упростить планы округа. Вы можете использовать рекурсивный алгоритм Рамера-Дугласа-Пекера для рекурсивного упрощения границ. Просто убедитесь, что вы кешируете результаты. Возможно, вам также придется решить эту проблему не для границ всего округа, а только для общих границ, чтобы не было пропусков. Это может быть довольно сложно.
Здесь вы можете найти проект, касающийся именно ваших проблем. Хотя он в основном работает с областью, "заполненной" точками, вы можете настроить ее для работы с определением типа "периметр", как у вас.
Он использует подход k-ближайших соседей для расчета региона.
Образцы:
Здесь вы можете запросить копию статьи.
По-видимому, они планировали предложить онлайн-сервис для запроса расчетов, но я не проверял его, и, вероятно, он не работает.
НТН!
Триангуляция полигонов должна помочь здесь. Вам все равно придется проверять много полигонов, но теперь это треугольники, поэтому их легче проверять, и вы можете использовать некоторые оптимизации, чтобы определить только небольшое подмножество полигонов для проверки заданной области или точки.
Кажется, что у вас есть все алгоритмы, которые вам нужны для полигонов, не только для треугольников, вы также можете объединить несколько слишком маленьких треугольников после триангуляции или, если количество треугольников становится слишком большим.