Замена CGAL для iOS

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

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

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

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


iphone geocoding cgal
person Aleks N.    schedule 27.12.2010    source источник

Ответы (2)


arrow_upward
3
arrow_downward

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

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

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

person Tom Verbeure    schedule 28.12.2010
comment
Спасибо, Том. Я сейчас изучаю эту библиотеку. Отметит ваш ответ как «Ответ», если он действительно подходит. Я надеюсь, что так и будет, так как я точно храню данные узла в базе данных SQLite. - person Aleks N.; 28.12.2010
comment
Похоже, вы дали мне правильный вектор. Вот аналогичный вопрос и совет: stackoverflow.com/questions/4373730/ Видел это раньше, но по какой-то причине отфильтровал это, будучи поглощенным алгоритмом Вороного. :) - person Aleks N.; 28.12.2010

arrow_upward
0
arrow_downward

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

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

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

person payne    schedule 21.01.2011
comment
На самом деле то, что я сделал, это скомпилировал библиотеку Spatialite для iOS, затем преобразовал мою базу данных MySQL в базу данных со столбцом Geometry и пространственным индексом и позволил библиотеке сделать все остальное. - person Aleks N.; 22.01.2011