Пересекаються ли отрезки Опции

[RathaR]

Привет всем в Новом Году
Вспомнилась мне, задачка, которая фигурировала в цитате с баша, а именно:
"Даны координаты начала и конца двух отрезков, определить пересекаються ли они".
Вот я и задумался над этим... в голову пришел лишь один алгоритм:
1) У нас даны координаты 4 точек, запишем их в таком порядке, чтобы образовался полигон(для нахождения диагоналей).
2) Находим площадь этого полигона(половина произведения диагоналей на синус угла между ними).
3) Сравниваем полученый результат с половиной произведения наших отрезков на синус угла между ними.
4) Если площади совпали, значит отрезки являються диагоналями, а следовательно пересекаються, если нет, значит не перезекаються.
Если какая либо из заданых точек принадлежит другому отрезку, это ведь ничего не меняет, всерамно должен работать. Длинну отрезков по координатам найдем легко, углы между отрезками можна найти через модуль разности углов под которым расположен каждый из отрезков к горизонтали. А сами углы находим через арктангенс в паскале. Следовательно при реализаии проблем возникнуть не должно... но мне интересно, как еще можно решить эту задачу(желательно по проще)? Визуально-графический метод не предлагать

Сообщение отредактировано: RathaR - 1.01.2010 23:03

[RathaR]

Тут проскакивало несколько реализаций.. Искал?

Искал... не нашел ничего похожего...

А каков, собственно, критерий, что точки упорядочены нами именно в нужном порядке?

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

И чем, собственно, не устраивает наиболее очевидный алгоритм?

Не устраивает тем, что не додумался Геометрия, кажеться, 8 клас... уж и забыл как по двум точкам записать уравнение прямой погуглил - вспомнил.
Окей, а еще варианты решения этой задачи имеються?

Сообщение отредактировано: RathaR - 2.01.2010 21:07

[Lapp]

Искал... не нашел ничего похожего...

Вах! )) Отрезкм

[RathaR]

Вах! )) Отрезкм

Недосмотрел, бывает Хотя и не мудрено, судя по названию...
Но там ведь реализован метод через уравнения прямых, как описал andriano, так ведь? А других способов больше нет?

Сообщение отредактировано: RathaR - 4.01.2010 3:33

[andriano]

Но там ведь реализован метод через уравнения прямых, как описал andriano, так ведь?

Не знаю, не читал.

А других способов больше нет?

Другие способы, естественно есть. Вопрос в том, насколько они могут представлять интерес.
Например, если мы знаем о способе забивать гвозди молотком, всерьез рассматривать забивание гвоздей при помощи микроскопа вряд ли возможно.
Так же и здесь.
Предложенный способ, во-первых, реализует именно прямой метод, т.е. именно так, как мы бы делали это при помощи карандаша и бумаги. А во-вторых, он очень прост и нересурсоемок в реализации.
Как правило, множество способов решения задачи возникает там, где либо "прямой" метод труден в реализации или ресурсоемок, а иногда и невозможен, либо сама задача принципиально ресурсоемка, и в разных случаях могут проявляться достоинства того либо другого метода. Как, например, происходит в случае сортировки.
Здесь же просто отсутствуют предпосылки для изобретения других методов.