|
Иногда приходится решать следующую задачу: дано n неупорядочных точек на плоскости, необходимо найти их выпуклую оболочку. Представленный ниже метод решения этой задачи является вариантом алгоритма "заворачивания подарка". Время работы этого метода пропорционально m * n, где m - количество точек выпуклой оболочки. Существуют более быстрые методы, но этот алгоритм более прост для понимания и реализации, кроме того он эффективен в случае, когда m мало по сравнению с n. SuiteRef<Vector2d> & convexMN ( SuiteRef<Vector2d> & vert );Входной параметр - это ссылка на набор точек. Туда же будут записаны точки найденной выпуклой оболочки и их количество. Существует множество методов построения выпуклой оболочки за время O ( n log n ) в худшем случае. Вот один из них. Идея заключается в следующем. Вначале исходные точки упорядочиваются по возрастанию координаты X, а в случае равенства по Y. Для этой цели используется сортировка слияниями, которая сделает это за время O ( n log n ) в худшем случае: void mergeSort123 ( nat n, const Vector2d ** a, const Vector2d ** b ); После этого проводится прямая линия проходящая через первую и последнюю точки, и строятся выпуклые оболочки отдельно для точек лежащих ниже линии и выше. Это займёт время O ( n ). SuiteRef<Vector2d> & convexNlogN ( CArrRef<Vector2d> vert, SuiteRef<Vector2d> & res ); SuiteRef< nat > & convexNlogN ( CArrRef<Vector2d> vert, SuiteRef< nat > & res ); Алгоритм реализован в виде двух функций. В первой функции res - это ссылка на набор точек, а во второй - ссылка на набор индексов точек. Ссылки vert и res должны указывать на разные наборы. Этот алгоритм в моих экспериментах работал на случайных точках в 10 и более раз быстрее, чем предыдущий. Если исходные точки являются вершинами простого многоугольника, то в этом случае выпуклую оболочку можно построить за время O ( n ). Следующий алгоритм был взят с небольшими изменениями из книги "Вычислительная геометрия" (Препарата, Шеймос) пункт 4.1.4: SuiteRef<nat> & convexPolygon ( CArrRef<Vector2d> vert, SuiteRef<nat> & index ); DynArrRef<Vector2d> & convexPolygon ( CArrRef<Vector2d> vert, DynArrRef<Vector2d> & res ); DynArrRef<Vector2d> & convexPolygon ( DynArrRef<Vector2d> & vert ); Как обычно обход вершин полагается против часовой стрелки. Во втором варианте алгоритма указатели vert и res могут указывать на один массив. Описание шаблонов классов CArrRef, DynArrRef и SuiteRef находится здесь.
Исходники алгоритмов находятся в файле func2d.cpp. Наверх |