Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом

Приветствую, уважаемые эксперты!
Вопрос вот в чем: как можно определить пересекаются ли прямые. Т.е. у меня есть массив координат конечных точек прямых, и мне необходимо реализовать проверку на пересечение этих прямых. В инет не посылать, я там уже был, на сайте http://acm.dvpion.ru/article.asp?id_text=170 вставил код в свою прогу, но преподавателю так и не смог объяснить че где и почему, да и вообще он сказал что это не правильно. А на сайте http://netcode.ru/cpp/?artID=3984 алгоритм не могу реализовать в делфи, путаюсь, да и не могу понять что от куда брать (извините за мою тупость). Буду благодарен за пример хотябы для трех отрезков.

Вопрос задал: Ozz (статус: Посетитель) Вопрос отправлен: 29 мая 2009, 14:03 Состояние вопроса: открыт, ответов: 0.

Мини-форум вопроса

Вадим К (статус: Академик), 29 мая 2009, 14:15 [#1]: Первая программа решала поставленную задачу? Если да, то как она может быть неправильной? Просто некоторые преподаватели считают, что если они не понимают алгоритм, или алгоритм не тот, который они давали (а студент не может обяснить его), то даже если он решает задачу - он неверный. По второй ссылке приведено интересное размышление, хотя я советую попровать решить уравнение самостоятельно на листике и найти идею решения (она в конце концом всё равно сведётся к первой ссылке). Идея такая. любая прямая может быть задана двумя точками (x1,y1) и (x2,y2) либо в виде уравнения y=a*x+b. a и b могут быть рассчитаны по точками (формулы выводятся на листике, либо беруться в учебнике по геометрии). Дальше. Две прямые пересекаются, если есть такая точка, что она пренадлежит обоим прямым. Это легко сделать, подставив её в вышеприведённое уравнение прямой. Если это прямые, а не отрезки, то это уже достаточное условие. Я думаю, что вся загвоздка в том, что приведённое по первой ссылке решение работает для отрезков, а Вам надо для прямых. Галочка "подтверждения прочтения" - вселенское зло.

Ozz (статус: Посетитель), 29 мая 2009, 14:23 [#2]: По первой ссылке работает нормально, вроде и условие там если разобраться не сложное, уравнение прямой я тоже писал преподавателю, но по данному алгоритму этим даже и не пахнет. Из второй ссылки не пойму где взять tx и ty, как я понял это x0 и y0, но тоже не понятно как программно это определить. Найти надо не для прямых, а для отрезков, т.к. у них заданы начальная и конечная координаты!

Вадим К (статус: Академик), 29 мая 2009, 14:59 [#3]: а в условии написали "проверку на пересечение этих прямых". То что задано две точки, не означает, что это отрезок. А вот что обозначили через tx ty - я даже не знаю. наверно точку, но тогда как они пересечение считают... Галочка "подтверждения прочтения" - вселенское зло.

Ozz (статус: Посетитель), 29 мая 2009, 15:02 [#4]: Я вообще не настаиваю разбираться в тех примерах, если у кого есть свои варианты, пожалуйста, а то у меня курсовой долгом висит...

Мережников Андрей (статус: Абитуриент), 29 мая 2009, 17:33 [#5]: сначала на бумаге составляете решение математической задачи - определение уравнений прямых по заданным точкам на этих прямых. Затем получается система из двух линейных уравнений. Находите решение этой системы. Затем сравниваете найденные значения точки пересечения прямых с координатами начала и концов заданных отрезков. Если точка пересечения лежит внутри интервала, заданного координатами, то отрезки пересекаются. Чистая математика на самом деле.

Waserd (статус: Посетитель), 29 мая 2009, 19:05 [#6]: все намного проще) две прямые пересекаются, если они не параллельны!!! А параллельны они если (тут два варианта): 1. прямые заданы уравнением y=k*x+b. Тогда они параллельны если равны их коэффициенты k. 2. прямые заданы точками (x1,y1), (x2,y2) например. Тогда их вышеупомянутый коэффициент k считаем по формуле (y2-y1)/(x2-x1) и сводим решение к первому случаю. А вот о поиске их точек пересечения, я так понял, вопрос не стоит.

Мережников Андрей (статус: Абитуриент), 29 мая 2009, 20:46 [#7]: вопрос стоит не о пересечении прямых, а о пересечении отрезков этих прямых. Поэтому отличие коэффициентов при Х еще не означает, что отрезки пересекаются.

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.