Полигон лежит в базе в виде обычного пути с тегом boundary.
Путь считается прямым как плака для скорости. Но примеров кривого пути, выпадающего за границу пока не находилось. Пути имеют от двух до нескольких сотен точек, проверка всех существующим алгоритмом - просто нереальное занятие.
Про выпуклые полигоны ничего сказать не могу, вообще не математик
Как сейчас происходит обработка? Выкачивается вся база, затем выполняется проверка, какие-то результат сохраняются? На что уходит бОльшее количество времени - на выкачивание или на обработку? Известно, сколько всего точек в путях, не только конечных?
Все точки в пути пронумерованы. Соответственно номер последней = количеству точек. Обработка идет как запрос всех точек, запрос координат полигона, обработка. Следующий полингон, обработка и так доконца. Данные есть путь в полигоне или нет пишутся в отдельную таблицу.
Больше всего тратится на обработку.
Для оптимизации процесса обработаные точки пишутся в отдельную таблицу и при следующих прогонах при неизменных координатах полигона и точки не проверяются. Это дало существенный прирост скорости, но это касается только точек ВНУТРИ полигона, а остальные все равно приходится проверять.
Вычисляем габаритный прямоугольник нашего way (тупо по максимумам и минимумам составляющих его точек);
Берем точку A заведомо вне его (а значит, и вне way);
Берем список точек, входящих в габаритный прямоугольник (O1, O2, …, On);
Цикл(i, i <= n, i++). Проверяем, сколько сегментов нашего way пересекает отрезок AOi. Получаем количество пересечений с границей way. Если количество пересечений нечетное - точка Oi внутри way, если четное - снаружи. (КонецЦикла)
Хммм. Получить по ID точки вэя - элементарно.
Потом точки в пределах габаритного прямоугольника - столь же просто. База, конечно, поюзается - но не больше, чем при любом другом запросе региона.
Вычисления вообще никакие и могут выполняться несколько раз в секунду.
Я недавно писал код одной трехмерной игры и ужасался, КАКОЙ объем вычислений проделывает ЦП каждую секунду. Конкретной в той игре каждую секунду обрабатываются МИЛЛИОНЫ вокселей. И с каждым из них проделываются не самые тривиальные операции.
И ведь геймплей-то простенький.
На этом форуме пива не пьют, похоже
По ссылке всё написано. Там даже проще описано, кстати - выбран луч, направленный вправо. То есть то, о чем я писал, только для облегчения вычислений точка A выбрана точно справа от O. Отдельно обрабатываются нестандартные ситуации. Весь код занимает всего ничего.
Не вопрос, просто еще одна реализация алгоритма с лучем из точки. ВОпрос в том, что обработка получается долгая. И с ростом количества полигонов и количества точек она будет идти еще дольше. Для Москвы получается что нужно проверить 130 000+ отрезков на пересечение с 1000+ сторонами полигона. То есть это 130 000 000 итераций по несколько шагов внутри. Полигонов сейчас почти 100, большинство из нескольких десятков точек, но есть и больше, не только Москва.
вычислительную сложность алгоритма можно снизить, применив техники BSP/quadtree сотоварищи. Только у меня бооольшие сомнения, что это стоит реализовывать на серверной стороне. Удобно, конечно, но ведь сдохнет, бедолага, под запросами.
Угу. Осталось найти сервер с видеокартой нвидиа свежих поколений и написать дллку для пхп. которая бы работала с кудой… Вот у меня это все бегает на домашнем серваке, там ATI, причем простенькая
Вы к чему, вообще, хотите прийти? К тому, что это сделать просто, а значит, можно делать каждый раз, когда нужно определить, в каком городе находится улица/дом? Зачем, если KekcuHa каждый день для каждого города России?
Всё, что можно посчитать заранее, нужно посчитать заранее.
Или вам просто был интересен алгоритм? Тогда прошу прощения, что влез.
Вот и я про то же.
Тем более, что обрабатывая окрестности своей деревни, грузить planet.osm (ну ладно, даже russia.osm) крайне накладно по вычислительным (и по памяти - что все равно сведется к времени вычислений, если не загнется вообще) ресурсам.
А алгоритмы можно и нужно оптимизировать.
Варианты оптимизации следующие (что пришло сразу в голову):
Уже упомянутый boundbox.
“полувыпуклые” (т.е. те у которых по любой горизонтали односвязная область) полигоны - тогда можно отсортировать ребра и проверять точку на попадание между двух ребер.
Целочисленные расчеты (в свете быстрых сопроцессоров может быть не очень актуально - но требует оценки). Оптимизация сравнений (уход от делений и т.д.)
Более экономные тыпы данных (4 байта вместо 8) даст выгоду по памяти/кэшу/свопу → дополнительное быстродействие.
Повторное использоваение предыдущих расчетов - т.е. не проводить расчеты для полигона/точки(дороги), которые не менялись с прошлого расчета (Очень большая выгода - но требует хранения базы - к вопросу о постоянном повторе расчетов).
…
И вообще, можно сделать доступными для народа исходники, тогда кто-угодно сможет по месту посмотреть, что подлежит оптимизации.
К чему прийти? К тому ,чтобы обсчет занимал не несколько часов, а меньше. Причем не столько с расчетом на сегодня, сколько с расчетом на ближайшее будущее. Русский ОСМ начал развиваться очень активно, это видно даже по форуму. Есть предпосылки к тому, что развитие пойдет еще быстрее - карта во многих местах дошла до уровня пригодного для эксплуатации и ею начнут пользоваться, а значит будет приток рисовальщиков.
Я уже писал, что каждый новый полингон в разы увеличивает количество операций по провеоке. Сколько в РФ городов? Сейчас прогон занимает полтора-два часа, сколько он будет занимать завтра?
Весь спор пошел из заявлений некоторых участников форума о том, что операции с базой осм не требуют сложных операций и больших вычислительных ресурсов. Как видим, пришли к выводу что таки требует.
Из предложеных методов оптимизации алгоритма:
-ббокс и непроверка неизменившихся точек уже реализованы, целочисленные расчеты применены,
-от деления отказаться не могу - знаний в области математики не хватает
-типы данных надо оптимизировать, пока используются те, что применены в типовой базе осм
Про полувыпуклые вообще не понял Для меня это темный лес…
