Замена CGAL для iOS

Question

У меня есть набор узлов, которые определяют улицы. Каждый узел имеет широту и долготу. Также у меня есть местоположение пользователя с широтой и долготой. Мое намерение состоит в том, чтобы построить диаграмму Вороного для сегментов, определяемых каждой парой узлов, а затем найти, какое местоположение узла узла ближе всего.

Похоже, эта задача может быть выполнена с помощью библиотеки CGAL. Хотя я в процессе компиляции его для среды iOS, возможно, вы, ребята, сможете предоставить ссылки на libs, которые уже скомпилированы против iOS, или были предназначены для использования в среде Objective C с самого начала ...

Потому что я боюсь, что даже если CGAL скомпилируется для меня, я могу попасть в неприятности при использовании. Благодаря!

P. S. Также, возможно, у вас есть лучшее решение. Не стесняйтесь пишете его здесь.

Answer 1

Я никогда не использовал CGAL, поэтому я не могу прокомментировать, лучше ли мое решение.

Но я использовал библиотеку spatialite, чтобы сделать что-то подобное. Spatialite работает поверх sqlite. Когда вы используете его, лучше не использовать библиотеку sqlite, поставляемую с iPhone, а просто перекомпилировать все с нуля с включенным пространственным пространством. После того, как у вас есть данные в базе данных, вы можете использовать просто такие функции, как ST_Distance, чтобы найти закрывающие сегменты.

Spatialite использует R * -Trees для пространственной индексации. Поиск очень быстрый.

Answer 2

CGAL - это беспорядок (дизайн комитета и C++, всегда опасный), ИМХО. Трудно проникнуть.

Но, вам нужно рассчитать диаграмму Voronoi на устройстве? Если ваш набор данных - это уличные данные, это может не так сильно измениться, и вы можете предварительно создать его вне устройства.

И, наконец, диаграмма Вороного является мощной конструкцией, но здесь может быть излишним. Если вы хотите избежать большой библиотеки, достаточно простой эвристики: поместите точки вдоль ваших уличных сегментов. Учитывая местоположение пользователя, найдите ближайшую улицу (используя, скажем, kd-дерево - простую для реализации, быструю, много реализаций). Используйте те, чтобы протестировать набор кандидатов, чтобы найти ближайший.