Всем привет!
Есть отрезок, рядом с которым лежит множество точек. Мне нужно найти те точки, которые лежат в пределах концов отрезка, т.е. они могут лежать и справа и слева от отрезка, но не могут выходить так сказать вперед и назад от него.
Сейчас я делаю так - нахожу центр отрезка и ищу точки, которые лежат не дальше, чем половина длины этого отрезка. Т.е. получается, что в поиске участвуют точки, лежащие в окружности, построенной от центра отрезка с радиусом, равным половине длины отрезка.
Вот кусок это процедуры:

Но при этом теряются точки, которые лежат в пределах отрезка, но удалены от него вправо или влево более чем на половину длины отрезка.
Вот картинка, на которой показано все это в графике:

Розовая линия - линия, которую я делю по условию, для получения анализируемого отрезка;
Белые, красные и коричневые точки - те самые точки, которые надо посчитать;
Красная окружность - показывает ту область, в которой ищет точки мой алгоритм;
Зеленые линии показывают тот диапазон точек, которые реально попадают в так сказать пределы отрезка.

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

Я так понимаю мне надо анализировать не в окружности, а например строить параллелограмм и анализировать в нем, но как это сделать я не знаю.
Очень прошу помощи! 

Наверно лучше вопрос задать в разделе http://forum.vingrad.ru/forum/s/ab518839f7...mp;showforum=13

http://algolist.manual.ru/maths/geom/distance/pointline.php
По ссылке описано как искать расстояние до отрезка, я сам не вникал но может поможет.


Это сообщение отредактировал(а) Frees - 8.8.2012, 13:09

К сожалению расстояние до отрезка не поможет - это не поможет отсечь ненужные точки.

Тут вопрос больше геометрии наверно - как построить параллелограмм (если я вообще прав) имея только одну его сторону, т.е. как его рассчитать в delphi. Есть формулы параллельного переноса - но и как их реализовать я не понимаю.

А как ты собрался параллелограмм строить? для этого либо угол нужен, либо 3я точка.  Тогда все легко решается. 

Да я вот весь день сижу и думаю как его строить. Даже на листочке рисую, чтобы хоть как-то себе это представить. Пока ничего в голову не приходит. Я после того как придумал этот подход с окружностью больше ничего "гениального" не смог сгенерировать.

Если, отрезок AB, а точки, например C1, C2,.., Сn
То ищешь скалярные произведения между парами векторов ACn и AB; BCn и BA. Если скалярные произведения > 0, то точка расположена между вершинами, если одни из них равно 0 , то прям над одной из вершин, если хоть одно произведение < 0, тогда за границами.

Это сообщение отредактировал(а) rodnover - 8.8.2012, 16:07

Огромное спасибо, за подсказку!!! Реально помогло!!! От всей души благодарю!

Всегда пожалуйста, обращайтесь. 

Товарищи, прошу помощи еще раз.

Существует ли способ найти точки лежащие, на определенном расстоянии до кривой?
Что имеем
1) сотни тысяч или миллионы точек с координатами X,Y,Z;
2) несколько сотен (максимум тысяч) кривых, состоящих из нескольких десятков вертексов также с трехмерными координатами.

Сейчас для поиска точек, которые лежат на заданном расстоянии от каждой из кривых я использую предложенный выше метод, мизерно доработанный мною - кривую рассматриваю как набор отрезков, для которых и идет поиск точек. Расстояние от отрезка до точки я определяю как высоту треугольника, образованного концами отрезка и анализируемой точкой. Понятно, что работает это просто супер медленно (если в файле 1 000 000 точек, а в кривой 40 отдельных отрезков, то для поиска приходятся проводить 40 000 000 вычислений).

Погуглил на счет расстояния от точки до кривой - ничего путного не нашел, поэтому и обращаюсь за помощью к вам.

Буду очень благодарен за любую помощь!

Пример моего кода:

Dementor, мне кажется, что для поиска алгоритма чего - либо, в том числе и для "...способ найти точки лежащие, на определенном расстоянии до кривой.." нужно зайти в раздел Алгоритмы (http://forum.vingrad.ru/forum/tech-algorithm-techique-method.html).
Разобравшись там с алгоритмом в принципе, если нужно, заходишь на этот подфорум для вопросов по реализации алгоритма на языке Дельфи.

Да, наверно вы правы туда и пойду. Спасибо за совет!
Мне реализовать не так сложно, а вот придумать сам алгоритм...
Пойду туда!