Ближайшие отрезки к точке. Опции

[ViGOur]

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

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

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

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

[Litkevich Yuriy]

а что из себя представляют линии?
У них есть абсолютные координаты или только длины?

[ViGOur]

Линии разумеется имеют координаты по двум точкам: начало(x, y), конец(x,y).

Поправил немного задачу...

[Iron Bug]

я не понимаю, в чём тут смысл задачи. если координаты известны - сортируем и точки, и линии по осям - и вперёд, с песнями. или тут какой-то подвох?

[Алексей1153]

да, чего-то в ТЗ не хватает )

берёшь и строишь все линии, а зачем нужны точки внутри кабинетов - непонятно

upd

о, название не сразу увидел - " Ближайшие отрезки к точке."

ну так это - строишь через точку нормаль к прямой, находишь пересечение , а потом длину отрезка нормали. Где будет мЕньшая по длине нормаль - та линия ближе к точке

Сообщение отредактировал Алексей1153 - 6.2.2013, 18:46

[ViGOur]

я не понимаю, в чём тут смысл задачи. если координаты известны - сортируем и точки, и линии по осям - и вперёд, с песнями. или тут какой-то подвох?

Тогда нужно будет и углы относительно точки рассчитывать, все линии по разному могут быть расположены, к тому же есть линии обозначающие положение дверей и окон...

ну так это - строишь через точку нормаль к прямой, находишь пересечение , а потом длину отрезка нормали

Все то же, как и в моем ответе Iron Bug.

Я думал об этом варианте (в принципе вы предложили одно и то же, но по разному), но мне он кажется не оптимальным, хотя может это из-за того, что вечер и утром я все же передумаю!

[Iron Bug]

Все то же, как и в моем ответе Iron Bug.

при чём тут система координат? нормаль - чисто геометрическое понятие. и строится она по формуле. и от системы координат не зависит.
а чтобы сразу отсечь потенциально "далёкие" объекты, я предложила сначала отсортировать линии. а если там ещё и "окна" и всякая лажа - то она отсеивается ещё до всех манипуляций с вычислением расстояний, чтобы не парить моск. если стена неотличима от окна - это проблема постановки задачи.


Сообщение отредактировал Iron Bug - 7.2.2013, 9:41

[ViGOur]

Iron Bug, я примерно понял что ты имеешь ввиду, сейчас попробую как это будет!

[ViGOur]

В принципе и правда, как предложила Iron Bug, подходит, но для этого чертеж должен быть правильным!
Чтобы удовлетворять условию:

foreach( ... )
{
     ...
    if( (pos.y() > lineP1.y() && pos.y() < lineP2.y()) ||
        (pos.y() > lineP2.y() && pos.y() < lineP1.y()))
    {
        // Лево
        if( pos.x() > lineP1.x() && pos.x() > lineP2.x() )
        {
        // Здесь еще проверки, прошлая линия меняется новой или не меняется
        }
        // Право
        if( pos.x() < lineP1.x() && pos.x() < lineP2.x() )
        {
        // Здесь еще проверки, прошлая линия меняется новой или не меняется
        }
    }

    if( (pos.x() > lineP1.x() && pos.x() < lineP2.x()) ||
        (pos.x() > lineP2.x() && pos.x() < lineP1.x()))
    {
        // Верх
        if( pos.y() > lineP1.y() && pos.y() > lineP2.y() )
        {
        // Здесь еще проверки, прошлая линия меняется новой или не меняется
        }
        // Низ
        if( pos.y() < lineP1.y() && pos.y() < lineP2.y() )
        {
        // Здесь еще проверки, прошлая линия меняется новой или не меняется
        }
    }
}

Сразу говорю верх и них я не перепутал, это такая система координаты у QGraphicsScene

[Алексей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