Группировка географических фигур
Я использую Dundas Maps и пытаюсь нарисовать карту мира, где страны сгруппированы по регионам, которые являются специфическими для реализации бизнеса.
У меня есть данные формы (точки и сегменты) для каждой страны в мире. Я могу объединять страны в регионы, добавляя все точки и сегменты для стран внутри региона в новую форму региона.
foreach(var region in GetAllRegions()){
var regionShape = new Shape { Name = region.Name };
foreach(var country in GetCountriesInRegion(region.Id)){
var countryShape = GetCountryShape(country.Id);
regionShape.AddSegments(countryShape.ShapeData.Points, countryShape.ShapeData.Segments);
}
map.Shapes.Add(regionShape);
}
Проблема в том, что границы страны все еще отображаются внутри региона, и я хочу удалить их, чтобы отображались только региональные границы.
Полигоны Дунды должны начинаться и заканчиваться в одной и той же точке. Это касается всех форм страны. Теперь мне нужен алгоритм, который может:
- Определить, где границы страны пересекаются на региональной границе, чтобы я мог присоединиться к сегментам региональной границы.
- Определите, какие границы страны не являются региональными, чтобы я мог их отменить.
- Отсортируйте получающиеся региональные точки так, чтобы они последовательно описывали границы формы.
Ниже я дошел до карты. Вы можете видеть, что границы страны все еще должны быть удалены. Например, граница между Монголией и Китаем должна быть отброшена, тогда как граница между Монголией и Россией должна быть сохранена.
Причина, по которой мне нужно сохранить региональную границу, заключается в том, что цвета области будут важны при передаче информации, но смежные области могут быть одного цвета. Регионы могут меняться, чтобы включать или исключать страны, и поэтому формирование регионов должно быть динамичным.
РЕДАКТИРОВАТЬ: Теперь я знаю, что я то, что я ищу, это союз многоугольников. Дэвид Лин объясняет, как это сделать , используя пространственные функции в SQL Server 2008, что может быть вариантом, но мои усилия остановились, потому что результирующее объединение многоугольников настолько сложно, что SQL усекает его до 43 680 символов. Сейчас я пытаюсь найти обходной путь для этого или найти способ объединения в коде.
2 ответа
Я надеюсь, что при группировке стран не будет перекрытия - вы можете взять довольно наивный алгоритм, который ищет общие вершины. Простым представлением было бы перебрать точки на одном многоугольнике, чтобы посмотреть, есть ли он на каком-либо из другие ваши многоугольники и разделяет ту же следующую или предыдущую точку, чтобы увидеть, есть ли совпадение. Затем просто удалите общую вершину, чтобы создать объединение
Предположим, что соседние страны разделяют общие вершины и ребра (в противном случае задача значительно усложняется).
Для каждого региона пройдите через полукруги, соответствующие странам в регионе, и создайте список вершин и ребер. Каждое ребро должно иметь указатели на две вершины, являющиеся его конечными точками, и каждая вершина должна иметь указатели на ребра, конечной точкой которых она является.
Добавляя вершины в список, убедитесь, что они уникальны. Другими словами, если вы добавляете вершину с координатами (x, y) , если такая вершина уже есть в списке, не добавляйте новую. Это означает, что вам потенциально придется сравнивать каждую новую вершину с уже имеющейся в списке. Вы можете ускорить это, разбив ограничивающую рамку области, скажем, на n x n бункеров, в которых вы можете хранить вершины. Когда появляется новая вершина, найдите ее бункер и сравните его с другими вершинами в этом бункере.
По мере добавления ребер в список ребер сделайте то же самое - если добавляется ребро (v0, v1), проверьте, существует ли ребро (v0, v1) или (v1, v0). За исключением этого случая, удалите существующее ребро из списка и не добавляйте новое ребро. Причина в том, что эти два края «взаимно отменяют» друг друга - они происходят из соседних стран.И не забудьте удалить указатели ребер в списке вершин, которые соответствуют удаленному ребру.
Когда вы это сделаете, у вас должен быть список ребер, не общих для двух стран. Это края, образующие границу области. У вас также должен быть список вершин, некоторые из которых указывают на два ребра, а другие не указывают ни на одно ребро. Бывшие вершины находятся на границе региона.
Теперь выберите ребро из списка ребер и удалите его (и удалите соответствующие указатели ребер из вершин, которые являются его конечными точками) из списка ребер. Перейдите к одной из конечных точек вершины, и она укажет на другое ребро. Таким образом вы пройдете от края к краю вдоль границы области. Добавьте эти края в свой regionShape по мере удаления их из списка редакторов. В конце концов вы вернетесь к конечной точке вашего первого ребра, и у вас будет замкнутый цикл.
Если в списке кромок остались какие-либо края, снова запустите процесс, чтобы извлечь еще один контур границы, и продолжайте, пока все контуры границ не будут извлечены и список кромок не станет пустым.
Я упомянул одну оптимизацию, которая заключается в пространственной организации вершин в интервалы, чтобы вы могли быстрее проверить их равенство. Другая оптимизация - избежать физического удаления ребер из списков, а просто пометить их как «удаленные».