У меня есть программа, которая пока берет набор случайных точек, сайтов, и формирует вокруг этих точек соответствующую диаграмму Вороного, представленную в виде графа углов и ребер. Это также дает мне триангуляцию Делоне в качестве еще одного графа, в котором все сайты являются его узлами (хотя я не могу сказать, полезно ли это здесь).
До сих пор каждый реберный объект имел запись о том, с какими углами он инцидентен, и каждый угловой объект имел записи о том, какие ребра инцидентны ему и с какими другими углами он примыкает. Моя цель состоит в том, чтобы иметь возможность добавить в мой класс Edge два поля для двух соседних сайтов и расширить мой класс Site, добавив два поля: одно поле, содержащее набор углов, окружающих его, и другое для набора ребер. вокруг него.
Я думал, что можно было бы сгенерировать все отдельные полигоны, используя модифицированный поиск в ширину. Однако для этого потребуется просмотреть все сайты и выяснить, какой из них принадлежит какому полигону, и это будет O (n ^ 2), что не идеально. Есть ли более эффективный алгоритм, который может сделать то же самое?
