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

и задачки для интервью.
Snickers
Уже с Приветом
Posts: 807
Joined: 16 Aug 2001 09:01
Location: Boston, MA

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

Post by Snickers »

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

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

Заранее спасибо :beer:
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

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
Уже с Приветом
Posts: 807
Joined: 16 Aug 2001 09:01
Location: Boston, MA

Post by Snickers »

Спасибо venco. Пытаюсь осмыслить написанное :D
Можете коротко объяснить идею?
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Знак векторного произведения зависит от взаимной ориентации векторов.
(a*conj(b)).imag() и есть векторное произведение.
Теперь сортируем вершины относительно одной из вершин.
Snickers
Уже с Приветом
Posts: 807
Joined: 16 Aug 2001 09:01
Location: Boston, MA

Post by Snickers »

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


Спасибо. :fr:

Return to “Головоломки”