Как сгенерировать случайно точки на плоскости, так что бы ближайшие к ним соответствовали связями к узлам графа?

Question

[Даниил]

Задача, есть Граф, где условно показано, какая точка должна быть ближайшая. Нужно сгенерировать случайно и разбросать так точки на плоскости, что бы связи между ближайшими точками не пересекались..
Вот пример входных данных.

Comments

[Сергей Соколов]

Уточните: почти-случайно нужно расположить именно вершины этого графа?
Т.е. можно именно его положить на плоскость, случайно повернуть, увеличить-уменьшить. И затем каждую точку чуть сдвинуть на какуют-то незначительную малую величину?

[Даниил]

Сергей Соколов, насчет трансформаций думал, но это не то. То есть не просто рандомно сгенерировать 10 точек, и куда угодно, а что бы по этим точкам можно построить триангуляцию Далоне! Возможно это вполне себе задачка из книжек, о я не нашел.

[Сергей Соколов]

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

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

[Сергей Соколов]

Ну и триангуляция – от слова треугольник. На рисунке пропущены несколько рёбер.

[xmoonlight]

Сергей Соколов, не подскажешь софт в чём такое можно чертить?

[Сергей Соколов]

xmoonlight, эта иллюстрация из wiki. Нарисовать – GeoGebra.

[xmoonlight]

Сергей Соколов, Ясно. Спасибо.

[Сергей Соколов]

в GeoGebra, оказывается, есть встроенная функция DelaunayTriangulation(). Вот накидал точки как у ТС и построил:

скрин

Кайф в том, что точки можно свободно двигать и смотреть, как перестраивается диаграмма.

[xmoonlight]

Сергей Соколов, Красиво!
Забыл узнать: оно без инета пашет (оффлайн режим) или только через свой сервис?

[Сергей Соколов]

Voronoi() тоже есть в GeoGebra

spoiler

[Даниил]

Сергей Соколов, вообще изначально 100% совпадения задачи не стояло. Ща думаю как примерно по набору по графу максимально похоже составить. То есть возможно и с обрывами, но минимум.

[xmoonlight]

Сергей Соколов, ?

[Сергей Соколов]

xmoonlight, GeoGebra вроде обычное standalone приложение под популярные платформы. Оффлайновое. Не проверял. Почему бы не скачать и не узнать

[xmoonlight]

Сергей Соколов, Теперь стало ясно, что нужно тестить..

Почему бы не скачать и не узнать

Не спорю, просто я думал ты сразу точно скажешь, чтобы не тестить самому.
Благодарю за ответ.

Answer 1

[rPman]

решение будет гулять вокруг того, как именно сформулировано условие:

где условно показано, какая точка должна быть ближайшая

например если это конкретные значения, то решение будет в поиске пересечения окружностей вокруг каждой вершины и ее соседей

Дальше эту задачу можно расширить, если у каждого из этих значений будет дельта окружность (т.е. расстояния указаны в виде min/max) тогда ищем не точки пересечения а области пересечения колец, ну и комбинаторика, в какую область какую точку запихнуть чтобы не возникало противоречий, с каждым шагом алгоритма увеличивая количество учитываемых вершин - с трудоемкостью в факториал.