Ближайшие отрезки к точке. Опции Подписка на тему Сообщить другу Версия для печати Скачать тему Подписка на этот форум Режимы отображения Древовидный Переключить на: Стандартный Переключить на: Линейный

[ViGOur]

Исходные данные:
Массив линий ( начало(x, y), конец(x, y) )
Массив точек (x, y)

Массив линий это план этажа, кабинеты, коридоры, двери, окна и ... Другими словами все то, что архитектор начертил бы на бумаге.
Точки - координаты внутри кабинетов (только внутри кабинетов).

Нужно построить кабинеты имея исходные данные!

p.s. сам ломаю голову как это сделать.

[Алексей1153]

по мне - так не париться с сортировкой, посчитается моментально чисто на нормалях. На первое время пойдёт, а потом уж можно подумать об оптимизации сортировкой


даже если 1000 отрезков и 1000 точек, будет миллион комбинаций.

компилировал, но не тестировал )

typedef std::vector<QLineF> td_lines;
typedef std::vector<QPointF> td_points;
typedef std::map<td_points::const_iterator,td_lines::const_iterator> td_point_and_line;

void FindNearestLinesForPoints
(
     const td_lines& _lines//массив линий
    ,const td_points& _points//массив точек
    ,td_point_and_line& _point_and_line//ассоциация точек с ближайшей линией
)
{
    _point_and_line.clear();

    for(td_points::const_iterator itP=_points.begin();itP!=_points.end();itP++)
    {
        float min_dist=-1;//это модуль расстояния, -1 показывает незаполненность

        const QPointF& P=*itP;

        for(td_lines::const_iterator itL=_lines.begin();itL!=_lines.end();itL++)
        {
            const QLineF& L=*itL;

            //нормаль для L, начинающиющаяся из точки P
            const QLineF n=L
                .translated(-L.p1()+P)//линию пускаем из точки
                .normalVector()//находим нормаль
;

            //ищем точку пересечения нормали и линии L
            QPointF cross;
            if(L.intersect(n,&cross)!=L.NoIntersection)
            {
                //расстояние
                const float dist=QLineF(P,cross).length();

                if(min_dist<0 || dist<min_dist)
                {
                    //новая минимальная длина
                    min_dist=dist;

                    //запоминаем линию для точки
                    _point_and_line[itP]=itL;
                }
            }
            else
            {
                //сюда можем попасть только в случае, если линия вырождена в точку
            }
        }
    }

    //_lines + _points + _point_and_line - искомая ассоциация
}

Сообщение отредактировал Алексей1153 - 7.2.2013, 21:01