Координатные точки на полигоны

Question

У меня есть большой набор координат, который включает в себя:

59.284 18.42
59.401 18.078
58.894 17.854
59.277 18.742
59.219 18.186
59.472 18.108

Координаты широты имеют разрешение 0,001 и долготу 0,002.

Каждая точка связана с прямоугольной областью.Для точки (x, y) широта этой области находится в диапазоне от x до x + 0,01, при этом долгота составляет от y до y + 0,02.

Каждая точка связана со значением от 1 до 10.

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

Есть ли какой-нибудь алгоритм или инструмент, который мог бы помочь мне в этом?

Я могу программировать на python, csharp, java или c ++.

Спасибо за вашу помощь,

Барри

Answer 1

Для каждого набора координат, связанного со значением от 1 до 10, делайте

1. масштабировать координаты до целых значений (умножить на 1000), чтобы избежать сравнений с плавающей запятой
2. преобразование координат в прямоугольные многоугольники
3. 'объединяет' эти многоугольники (используя Clipper , Boost Geometry или Boost Polygon ) для объединения смежных

Answer 2

Вот ответ:

http://www.cs.man.ac.uk/~toby/alan/software//

Answer 3

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

Ответ № 11 в статье на форуме CFD обобщает один метод следующим образом:

(1) Предположим, у вас есть пакет печати, который может строить прямые отрезки. (2) Построить точную сетку с (x, y) координатами по области, на которой вы хотите построить график. (3) Оценить функцию, которая будет настроена в каждом узле, путем вычисления функции или, возможно, интерполирования некоторого дискретного приближения. (4) Выберите список уровней моды для построения графика. (5) Для каждого прямоугольника сетки: (a) Найдите наибольшее и наименьшее значения функций по углам. (b) Игнорировать уровни контуров вне диапазона самых больших и самых маленьких значений. (c) Для каждого приемлемого контура и для каждого ребра найдите значения координат пересечения уровня контура и прямой линии, соединяющей значения функции по углам. (d) Построить отрезки, соединяющие координаты, с равными значениями контура.

Заметьте, ответы № 6- # 10 кратко рассказывают об использовании gri, PGPLOT, matlab и Plotmtv для построения контуров.

Answer 4

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