Как поделить пространство на сетку треугольников (граф)?

Question

[egorkozelskij]

Здравствуйте!

Есть область писелей. Мне нужно построить граф путей по этой области. То есть разделить все пространство на треугольники и вершины записать в граф.
Какие алгоритмы можно использовать для такой задачи? (Если важно, пишу на питоне)

Comments

[egorkozelskij]

Понятия, который мне дал лектор:
High pass filtering and Hough transform.
Non-Linear bordered obstacles may be approached by bounding boxes parallel to model axes
Data Points are the center points of the line segments in the free area

[egorkozelskij]

Подсказали, что мне нужен алгоритм Хафа.
Подскажите, как его применить для разбиение пространства?

Answer 1

[GreatRash]

А не нужна ли вам триангуляция Делоне?

Comments

[egorkozelskij]

А как приминительно к Делоне я смогу испольовать преобразование Хафа?
Возможно ли это все дело объединить, чтобы не уходить от задания?
(Общая задача стоит в том, чтобы для передвижения робота разметить пространство на треугольники.)

[GreatRash]

egorkozelskij, я вообще не совсем понимаю для чего это преобразование Хафа нужно. Судя по описанию - это совсем не то, что вам нужно.

[egorkozelskij]

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

[egorkozelskij]

Тогда как брать эти точки? Какая точка отсчета?

[egorkozelskij]

Вот часть алгоритма:
На плоскости есть другие предметы (квадрат, круг и другие фигуры). Строю прямые, касательные к фигурам и на них беру точки. Не совсем понятно каким образом брать точки на этих прямых? Сколько их там нужно?
Да, сетка получится, но как управлять ее плотснотью? Просто через каждое фиксированное расстояние брать точку может?

[GreatRash]

egorkozelskij, вам же лектор написал - "Data Points are the center points of the line segments in the free area". Т.е. берёте центр у каждой найденной линии.