Группировка географических фигур

Question

Я использую 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);
}

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

Полигоны Dundas должны начинаться и заканчиваться в одной и той же точке. Это касается всех форм страны. Теперь мне нужен алгоритм, который может:

• Определите, где границы страны пересекаются на региональной границе, чтобы я мог присоединиться к сегментам региональной границы.
• Определите, какие границы страны не являются региональными, чтобы я мог их отменить.
• Сортировка полученных региональных точек так, чтобы они последовательно описывали границы формы.

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

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

EDIT: Теперь я знаю, что я ищу СОЮЗ полигонов. Дэвид Лин объясняет, как это сделать , используя пространственные функции в SQL Server 2008, что может быть вариантом, но мои усилия остановились, потому что результирующее объединение многоугольников настолько сложно, что SQL усекает его до 43 680 символов. Сейчас я пытаюсь найти обходной путь для этого или найти способ объединения в коде.

Answer 1

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

Answer 2

Предположим, что соседние страны имеют общие вершины и ребра (если нет, проблема становится намного сложнее).

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

Добавляя вершины в список, убедитесь, что они являются уникальными. Другими словами, если вы добавляете вершину с координатами (x,y), если такая точка уже есть в списке, не добавляйте новую. Это означает, что вам, возможно, придется проверять каждую новую вершину на соответствие тем, которые уже есть в списке. Вы можете ускорить это, разбив ограничивающий прямоугольник области, скажем, на n x n корзин, в которых вы можете хранить вершины. Когда приходит новая вершина, найдите ее корзину и сравните ее с другими вершинами в этой корзине.

Когда вы добавляете ребра в список ребер, делайте то же самое - если ребро (v0, v1) добавляется, проверьте, существует ли существующее ребро (v0, v1) или (v1, v0). За исключением этого случая, удалите существующее ребро из списка и не добавляйте новое ребро. Это потому, что эти два края «взаимно отменяют» друг друга - они из соседних стран. И не забудьте исключить указатели ребер в списке вершин, которые соответствуют удаленному ребру.

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

Теперь выберите ребро из списка ребер и удалите его (и удалите соответствующие указатели ребер из вершин, которые являются его конечными точками) из списка ребер. Перейдите к одной из конечных точек вершины, и она будет указывать на другой край. Таким образом, вы будете идти от края к краю вдоль границы региона. Добавьте эти ребра в ваш regionShape, удалив их из списка ребер. В конце концов вы вернетесь к конечной точке вашего первого ребра, и у вас будет замкнутый цикл.

Если в списке ребер остались какие-либо ребра, запустите процесс еще раз, чтобы извлечь еще один контур границы, и продолжайте, пока все петли границы не будут извлечены и список ребер не будет пустым.

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