Во-первых, я рекомендую использовать файлы 2008 TIGER .
Во-вторых, как отмечают другие, сейчас существует много проектов, которые уже читают, интерпретируют, конвертируют и используют данные. Однако создать собственный анализатор для этих данных почти тривиально, поэтому нет смысла просматривать код другого проекта и пытаться извлечь то, что вам нужно, если вы не планируете использовать их проект в целом.
Если вы хотите начать с нижнего уровня
1010 * Синтаксический *
Создание собственного синтаксического анализатора TIGER (достаточно просто - просто БД из отрезков линий) и построение простого рендера поверх этого (линий, многоугольников, букв / имен) также будут довольно простыми. Вы захотите взглянуть на различные типы проекций карты для фазы рендеринга. Наиболее часто используемый (и, следовательно, наиболее знакомый пользователям) проектор Mercator - он довольно простой и быстрый. Возможно, вы захотите поиграть с поддержкой других проекций.
Это даст немного «удовольствия» с точки зрения того, как проецировать карту и как изменить эту проекцию (скажем, пользователь нажимает на карту, вы хотите видеть широту / долготу, по которой он щелкал - требуется реверсирование) текущее уравнение проекции).
Rendering
Когда я разработал рендерер, я решил основывать окно на фиксированном размере (встроенное устройство) и фиксированном увеличении. Это означало, что я мог центрировать карту по широте / долготе и с центральным пикселем = центральный широта / долгота при данном увеличении, и, учитывая проекцию меркатора, я мог вычислить, какой пиксель представляет каждый широту / долготу, и наоборот.
Некоторые программы вместо этого позволяют окну меняться, и вместо увеличения и фиксированной точки они используют две фиксированные точки (часто верхний левый и нижний правый углы прямоугольника, определяющего окно). В этом случае определение переноса пикселя в широту становится тривиальным - это всего лишь несколько интерполяционных вычислений. Вращение и масштабирование делают эту передаточную функцию немного более сложной, но не должны быть значительно сложнее - это все еще прямоугольное окно с интерполяцией, но углы окна не обязательно должны быть ориентированы по отношению к северу. Это добавляет несколько угловых случаев (например, вы можете вывернуть карту наизнанку и посмотреть на нее, как будто изнутри Земли), но это не обременительно и может быть решено во время работы над ней.
После того, как вы сделали передачу широты / долготы в пиксели, рендеринг линий и многоугольников становится довольно простым, за исключением обычных проблем с графикой (таких как несоответствие границ линий или многоугольников, сглаживание и т. Д.). Но рендеринг простой уродливой карты, такой как это делают многие рендеры с открытым исходным кодом, довольно прост.
Вы также сможете играть с вычислениями расстояния и большого круга - например, хорошее эмпирическое правило состоит в том, что каждый градус широты или долготы на экваторе составляет приблизительно 111,1 км - но один меняется по мере приближения к полюс, в то время как другой продолжает оставаться на 111,1 км.
Хранение и конструкции
Однако то, как вы храните данные и ссылаетесь на них, во многом зависит от того, что вы планируете делать с ними. Множество трудных проблем возникает, если вы хотите использовать ту же структуру базы данных для демографии и для маршрутизации - данная структура базы данных и индексирование будут быстрыми для одного и медленными для другого.
Использование почтовых индексов и загрузка только ближайших почтовых индексов работает для небольших проектов рендеринга карт, но если вам нужен маршрут по всей стране, вам нужна другая структура. У некоторых реализаций есть базы данных «наложения», которые содержат только основные дороги и привязывают маршруты к наложению (или через несколько наложений - местный, метро, округ, штат, страна). Это приводит к быстрой, но иногда неэффективной маршрутизации.
Черепица
Черепица на вашей карте на самом деле не легкая. При меньшем увеличении вы можете визуализировать всю карту и разрезать ее. При больших увеличениях вы не можете рендерить все целиком (из-за ограничений памяти / пространства), поэтому вам нужно нарезать их на кусочки.
Вырезание линий на границах плиток, чтобы вы могли визуализировать отдельные плитки, приводит к получению не идеальных результатов - часто получается, что линии отображаются за пределами границы плиток (или, по крайней мере, сохраняются данные конца строки, хотя и выполняется останавливается, как только обнаруживает, что он упал с края) - это уменьшает ошибку, возникающую из-за того, что линии выглядят так, как будто они не совсем совпадают при перемещении по плиткам.
Вы увидите, о чем я говорю, когда будете работать над этой проблемой.
Найти данные, которые попадают в данную ячейку, тоже нетривиально - линия может иметь оба конца за пределами данной ячейки, но проходить через ячейку. Вам нужно будет проконсультироваться с графическими книгами об этом ( Книга Майкла Абраша является оригинальным справочником , свободно доступным сейчас по предыдущей ссылке). В то время как речь идет в основном об играх, здесь применимы окна, обрезка, ребра многоугольника, столкновения и т. Д.
Однако вы можете играть на более высоком уровне.
После того, как вы выполнили все вышеперечисленное (либо адаптировав существующий проект, либо выполнив вышеуказанное самостоятельно), вы можете поиграть с другими сценариями и алгоритмами.
Обратное геокодирование достаточно простое. Введите широту / долготу (или нажмите на карту) и получите ближайший адрес. Это научит вас, как интерпретировать адреса вдоль отрезков в данных TIGER.
Базовое геокодирование - сложная проблема. Написание анализатора адресов - это полезный и интересный проект, а затем преобразование его в широту / долготу с использованием данных TIGER нетривиально, но очень интересно. Начните с простого и малого, требуя точного соответствия имени и формата, а затем начните изучать «подобное» сопоставление и фонетическое сопоставление. Есть много исследований в этой области - посмотрите на проекты поисковых систем для некоторой помощи здесь.
Найти кратчайший путь между двумя точками - нетривиальная проблема. Существует множество алгоритмов для этого, большинство из которых запатентованы. Я рекомендую, если вы попробуете это, используйте простой алгоритм вашего собственного дизайна, а затем проведите некоторое исследование и сравните ваш дизайн с современным уровнем развития. Это очень весело, если вы увлекаетесь теорией графов.
Следование по пути и упреждающее указание не так просто, как кажется на первый взгляд. Учитывая набор инструкций со связанным массивом пар широта / долгота, «следуйте» маршруту, используя внешний вход (GPS или имитированный GPS), и разработайте алгоритм, который дает инструкции пользователю по мере приближения к каждому реальному пересечению. Обратите внимание, что из-за извилистых дорог и т. Д. Больше пар широта / долгота, чем инструкций, и вам необходимо определить направление движения и т. Д. Множество угловых случаев вы не увидите, пока не попробуете это реализовать.
Поиск точек интереса. Этот интересен - вам нужно найти текущее местоположение и все точки интереса (не являющиеся частью TIGER, создать свой собственный или получить другой источник) в пределах определенного расстояние (по прямой линии или расстояние, превышающее расстояние) от источника. Это интересно тем, что вам нужно преобразовать базу данных POI в формат, который легко найти в этом случае. Вы не можете потратить время, чтобы просмотреть миллионы записей, выполнить расчет расстояния (sqrt (x ^ 2 + y ^ 2)) и вернуть результаты. Вам нужен какой-то метод или алгоритм, чтобы сначала сократить объем данных.
Торговый продавец. Маршрутизация с несколькими пунктами назначения. Просто более сложная версия обычной маршрутизации.
Вы можете найти множество ссылок на многие проекты и источники информации на эту тему здесь .
Удачи, и, пожалуйста, опубликуйте все, что вы делаете, независимо от того, насколько рудиментарно или уродливо, чтобы другие могли извлечь выгоду!
-Adam