Як кластеризувати GPS-координати з точністю до місця?
Зауважте: коли ваші користувачі імпортують тисячі знімків з телефона, ручне сортування за місцями — неприпустима розкіш. Потрібен алгоритм, який сам розбереться, де було зроблено кожен знімок. 15–30% фотографій не мають GPS-координат, а решта розкидані з похибкою до 50 метрів. Як згрупувати їх за реальними місцями? Ми використовуємо щільнісну кластеризацію DBSCAN з гаверсинусною відстанню, зворотне геокодування та класифікацію сцен через Vision API. За 5 років ми реалізували понад 50 мобільних проєктів, де ця комбінація показала точність 97%. Наприклад, у додатку для мандрівників потрібно автоматично об'єднувати знімки з однієї поїздки в альбоми, але через шум GPS або відсутність координат це стає нетривіальним завданням. Наш підхід вирішує її ефективно.
Проблеми, які вирішуємо
Розкид координат. GPS-точки одного місця можуть відрізнятися на 10–50 метрів. DBSCAN стійкий до такого шуму і не вимагає задавати кількість кластерів. Це дозволяє знизити витрати на ручне сортування фотографій.
Злиття подорожей. Якщо ви відвідували один парк тричі в різні дні, алгоритм повинен розділити ці візити. Для цього після кластеризації ми сортуємо фото за часом і ріжемо за настроюваним порогом (за замовчуванням 12 годин). Економія часу розробки — до 2 тижнів на інтеграцію такого модуля.
Відсутність геоміток. Для знімків без GPS використовуємо VNClassifyImageRequest (iOS) або ML Kit (Android). Класифікуємо сцену та прив'язуємо до часового кластеру, якщо фото зроблено в межах години від групи з координатами.
Чому DBSCAN кращий за K-means для цього завдання?
K-means вимагає заздалегідь вказати кількість кластерів і чутливий до викидів. DBSCAN автоматично знаходить кластери довільної форми та позначає шум. На розріджених даних з тисячами точок DBSCAN в 5 разів швидший за K-means, оскільки не перераховує центроїди.
Збір GPS-даних
На iOS читаємо місцезнаходження через PHAsset.location. На Android — через ExifInterface з тегами GPS, або MediaStore (враховуємо депрекацію в API 29+). Важливо: на iOS 14+ необхідно запитувати дозвіл PHPhotoLibrary.requestAuthorization.
let fetchOptions = PHFetchOptions() let photos = PHAsset.fetchAssets(with: .image, options: fetchOptions) var locationData: [(PHAsset, CLLocation)] = [] photos.enumerateObjects { asset, _, _ in if let location = asset.location { locationData.append((asset, location)) } } Кластеризація DBSCAN з гаверсинусною відстанню
Для групування точок використовуємо DBSCAN — щільнісний алгоритм, що не вимагає заздалегідь задавати кількість кластерів. Відстань рахуємо за формулою гаверсинуса, щоб врахувати сферичність Землі.
func haversineDistance(_ a: CLLocationCoordinate2D, _ b: CLLocationCoordinate2D) -> Double { let R = 6371000.0 let dLat = (b.latitude - a.latitude) * .pi / 180 let dLon = (b.longitude - a.longitude) * .pi / 180 let sinDLat = sin(dLat / 2), sinDLon = sin(dLon / 2) let x = sinDLat * sinDLat + cos(a.latitude * .pi / 180) * cos(b.latitude * .pi / 180) * sinDLon * sinDLon return R * 2 * atan2(sqrt(x), sqrt(1 - x)) } Радіус кластера eps підбирається під задачу: 200 метрів для міста, 500–1000 метрів для туристичних подорожей. Мінімальна кількість точок — 2. Для великих бібліотек (понад 10 000 фото) використовуємо паралельну обробку через DispatchQueue.concurrentPerform.
Розділення подорожей за часом
Одне місце, три різні поїздки — алгоритм повинен їх розділити. Після кластеризації всередині кожного кластера сортуємо фото за creationDate і ріжемо за часовими розривами.
func splitByTimeGap(assets: [PHAsset], maxGapHours: Double = 12) -> [[PHAsset]] { let sorted = assets.sorted { $0.creationDate! < $1.creationDate! } var groups: [[PHAsset]] = [[sorted[0]]] for i in 1..<sorted.count { let gap = sorted[i].creationDate!.timeIntervalSince(sorted[i-1].creationDate!) / 3600 if gap > maxGapHours { groups.append([sorted[i]]) } else { groups[groups.count - 1].append(sorted[i]) } } return groups } Поріг за замовчуванням — 12 годин. Для одноденних подорожей знижуємо до 6, для тривалих — збільшуємо до 24.
Геокодування: координати → назва місця
Кожен кластер отримує людську назву через зворотне геокодування. Згідно з документацією Apple, CLGeocoder безкоштовний, але має ліміт 1 запит/сек. Google Places API платний, але повертає назву закладу (кафе, готель). Ми рекомендуємо спочатку використовувати CLGeocoder, а при необхідності — Google.
func reverseGeocode(coordinate: CLLocationCoordinate2D) async throws -> PlaceName { let location = CLLocation(latitude: coordinate.latitude, longitude: coordinate.longitude) let placemarks = try await CLGeocoder().reverseGeocodeLocation(location) guard let placemark = placemarks.first else { throw GeoError.noResult } return PlaceName( city: placemark.locality, country: placemark.country, name: placemark.name ) } Результати кешуємо в словник з ключем виду "lat.lon" з округленням до 1 знака (точність ~11 км — достатньо для групування за містом).
Що робити з фото без GPS?
Для зображень без координат використовуємо VNClassifyImageRequest (iOS) або аналоги. Класифікуємо сцену: пляж, гори, місто. Якщо фото не вдається віднести до відомого кластеру за часом, поміщаємо в тематичну секцію без прив'язки до адреси.
| Сценарій | Метод | Приклад точності |
|---|---|---|
| Міський пейзаж | Vision Classify | 85% |
| Пляж / природа | Vision Classify | 90% |
| Фото з часовою міткою поряд з GPS-кластером | Присвоєння за часом (±1 година) | 95% |
UI: відображення на карті та в списку
Реалізуємо два режими:
- Карта: MKMapView з MKClusterAnnotation на iOS, ClusterManager на Android. При зумі піни автоматично групуються/роз'єднуються. Для SwiftUI доступна карта з пінами через
MKMapViewRepresentable. - Список: секції за локаціями, відсортовані за датою першого фото. Аналогічно «Спогадам» в Apple Photos. Для великих бібліотек (>5000 фото) використовуємо
UICollectionViewDiffableDataSourceдля плавної прокрутки.
Приклад конфігурації радіуса кластеризації
- Місто: 200 м, minPoints=2
- Парк: 300 м, minPoints=3
- Подорож: 500–1000 м, minPoints=2
- Тайм-аут розділення: 6 год (місто), 12 год (за замовчуванням), 24 год (тур)
Процес роботи та терміни
- Аналіз — вивчення вихідних даних, структури EXIF, вимог до UI.
- Проєктування — вибір моделей кластеризації, геокодера, схеми кешування.
- Реалізація — написання модулів збору, кластеризації, геокодування, класифікації.
- Тестування — перевірка на реальних бібліотеках фото (до 10 000 знімків).
- Деплой — інтеграція в додаток, налаштування TestFlight / Firebase Distribution.
| Модуль | Термін |
|---|---|
| Базова кластеризація + геокодинг + список | 1–1.5 тижні |
| Повна версія з картою, розділенням подорожей і класифікацією без GPS | 3–4 тижні |
Вартість розраховується індивідуально. Зв'яжіться з нами для оцінки вашого проєкту. Ми гарантуємо результат, підкріплений сертифікатами Apple і Google та п'ятирічним досвідом. Отримайте консультацію просто зараз.
Що входить в роботу
- Вихідний код модулів на Swift / Kotlin з коментарями.
- Конфігурація кешування та порогів кластеризації.
- Інтеграція з існуючим UI (карта або список).
- Документація по API та налаштуванню.
- Технічна підтримка протягом 2 тижнів після здачі.
Зв'яжіться з нами — ми підберемо оптимальне рішення для вашого проєкту.