Пересекаються ли отрезки |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Пересекаються ли отрезки |
RathaR |
Сообщение
#1
|
Знаток Группа: Пользователи Сообщений: 346 Пол: Мужской Реальное имя: Иван Репутация: 7 |
Привет всем в Новом Году
Вспомнилась мне, задачка, которая фигурировала в цитате с баша, а именно: "Даны координаты начала и конца двух отрезков, определить пересекаються ли они". Вот я и задумался над этим... в голову пришел лишь один алгоритм: 1) У нас даны координаты 4 точек, запишем их в таком порядке, чтобы образовался полигон(для нахождения диагоналей). 2) Находим площадь этого полигона(половина произведения диагоналей на синус угла между ними). 3) Сравниваем полученый результат с половиной произведения наших отрезков на синус угла между ними. 4) Если площади совпали, значит отрезки являються диагоналями, а следовательно пересекаються, если нет, значит не перезекаються. Если какая либо из заданых точек принадлежит другому отрезку, это ведь ничего не меняет, всерамно должен работать. Длинну отрезков по координатам найдем легко, углы между отрезками можна найти через модуль разности углов под которым расположен каждый из отрезков к горизонтали. А сами углы находим через арктангенс в паскале. Следовательно при реализаии проблем возникнуть не должно... но мне интересно, как еще можно решить эту задачу(желательно по проще)? Визуально-графический метод не предлагать Сообщение отредактировано: RathaR - -------------------- Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик! Я - системный аналитик! |
RathaR |
Сообщение
#2
|
Знаток Группа: Пользователи Сообщений: 346 Пол: Мужской Реальное имя: Иван Репутация: 7 |
Цитата Тут проскакивало несколько реализаций.. Искал? Искал... не нашел ничего похожего... Цитата А каков, собственно, критерий, что точки упорядочены нами именно в нужном порядке? Непонял... нам необходимо получить последовательность точек в таком порядке, чтобы последовательно соединяя получить полигон, а учитывая то, что точек всего 4, мы сможем вырать в этой последовательности две диагонали, и соответственно проверить, являються ли наши отрезки, что заданы в условиии, диагоналями, или сторонами полигона. Цитата И чем, собственно, не устраивает наиболее очевидный алгоритм? Не устраивает тем, что не додумался Геометрия, кажеться, 8 клас... уж и забыл как по двум точкам записать уравнение прямой погуглил - вспомнил. Окей, а еще варианты решения этой задачи имеються? Сообщение отредактировано: RathaR - -------------------- Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик! Я - системный аналитик! |
sheka |
Сообщение
#3
|
Я. Группа: Пользователи Сообщений: 809 Пол: Мужской Реальное имя: Саша Репутация: 11 |
100пудово решал бы именно так, как предложил andriano. Просто самый простой и надежный способ.
Но, раз стоит такой вопрос: Окей, а еще варианты решения этой задачи имеються? могу предложить извращенный вариант используя кучу условий и записать решение в один длинный рядок. как-то так: begin |
Текстовая версия | 3.05.2024 18:39 |