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



Это сообщение отредактировал(а) mrgloom - 4.8.2011, 13:56

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


Присоединённый файл ( Кол-во скачиваний: 2 )
 point_inclusion_handout.pdf 71,92 Kb

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

про этот
если невупуклый, то либо превратить его в набор выпуклых, либо использовать другой алгоритм, например этот

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

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

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


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



Это сообщение отредактировал(а) mrgloom - 4.8.2011, 15:15

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

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

Это сообщение отредактировал(а) mrgloom - 5.8.2011, 09:14