@daniil14056

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

Задача, есть Граф, где условно показано, какая точка должна быть ближайшая. Нужно сгенерировать случайно и разбросать так точки на плоскости, что бы связи между ближайшими точками не пересекались..
Вот пример входных данных.
600500c02e023174300489.png
  • Вопрос задан
  • 184 просмотра
Пригласить эксперта
Ответы на вопрос 1
@rPman
решение будет гулять вокруг того, как именно сформулировано условие:
где условно показано, какая точка должна быть ближайшая


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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы