программы расчета выпуклых оболочек.

я есть большой массив вершин, некоторые из них являются ребрами, некоторые являются избыточными (внутри фигуры), и я хочу их удалить.

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

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

Любое предложение?

 sykora25 янв. 2009 г., 17:46
Вы хотитеa многоугольник, который охватывает все точки, или вы хотитенаименьшее (с точки зрения площади) многоугольник, который охватывает все точки?
 fabiopedrosa25 янв. 2009 г., 17:53
@sykora, многоугольник, который охватывает все точки. Сканирование Грэма кажется действительным. Благодарю.

Ответы на вопрос(0)

Ваш ответ на вопрос