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

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

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

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

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

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

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

Спасибо!

1 3
objective-c mapkit convex-hull

1 ответ:

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

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

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

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

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

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

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

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

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

0