Построение MKPolygon с использованием внешней границы набора координат. Как разделить координаты, попадающие по обе стороны от линии?

Я пытаюсь построить MKPolygon, используя внешнюю границу набора координат.

Насколько я могу судить, в Xcode нет функциональности для достижения этого (методы MKPolygon будут использовать все точки для построения многоугольника, включая внутренние точки).

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

Это берет внешние координаты широты и проводит линию между ними. Оттуда вы разделяете свои точки на основе этой линии на два подмножества и обрабатываете расстояние между внешними широчайшими, чтобы начать строить треугольники и исключать точки внутри, пока не останется внешняя граница.

Я могу найти внешние точки, просто взглянув на минимальную/максимальную широту, и могу провести линию между ними (MKPolyline), но как мне определить, попадает ли точка на одну или другую сторону этой MKPolyline?

Дополнительный вопрос заключается в том, существует ли проверка попаданий, чтобы определить, попадают ли точки в MKPolygon.

Спасибо!


xcode objective-c mapkit hittest convex-hull
person user1499007    schedule 24.10.2012    source источник
comment
Когда вы решите это, я уверен, что это будет популярный класс для других разработчиков. Вы должны опубликовать его и поделиться ссылкой здесь, когда вы закончите.   -  person Craig    schedule 25.10.2012
comment
Обязательно поделюсь, когда разберусь!   -  person user1499007    schedule 25.10.2012

Ответы (1)


arrow_upward
0
arrow_downward

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

Возникли проблемы с форматированием полного кода, поэтому мне придется просто указать свои шаги (вероятно, лучше, потому что мне нужно кое-что почистить!)

Я начал с массива MKPointAnnotations

1) У меня самая нижняя точка слева. Для этого я перебрал все точки и сравнил широту и долготу, чтобы получить самую низкую точку. Эта точка определенно будет в выпуклой оболочке, поэтому добавьте ее в NSMutableArray, в котором будут храниться наши точки выпуклой оболочки (cvp)

2) Получить все точки слева от самой низкой точки и перебрать их, вычислив угол cvp к остальным точкам слева. Точка, которая имеет наибольший угол, будет точкой, которую нужно добавить в массив.
atan(cos(lat1)sin(lat2)-sin(lat1)*cos(lat2)*cos(lon2-lon1), sin (lon2-lon1)*cos(lat2))

  • Для каждой найденной точки создайте треугольник (используя широту от новой точки и длину от предыдущей точки) и создайте многоугольник. Я использовал этот код для проверки попадания на полигон: BOOL mapCoordinateIsInPolygon = CGPathContainsPoint(polygonView.path, NULL, polygonViewPoint, NO); Если что-то было найдено в тесте попадания, удалите это из массива сравнения (все те, что слева от исходного массива, за вычетом очков корпуса)

  • Как только у вас будет как минимум 3 точки в вашем массиве cvp, постройте еще один многоугольник со всеми cvp в массиве и удалите все внутри, используя тест на попадание.

3) После того, как вы проработали все оставшиеся точки, создайте новый массив сравнения оставшихся точек, которые не были удалены или добавлены к корпусу.

4) Используйте те же вычисления и полигональные тесты, чтобы удалить точки и добавить найденные cvp. В конце у вас остается список точек, которые составляют вашу выпуклую оболочку.

person user1499007    schedule 27.10.2012
comment
У меня есть аналогичная проблема, которую я решил, используя снимок карты и преобразовав границу MKPolygon в путь для UIBeizierPath и нарисовав ее поверх снимка. Преимущество: я могу кэшировать эти снимки для быстрой перезагрузки, и это очень хорошо служит моей цели. DisAdv: я теряю гибкость карт и мне нужно много конвертировать между широтой/долготой и CGPoint. Мне было бы очень интересно, если бы вы когда-нибудь опубликовали свой код. с картами - person Numan Tariq; 11.12.2014