Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > набор линий и точек и расстояние между ними

Автор: mrgloom 4.8.2011, 13:04

вообщем есть набор отезков.
есть набор точек (контур).
с помощью алгоритма я этот контур накладываю на отрезки.
и мне надо определить какие отрезки не попали на контур (т.е. например на расстоянии L от линии нет ни 1 точки, значит линия не попала на контур)
так вот все отрезки против всех точек смотреть долго.
я использую quadtree для линий, и беру 1 точку и ее квадратную окрестность 2L и проверяю по поиску по дереву какие линии в этой области лежат,а потом ищу расстояние от точки до каждого отрезка.
может можно как то быстрее и я чего то не учел?

Автор: baldina 4.8.2011, 13:30

для выпуклого многоугольника можно использовать предобработку + двоичный поиск для определения принадлежности точки многоугольнику, O(logN).
поскольку требуется несколько определений для одного многоугольника, предобработка многоугольника будет оправдана.

Автор: mrgloom 4.8.2011, 14:02

не понял вы про какие многоугольники? которые составляют отрезки?
(они не обязательно составляют, скажем так это в основном прямоугольники и отрезки)
или вы про "контур" который составляют точки? (так он не обязательно выпуклый и может состоять из нескольких фигур,которые даже не замкнуты)

Автор: baldina 4.8.2011, 14:31

Цитата(mrgloom @ 4.8.2011, 13:04

)

есть набор точек (контур).

про этот
если невупуклый, то либо превратить его в набор выпуклых, либо использовать другой алгоритм, например http://www.mathworks.com/matlabcentral/fileexchange/10391-fast-points-in-polygon-test/content/poly_stuff/inpoly.m

Добавлено через 1 минуту и 26 секунд
вам ведь

Цитата(mrgloom @ 4.8.2011, 13:04

)

надо определить какие отрезки не попали на контур

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

Автор: mrgloom 4.8.2011, 15:10

Цитата(baldina @ 4.8.2011, 14:31

)

надо определить какие отрезки не попали на контур

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

не так.
этот "контур" уже наложен на группу отрезков и мне надо решить 2 задачи:
1.Найти отрезки которые далеко(если близко нету не одной точки контура)

2.посмотреть все ли точки контура хорошо легли на отрезки.
(для каждой точки контура, посмотреть есть ли на близком расстоянии отрезок)
(хотя тут наверно надо как то сложнее. учитывать направление)

пример для наглядности. зеленый контур, серые отрезки. красные рамки-контур плохо лег.
http://rghost.ru/16834841.view

Автор: baldina 4.8.2011, 16:37

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

Автор: mrgloom 5.8.2011, 09:13

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