У меня есть набор линейных объектов внутри определенной многоугольной границы. Для каждой линии я хотел бы создать многоугольник, внутри которого каждая возможная точка находится ближе к данной линии, чем к любой другой линии в слое. В прошлом я делал это для точечных объектов ввода, используя триангуляцию Делоне, но если есть аналогичный процесс для линейных объектов, я не смог бы его найти.
ETA: решение Geogeek пришло мне в голову, но в более прямых участках, где у входных линий меньше вершин, получающиеся многоугольники слишком близко (даже перекрывают) линию, что не должны. Здесь красные линии - мои входные данные, вы можете увидеть вершины и полигоны Тиссена, сгенерированные из них.
Возможно, быстрое и (очень) грязное решение могло бы заключаться в том, чтобы преобразовать каждую линию в обильный набор точек, расположенных на равных расстояниях (а не только в вершинах линии), сгенерировать полигоны Тиссена из них, а затем растворить их на основе идентификатора исходной линии.
Ответы:
Чтобы проиллюстрировать решение для обработки растров / изображений, я начал с размещенного изображения. Это гораздо более низкого качества, чем исходные данные, из-за наложения синих точек, серых линий, цветных областей и текста; и утолщение оригинальных красных линий. Как таковой он представляет собой проблему: тем не менее, мы все еще можем получить клетки Вороного с высокой точностью.
Я выделил видимые части красных линейных объектов, вычтя зеленый из красного канала, а затем расширил и размыл самые яркие части на три пикселя. Это было использовано в качестве основы для расчета евклидова расстояния:
(Весь код, показанный здесь - Mathematica 8.)
Идентификация очевидных «гребней» - которые должны включать в себя все точки, которые разделяют две соседние ячейки Вороного - и повторное объединение их с линейным слоем, обеспечивает большую часть того, что нам нужно для продолжения:
Красная полоса представляет то, что я мог сохранить на линии, а голубая полоса показывает гребни в преобразовании расстояния. (Из-за разрывов в самой исходной линии все еще остается много мусора.) Эти гребни необходимо очистить и закрыть с помощью дополнительного расширения - подойдет два пикселя - и тогда мы сможем идентифицировать связанные области, определяемые исходные линии и ребра между ними (некоторые из которых необходимо явно перекомбинировать):
По сути, это позволило идентифицировать пять ориентированных линейных элементов. Мы можем видеть три отдельных линейных элемента, исходящих из точки слияния. У каждого есть две стороны. Я считал, что правая сторона двух самых правых черт одинакова, но в остальном отличил все остальное, дав пять черт. Цветные области показывают диаграмму Вороного по этим пяти признакам.
Команда Euclidean Allocation, основанная на слое, который различает три линейных объекта (которые у меня не были доступны для этой иллюстрации), не будет различать разные стороны каждого линейного объекта, и поэтому она будет объединять зеленые и оранжевые области, обрамляющие крайнюю левую линию ; это разделило бы самый правый признак чирка на две части; и это объединит эти расколотые части с соответствующими бежевыми и пурпурными чертами на их других сторонах.
Очевидно, что этот растровый подход способен создавать тесселяции Вороного из произвольных объектов - точек, линейных частей и даже многоугольников, независимо от их формы, - и он может различать стороны линейных объектов.
источник
Я думаю, что вы можете:
Я надеюсь, что я действительно понял ваш вопрос, если вы не можете предоставить рисунок, чтобы объяснить ваши потребности больше.
источник