На входе - файл в формате .osm (или текст)
Имеется - некий заранее выбранный язык программирования/база данных.
Требуется - решить ту или иную геометрическую задачку на карте используя некий абстрактный язык программирования. Вариант - “возьми вот это, там есть такая функция встроенная в ядро” не подходит.
Так как задачек может быть много создам единую тему на всё.
Задача первая. Уже не первый день думаю но полученный алгоритм не кажется оптимальным.
Поиск объектов для которых заданная точка является внутренней
Собственно есть некоторая точка. Нужно из списка площадных объектов найти те, для которых точка является внутренней. Простейшее применение - найти полигоны городов для которых данная точка place=town является внутренней. Аналогичная проблема - найти дома внутри которых данная точка POI расположена чтобы узнать адрес и т.п.
Алгоритм для выпуклых областей кажется тривиальным. Но вот с невыпуклыми объектами всё сложно. Да и дырки усложняют ситуацию.
Есть ли какой-то общепризнанный оптимальный алгоритм?
В перловых библиотеках такое есть, но разобраться в них немногим легче, чем своё написать.
А так - точка должна находиться внутри ограничивающего прямоугольника (для скорости), внутри всех склеенных outer-линий, снаружи всех склеенных inner-линий.
Принадлежность точки невыпуклому многоугольнику - алгоритмы находятся (например, пробегаем по сторонам, трапеция опущенная на OX либо захватывает точку, либо освобождает, либо не трогает, сложность O(n) ).
Кто в теме - напишите как это по-человечески делается 
Из методов, не требующих подготовки геометрий, метод луча:
из точки вдоль любой оси пускаем луч на бесконечность и считаем рёбра, которые этот луч пересечёт. если рёбер нечётное число, то точка внутри, иначе снаружи.
Лёша может рассказать про PolygonTree. Он требует подготовки геометрии, но очень шустр при сложных контурах.
Ну вообще-то я мат-мех заканчивал … И топологию изучал, но похоже геометрический процессор глючить стал Кстати, метод луча не так уж и плох И главное - совершенно спокойно переносит большое количество сложных дырок.
http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm
Winding Number, на столько же эффективен, но более точный.
По человечески это делается при помощи пространственных индексов (дабы избавиться от большей части переборов). Но требует предварительного создания этого индекса. Если индекс помещается в памяти, то всё просто - добавляем нужные полигоны в индекс, а затем используем его для поисков. Сначала быстрый поиск кандидатов по индексу, а затем перебор кандидатов при помощи точных алгоритмов. Вот если в память не лезет - тут уже сложнее…
Подскажите, планарные алгоритмы не будут ли давать сбои на геоиде?
Upd: здесь вроде разумная подборка тестов точка/многоугольник
OGC Simple Features именно поэтому определены, как “последовательность точек, соединённых поямыми линиями в той проекции, в которой они заданы”.
У нас две с половиной проекции в осме - сферический меркатор, wgs84 lonlat, и все остальные. Погрешности перехода между первой и второй обычно намного меньше, чем общая точность отрисовки карты, а остальные на практике почти не используются 
Т.е. о переходе сфера-плоскость можно обычно не париться, оно будет влиять только при подсчёте расстояний и площадей.
Что стоит учитывать, так это то, что за 180-м градусом идёт минус сто семдесят девятый
Ну и для коллекции: http://free-books.dontexist.com/book/index.php?md5=17AF17B2C1988C556CADD01C3D6E4772
Похоже, оптимально использовать метод луча (горизонтального, дабы не мучаться)
Поиск всех полигонов, содержащих одну заданную точку и без сложных структур данных в один проход делается, а вот если точек много, нужны умные деревья для хранения сегментов полигонов (для быстрого поиска пересекающих отрезков).
Препарата - книжка хорошая, реально, хоть и 1989 г.
Только ты ссылку для нас-халявщиков забыл запостить:
http://search.cpan.org/~liosha/Math-Polygon-Tree-0.041/lib/Math/Polygon/Tree.pm#contains_points
Чего уж стесняться-то