Отсортировать вершины полигона...

Snickers · Post by **Snickers** » 26 Jan 2007 03:58

Вот такая вот проблемка образовалась на работе:

Имеется выпуклый полигон имеющий 4 вершины. Надо отсортировать вершины так, чтобы они шли против часовой стрелки. Размышляю вот уже какое-то время и решения не вижу. Буду благодарен за совет.

Заранее спасибо :beer:

venco · Post by **venco** » 26 Jan 2007 05:48

Code: Select all

typedef complex<double> V;

struct Before
{
    Before(V c) : c(c) {}
    V c;
    bool operator()(const V& a, const V& b) const
    {
        return ((a-c)*conj(b-c)).imag() < 0;
    }
};

void sort_poly(vector<V>& p)
{
    sort(p.begin()+1, p.end(), Before(p[0]));
}

Работает для любого выпуклого многоугольника.

Snickers · Post by **Snickers** » 26 Jan 2007 06:21

Спасибо venco. Пытаюсь осмыслить написанное

Можете коротко объяснить идею?

venco · Post by **venco** » 26 Jan 2007 15:39

Знак векторного произведения зависит от взаимной ориентации векторов.
(a*conj(b)).imag() и есть векторное произведение.
Теперь сортируем вершины относительно одной из вершин.

Snickers · Post by **Snickers** » 26 Jan 2007 16:03

venco wrote:Знак векторного произведения зависит от взаимной ориентации векторов.
(a*conj(b)).imag() и есть векторное произведение.
Теперь сортируем вершины относительно одной из вершин.

Спасибо.