crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )

 
Ответить в данную темуНачать новую тему
> Ближайшие отрезки к точке.
ViGOur
  опции профиля:
сообщение 6.2.2013, 16:46
Сообщение #1


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


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

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

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

p.s. сам ломаю голову как это сделать. :)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Litkevich Yuriy
  опции профиля:
сообщение 6.2.2013, 16:55
Сообщение #2


разработчик РЭА
*******

Группа: Сомодератор
Сообщений: 9669
Регистрация: 9.1.2008
Из: Тюмень
Пользователь №: 64

Спасибо сказали: 807 раз(а)




Репутация:   94  


а что из себя представляют линии?
У них есть абсолютные координаты или только длины?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 6.2.2013, 16:58
Сообщение #3


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


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

Поправил немного задачу...
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 6.2.2013, 17:38
Сообщение #4


Профессионал
*****

Группа: Модератор
Сообщений: 1611
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 219 раз(а)




Репутация:   12  


я не понимаю, в чём тут смысл задачи. если координаты известны - сортируем и точки, и линии по осям - и вперёд, с песнями. или тут какой-то подвох?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 6.2.2013, 18:46
Сообщение #5


фрилансер
******

Группа: Участник
Сообщений: 2939
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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

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

upd

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

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

Сообщение отредактировал Алексей1153 - 6.2.2013, 18:46
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 6.2.2013, 21:50
Сообщение #6


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


Цитата(Iron Bug @ 6.2.2013, 18:38) *
я не понимаю, в чём тут смысл задачи. если координаты известны - сортируем и точки, и линии по осям - и вперёд, с песнями. или тут какой-то подвох?
Тогда нужно будет и углы относительно точки рассчитывать, все линии по разному могут быть расположены, к тому же есть линии обозначающие положение дверей и окон...

Цитата(Алексей1153 @ 6.2.2013, 19:46) *
ну так это - строишь через точку нормаль к прямой, находишь пересечение , а потом длину отрезка нормали
Все то же, как и в моем ответе Iron Bug.

Я думал об этом варианте (в принципе вы предложили одно и то же, но по разному), но мне он кажется не оптимальным, хотя может это из-за того, что вечер и утром я все же передумаю! :)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 7.2.2013, 9:35
Сообщение #7


Профессионал
*****

Группа: Модератор
Сообщений: 1611
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 219 раз(а)




Репутация:   12  


Цитата(ViGOur @ 7.2.2013, 0:50) *
Все то же, как и в моем ответе Iron Bug.

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


Сообщение отредактировал Iron Bug - 7.2.2013, 9:41
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 7.2.2013, 10:47
Сообщение #8


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


Iron Bug, я примерно понял что ты имеешь ввиду, сейчас попробую как это будет!
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 7.2.2013, 14:51
Сообщение #9


Мастер
******

Группа: Модератор
Сообщений: 3296
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


В принципе и правда, как предложила 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
  опции профиля:
сообщение 7.2.2013, 20:57
Сообщение #10


фрилансер
******

Группа: Участник
Сообщений: 2939
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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


даже если 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
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

Ответить в данную темуНачать новую тему
Теги
Нет тегов для показа


1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 28.3.2024, 19:09