Здравствуйте, Дмитрий!
Увы, Вы не интересуетесь задачей, поэтому уточнить некоторые детали не представляется возможным.
Поэтому предлагаю следующий вариант:
В начале, предположим допустимость отсутствия точек из данного множества во всех вершинах четырехугольников,
обязательным является только то, что все точки будут внутри или в большинстве вершин. Это послабление условия необходимо только
для числа точек меньшего 4-х, ровно 5 и когда все точки внутри треугольника. В последнем случае задача разделения точек продолжает оставаться не намного проще исходной.
Итак, алгоритм следующий:
1) Если точек меньше 3, дополняем до 4
2) Находим при помощи алгоритма Грэхема точки, являющимися последовательными вершинами многоугольника, являющего оболочкой для всех точек.
3) Если вершин четное число:
а) берем 4 первых точки
б) оставляем первую и последнюю, добавляем две
в) и так, пока не дойдем до последней
4) Если вершин нечетное число и больше трех:
а) Если есть хоть одна дополнительная вершина внутри многоугольника,
то добавляем еще одну любую точку так, что внутри треугольника, состоящего из двух вершин многоугольника и этой точки нет других точек
Т.о. получили четное число вершин. Разбиваем на четырехугольники, начиная с этой добавленной, как в пункте 3)
б) Если внутри нет точек и вершин больше 5, то разбиваем аналогично 3), только для последнего четырехугольника оставляем от предпоследнего только одну точку, а не две последний будет иметь только одну общую точку)
в) Если у нас ровно 5 точек в вершинах пятиугольника, то добавляем любую точку, получаем шестиугольник, применяем 3)
5) Если три вершины, то добавляем одну дополнительную точку так, чтобы получился четырехугольник