Итак, для работы я работаю над контроллером робота, который исследует произвольную область. Область определяется серией вершин (это многоугольник). Вот пример:
Робот начинает с середины и пытается достичь самой внешней границы, а затем следовать за ней по всему периметру. Однако из-за характера местности он может быть не в состоянии добраться до определенных областей и может исследовать только данный регион:
Что я хочу сделать, так это вычислить все отдельные регионы, которые не были исследованы, и вернуть вершины, определяющие их границы, например:
После того, как это вычислено, у меня должен быть новый массив полигонов, содержащий геометрию для A, B и C.
К сожалению, я не могу придумать хороший и быстрый алгоритм для этого. Каков наилучший способ вычислить это?