Соединяйте узлы с соседями по прямой видимости (прямой) ⇐ Python

[Anonymous]

У меня есть структура, похожая на лабиринт, но с гораздо большим открытым пространством. И для каждого узла в структуре я хотел бы найти всех его «соседей» (узлы являются соседями, если они находятся на прямой видимости, т. е. нет стен, блокирующих прямую линию между ними).
Вот небольшое изображение, которое поможет объяснить, что я имею в виду.

• Черные линии — это стены.
• Красные точки – это узлы.
• Синие линии — это линии для соединения соседей (обратите внимание, что ни одна синяя линия не пересекает черную линию).

[img]https:// i.sstatic.net/899IR.jpg[/img]

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

Код: Выделить всё

for n1 in nodes:
for n2 in nodes:
if not intersect(n1, n2, edges):
n1.neighbours.append(n2)
n2.neighbours.append(n1)

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

Подробнее здесь: https://stackoverflow.com/questions/704 ... raightline