IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Пересекаються ли отрезки
сообщение
Сообщение #1


Знаток
****

Группа: Пользователи
Сообщений: 346
Пол: Мужской
Реальное имя: Иван

Репутация: -  7  +


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

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


--------------------
Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик!
Я - системный аналитик!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(RathaR @ 1.01.2010 19:03) *
мне интересно, как еще можно решить эту задачу(желательно по проще)?
Тут проскакивало несколько реализаций.. Искал?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Сразу споткнулся на:
Цитата
запишем их в таком порядке, чтобы образовался полигон
А каков, собственно, критерий, что точки упорядочены нами именно в нужном порядке?
Боюсь, на один шаг в алгоритме это никак не тянет.

И чем, собственно, не устраивает наиболее очевидный алгоритм?
1. По координатам записываем уравнения прямых.
2. Решаем полученную систему уравнений, получая координаты точки пересечения прямых (если нет, значит, не пересекаются).
3. Узнаем, лежит ли точка пересечения внутри каждого из отрезков или вне его.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Знаток
****

Группа: Пользователи
Сообщений: 346
Пол: Мужской
Реальное имя: Иван

Репутация: -  7  +


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

Искал... не нашел ничего похожего...
Цитата
А каков, собственно, критерий, что точки упорядочены нами именно в нужном порядке?

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

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

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

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


--------------------
Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик!
Я - системный аналитик!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Я.
****

Группа: Пользователи
Сообщений: 809
Пол: Мужской
Реальное имя: Саша

Репутация: -  11  +


100пудово решал бы именно так, как предложил andriano. Просто самый простой и надежный способ.
Но, раз стоит такой вопрос:
Цитата(RathaR @ 2.01.2010 16:05) *
Окей, а еще варианты решения этой задачи имеються?

могу предложить извращенный вариант lol.gif используя кучу условий и записать решение в один длинный рядок. как-то так:
begin
writeln( а вот здесь сделать проверку всех условий используя and,or,not,xor );
end.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Знаток
****

Группа: Пользователи
Сообщений: 346
Пол: Мужской
Реальное имя: Иван

Репутация: -  7  +


Цитата(sheka @ 2.01.2010 19:30) *

могу предложить извращенный вариант lol.gif используя кучу условий и записать решение в один длинный рядок. как-то так:

А какие условия проверять, то?


--------------------
Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик!
Я - системный аналитик!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(RathaR @ 2.01.2010 17:05) *
Искал... не нашел ничего похожего...
Вах! )) Отрезкм


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Знаток
****

Группа: Пользователи
Сообщений: 346
Пол: Мужской
Реальное имя: Иван

Репутация: -  7  +


Цитата(Lapp @ 3.01.2010 23:44) *

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

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

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


--------------------
Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик!
Я - системный аналитик!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(RathaR @ 3.01.2010 23:33) *
Недосмотрел, бывает rolleyes.gif Хотя и не мудрено, судя по названию...
Мало ли какое может быть окончание! Может, это какой-нить "мучительный" падеж.. Именно поэтому нужно задавать не все слово, а маску: "+пересе* +отрез*".

Цитата
Но там ведь реализован метод через уравнения прямых, как описал andriano, так ведь?
не помню..
Цитата
А других способов больше нет?
Тебе нужно "в шашечку" или ехать? (С) smile.gif
Я думаю, это самый простой способ.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Цитата(RathaR @ 3.01.2010 23:33) *

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


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Цитата
1. По координатам записываем уравнения прямых.


А как по координатам можно записать уравнение прямой (как я понял, речь идёт о y=kx+b)? Ходил по ссылке Lapp'а, там есть решение, но вроде как в них проверка на пересечение как-то по другому, или я не туда смотрю..


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Знаток
****

Группа: Пользователи
Сообщений: 346
Пол: Мужской
Реальное имя: Иван

Репутация: -  7  +


Цитата(Unconnected @ 4.01.2010 23:10) *

А как по координатам можно записать уравнение прямой (как я понял, речь идёт о y=kx+b)?

Ага, y=kx+b выводиться из (y1-y2)x+(x2-x1)y+(x1*y2-x2*y1).
Википедия

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


