Получить вогнутый корпус в mapKit

Question

Использование Swift и apple mapKit Я бы хотел рассчитать вогнутый корпус из GPS-координат. У меня есть массив CLLocation (широта, долгота), определяющий полилинию. Для геообработки маршрута я рассчитал для каждой 2d-точки в полилинии все возможные широты и долготы с расстоянием до n метров. В этот момент я хотел бы рассчитать вогнутую оболочку этого множества точек. Я не могу найти никакой информации о том, как вычислить вогнутый корпус из GPS-координат. Может ли кто-нибудь предложить мне учебник?

Answer 1

Я никогда не слышал термин вогнутые корпуса, пока я не прочитал ваш вопрос, поэтому я погубил его. Я нашел ссылки на несколько алгоритмов для вогнутых корпусов.

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

Если все точки, с которыми вы работаете, находятся в пределах 100 км друг от друга или около того, вы можете упростить задачу и преобразовать ваши lat/longs в декартовы координаты. Все, что вам нужно сделать, это выяснить расстояние между градусами долготы на текущей широте.

Как только вы преобразуете свои точки в декартовые координаты, это становится проблемой вогнутого корпуса.

Если вы имеете дело с большими регионами и хотите разрешить кривизну земли, у вас есть гораздо более сложная проблема.

Answer 2

This Бумага должна быть полезна вам. Я использовал алгоритм из этой статьи для реализации моей библиотеки hull.js.

Также вы можете триангулировать свою форму через Delaunay triangulation, а затем удалить граничные края, такие как here.