Я немного не понимаю вас. Вот смотрите:

У нас 9 точек. Мы в данном случае проверяем 1 и 9 точки. Их ординаты 2 и 3 соответственно. Я понимаю ваш алгоритм так: если ординаты всех промежуточных точек меньше 2, то кривая обязательно пересечет линию. Аналогично, если ордината всех промежуточных точек больше 3, то кривая абсолютно точно не пересечет линию. Тут все верно, но у нас остаются неописанные алгоритмом области - справа внизу под красной линией, и слева вверху. Если точка попадает в эти треугольнички, алгоритм не будет знать как поступить.

Это сообщение отредактировал(а) Ground - 21.3.2009, 08:28

Не понял. Можете показать на графике?

Добавлено через 9 минут и 54 секунды


Если ордината хотя бы одной точки <= 2, то отрезок пересечёт кривую.

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


Вот тут точка 3 как раз попадает в эту область.

Но эт не работает.   Ибо если ордината 7ой точки будет 2.5, то отрезок всё равно пересечёт кривую.

Добавлено через 1 минуту и 56 секунд
Да, я уже понял. Хм. 

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

Добавлено через 3 минуты и 55 секунд
Причём надо вычислять только для синей/жёлтой областей. Т.е. сначала проверка в какую область попадает точка, если в синюю/жёлтую, то вычислять ординату отрезка в этой точке и сравнивать с ординатой текущей промежуточной точке. 

Тогда получается нужно брать коориднаты точек, через которые провели линию, получать из них коэффициенты A, B и C для уравнения прямой Ах+Ву+С=0. И потом подставлять абциссу в уравнение y=-(Ax+C)/B. После сравнивать 2 ординаты. И еще надо делать проверку на деление на 0.
Ну такой алгоритм намного проще, чем находить пересечение линий 
Но все равно, при 10к точек получается 50млн различных вариантов проведения линии. С таким колчиеством не уложиться даже в минуту работы программы.
Должно быть что-то еще, какой то неучтенный момент, который заметно упростит программу.

Хотя сначала лучше напишу, проверю скорость выполнения.

Неверно. Уравнение прямой проведённой через две точки выглядит следующим образом: 





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

W4FhLF, Вид уравнения не совсем удобен для такой задачи
Вот в таком виде y=A*x+B для всех таких прямых, проходящих через  точку (x1,y1) угол наклона такой прямой будет монотонной функцией от A. Так что экстремальные значения углов будут приходится на экстремальные значения А, тригонометрия становится не нужна.

ksnk, да вообще он приводится к виду:

y = (x - x1) * (y2 - y1) / (x2 - x1) + y1

Dыражение (y2 - y1) / (x2 - x1) находится один раз и получается в итоге(обозначив это выражение как a):

y = (x - x1) * a + y1

Раскрываем скобки:

x*a - x1*a + y1

Обозначаем -x1*a + y1 как b и получаем:

y = x*a + b

Ничего не напоминает? 


Это сообщение отредактировал(а) W4FhLF - 21.3.2009, 17:04

Всем спасибо за помощь!
Алгоритм, предложенный W4FhLF очень хорошо себя показал.

Это сообщение отредактировал(а) Ground - 22.3.2009, 13:31