--------------------
Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик!
Я - системный аналитик!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Ага, спасибо, википедия лучше гугла иногда)


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Цитата(Unconnected @ 4.01.2010 22:42) *

википедия лучше гугла
Это в перлы.

Нет, можно, конечно, утверждать, что автомобиль лучше автомагазина...

Возможно, ты будешь удивлен, но я, чтобы почитать википедию, просто набираю в строке поиска гугла наряду с ключевыми словами еще слово "википедия".
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Знаток
****

Группа: Пользователи
Сообщений: 346
Пол: Мужской
Реальное имя: Иван

Репутация: -  7  +


Цитата(andriano @ 5.01.2010 12:32) *

Это в перлы.

Да ладно, чего к словам то придираться... я думаю что мысль все уловили верно...
Цитата

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

А я так ценю википедию, что даже посвятил ей закладку в браузере smile.gif
Поэтому мои трудозатраты, на это дело, несколько меньше rolleyes.gif

З.Ы. Не по теме это все...

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


--------------------
Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик!
Я - системный аналитик!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Цитата(andriano @ 2.01.2010 11:13) *

2. Решаем полученную систему уравнений, получая координаты точки пересечения прямых (если нет, значит, не пересекаются).


Ага разбирая отдельно случай вертикальных отрезков, горизонтальных, нулевого определитеся системы. Это отвратительное решение в лоб.
Как делал бы я.
Задаём прямую, содержащую отрезок 1 в виде ax+by+c = 0.
Подставляем в левую часть концы второго отрезка. Если получились числа одного знака - то не пересекаются. Если разного, то потом делаем то же самое, но наоборот - концы первого отрезка подставляем в уравнение для второго. Если опять разного знака - то пересекаются.


Добавлено через 2 мин.
Выглядело это примерно так:


function Intersect(X11, Y11, X21, Y21, X12, Y12, X22, Y22: double): boolean;
var
d11, d21, d12, d22: double;
begin
d11 := (x22 - x11) * (y12 - y11) - (x12 - x11) * (y22 - y11);
d21 := (x22 - x21) * (y12 - y21) - (x12 - x21) * (y22 - y21);
d12 := (x21 - x12) * (y11 - y12) - (x11 - x12) * (y21 - y12);
d22 := (x21 - x22) * (y11 - y22) - (x11 - x22) * (y21 - y22);
Result := (((d11 > 0) and (d21 < 0)) or ((d11 < 0) and (d21 > 0)))
and (((d12 > 0) and (d22 < 0)) or ((d12 < 0) and (d22 > 0)));
end;



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

Добавлено через 4 мин.
Цитата(Lapp @ 3.01.2010 22:44) *

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


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

Добавлено через 1 мин.
А ещё надо разобрать случай, когда отрезки ПОЧТИ вертикальны (да, да, делить на ПОЧТИ ноль тоже запрещено), и ПОЧТИ параллельны.
Короче, мой вариант лучше. И даже операция деления нигде не используется.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


И название темы поправте, а то глаза режеть.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Я.
****

Группа: Пользователи
Сообщений: 809
Пол: Мужской
Реальное имя: Саша

Репутация: -  11  +


Цитата(TarasBer @ 5.01.2010 14:53) *

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

Класс! +1 good.gif
Мне подобная идея сразу пришла в голову, только не получалось с реализацией, т.к. думал реализовать разницу знаков через вертикальную и горизонтальную прямые, которые бы проходили через одну из точек отрезка...А тут оказывается все намного проще)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(TarasBer @ 5.01.2010 17:20) *
И название темы поправте, а то глаза режеть.
"Пятьдесят прОцентов наших дОцентов говорят пОртфель"? (С) smile.gif
TarasBer, выразись, пожалуйста, конкретнее, какую именно тему ты имеешь в виду. И, желательно, с волшебным словом.. yes2.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Цитата(Lapp @ 6.01.2010 0:00) *
TarasBer, выразись, пожалуйста, конкретнее, какую именно тему ты имеешь в виду. И, желательно, с волшебным словом.. yes2.gif

Прежде, чем выделять красным предполагаемую ошибку, ты бы внимательно перечитал название темы.
Умба-карамба! (это волшебное слово такое)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 2:27
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name