image
Программа для построения выпуклой оболочки множества точек двумерной плоскости. Используется алгоритм Киркпатрика («разделяй и властвуй») для уменьшения сложности задачи. При малом числе точек для построения оболочки используется алгоритм Джарвиса. При большом числе точек, используется рекурсивный алгоритм вертикального или горизонтального разделения исходного множества точек на два не пересекающихся подмножества примерно равного размера. Соответственно, при слиянии оболочек используется алгоритм слияния не пересекающихся оболочек. Программа написана на C++/Qt.