Есть ли алгоритм для создания контура графика?

Я искал в Интернете и, возможно, мне не хватает некоторых правильных ключевых слов, но мне не удалось найти ничего подобного. Я нашел только полилинии (или просто линии), которые не совсем являются графиками. Я хотел бы создать контур графика (радиуса r), как показано на рисунке. Что-то уже есть в наличии? Я бы хотел, так сказать, не изобретать велосипед.

введите здесь описание изображения

Если бы кто-нибудь мог намекнуть мне на что-то или хотя бы на какой-то основной принцип, как это сделать, было бы здорово. В противном случае я, конечно, "изобрету" его самостоятельно.

Оптимально на С#.

Обновление: мне нужно рассчитать контурный многоугольник, а не просто нарисовать его визуально. Зеленые точки представляют полученный многоугольник. Также полностью игнорируются «внутренние» отверстия. Достаточно одного контурного полигона.

Обновление 2: улучшенное изображение, чтобы показать некоторые более экстремальные случаи. Кроме того, ребра графа никогда не перекрываются, поэтому нет необходимости учитывать это.

Обновление 3: изображение снова обновлено, чтобы отразить стыки со скосом.


c# graph algorithm outline
person SmartK8    schedule 01.02.2015    source источник
comment
как насчет рисования каждого ребра толщиной 2r? что бы контур графика был заполнен!   -  person Hamid Pourjam    schedule 02.02.2015
comment
О, мне нужно не его рисовать, а вычислять получившийся многоугольник. Я отредактирую вопрос, чтобы отразить это. Хорошая точка зрения.   -  person SmartK8    schedule 02.02.2015
comment
Какие углы будут? Если угол, подобный верхнему левому, становится все меньше и меньше, что должно произойти с контуром? он должен двигаться к бесконечности?? Также: Могут ли линии сблизиться, чтобы очертания слились?   -  person TaW    schedule 02.02.2015
comment
Рисовать в хорошем разрешении, а затем отслеживать результат для углов, все еще вариант, имхо; по крайней мере, если разрешение может быть достаточно хорошим ..   -  person TaW    schedule 02.02.2015
comment
Я нарисую слегка измененную версию, чтобы также показать некоторые перекрытия. Я бы рассматривал вариант отслеживания в крайнем случае. Проблема в том, что это изображение маленькое, чтобы соответствовать SO, но в противном случае график может быть очень большим (по пикселям). Таким образом, полученное изображение будет сумасшедшим (10k x 10k пикселей или даже больше).   -  person SmartK8    schedule 02.02.2015
comment
Немного обновил картинку и описание. Моя вина в том, что я не был ясным (но это не пришло мне в голову изначально).   -  person SmartK8    schedule 02.02.2015
comment
Может быть, вычислить вогнутую оболочку на множестве точек. См. ubicomp.algoritmi.uminho.pt/local/concavehull.html.   -  person tmlen    schedule 02.02.2015
comment
tmlen: Я был очень взволнован, но потом понял, что некоторых зеленых точек на самом деле не существует раньше времени. Например, 3-я зеленая точка слева (координата x - ее трудно определить) или 2-я, 4-я или 6-я. Я так понимаю, вы имели в виду создание 4 угловых точек для каждого края, а затем запуск на нем вогнутого корпуса. Но как это решить для точек, которые на самом деле создаются процессом (многие из них на самом деле).   -  person SmartK8    schedule 02.02.2015
comment
Это не приблизит вас к решению, но мой вопрос о малых углах был вполне реальным: вы хотите их срезать (митра) или они будут создавать огромные шипы или их все равно не может быть?   -  person TaW    schedule 02.02.2015
comment
Ты прав. Я предполагаю, что они должны быть обрезаны, что означает круглое или косое соединение. Но очевидно, что круглое соединение немного сложнее и приведет к более сложному результирующему многоугольнику. Итак, на данный момент я предполагаю, что соединение со скосом - это путь, если вышеуказанный радиус сохраняется для всех точек исходного графика и соответствующего контура.   -  person SmartK8    schedule 02.02.2015
comment
Я начинаю понимать, почему я ничего не могу найти по этому поводу. Кажется, что эта задача довольно сложная. Существует множество контуров полилиний, но я понятия не имею, как масштабировать их, чтобы отобразить другого зверя IMO.   -  person SmartK8    schedule 02.02.2015
comment
Спасибо, сумма Минковского звучит именно так, как я хочу. Я расследую это. Пока единственная небольшая возможная проблема, которую я вижу, это то, что у меня не полигон, а граф. Но, может быть, это не имеет значения. Я надеюсь, что это не так.   -  person SmartK8    schedule 02.02.2015
comment
Да, это правда, но вам все равно нужно соединить эти линии, чтобы создать замкнутый многоугольник. Но я все еще работаю над его тестированием. Я нашел библиотеку Clipper, которая вычисляет сумму Минковского на C#.   -  person SmartK8    schedule 03.02.2015

Ответы (1)


arrow_upward
0
arrow_downward

Во-первых, для каждого «отрезка линии» от точки A до B сгенерируйте к нему прямоугольник (все 4 точки, так сказать, как «путь»). Затем найдите два перекрывающихся прямоугольника и объедините их:

Слияние немного сложно, идея: начните с вычисления угла всех 8 линий (например, если прямоугольники проходятся по часовой стрелке). Затем пройдите один прямоугольник до первого пересечения линии-линии, проверьте с помощью углов, какое направление является «внешним», и двигайтесь вдоль линии пересечения второго прямоугольника ... пока снова не достигнете начальной точки => Теперь вы прошли форма обоих вместе (и, надеюсь, сохранил его где-то).

Объединяйте до тех пор, пока не останется только одна большая часть (или несколько непересекающихся частей). Теоретически, начиная с любой точки, вы можете пройти всю фигуру, но есть еще одна проблема: возможны отверстия.
Если одна фигура имеет два или более непересекающихся набора точек (где ни одна точка из множества 2 не достижима из набор 1 и наоборот), все дизъюнктные пути, кроме одного, являются дырочными. Легкая возможность получить реальную внешнюю границу — это поиск экстремума, т.е. точка с наибольшей или наименьшей координатой X или Y (достаточно только одной из 4 комбинаций). Эта точка наверняка является частью внешней границы.

person deviantfan    schedule 01.02.2015
comment
Я знаю, что это всего лишь идея, но не будет ли слияние плохо масштабироваться? Я имею в виду. Вы объединяете два прямоугольника, но затем вам нужно снова пройти весь объединенный прямоугольник, когда в него вливается другой? У меня будут тысячи этих ребер графа. Также граф никогда не перекрывается (ребро пересекает другое ребро). Но проблема с дырками, о которой вы упомянули, довольно серьезная, вам в основном нужно будет делать CSG на прямоугольниках. Но я рассматриваю ваше решение (я имею в виду последствия и осуществимость). - person SmartK8; 02.02.2015
comment
Жаль, что здесь была ночь. Первый подход выглядит нормально, поворачивая угол до пересечения, но я боюсь, что слияние тысяч прямоугольников действительно приведет к безумному количеству слияний и пересечений линий - невозможно (так как это должно быть в реальном времени). Я, наверное, не понимаю второй подход крайностей. Потому что, на мой взгляд, слияние двух прямоугольников может дать многоугольник с 6 точками, и я не знаю, как обнаружить внутренние (не крайние) точки. Может быть, уточните немного, если вы будете. - person SmartK8; 02.02.2015