Версия для печати темы

Автор: RathaR 1.01.2010 23:03

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

Автор: Lapp 1.01.2010 23:45

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

Автор: andriano 2.01.2010 15:13

Сразу споткнулся на:

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

И чем, собственно, не устраивает наиболее очевидный алгоритм?
1. По координатам записываем уравнения прямых.
2. Решаем полученную систему уравнений, получая координаты точки пересечения прямых (если нет, значит, не пересекаются).
3. Узнаем, лежит ли точка пересечения внутри каждого из отрезков или вне его.

Автор: RathaR 2.01.2010 21:05

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

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


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

Автор: sheka 2.01.2010 22:30

100пудово решал бы именно так, как предложил andriano. Просто самый простой и надежный способ.
Но, раз стоит такой вопрос:

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

begin
writeln( а вот здесь сделать проверку всех условий используя and,or,not,xor );
end.

Автор: RathaR 3.01.2010 17:21

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

Автор: Lapp 4.01.2010 2:44

Вах! )) http://forum.pascal.net.ru/index.php?s=&showtopic=16693&view=findpost&p=98157

Автор: RathaR 4.01.2010 3:33

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

Автор: Lapp 4.01.2010 7:38

Мало ли какое может быть окончание! Может, это какой-нить "мучительный" падеж.. Именно поэтому нужно задавать не все слово, а маску: "+пересе* +отрез*".

не помню..
Тебе нужно "в шашечку" или ехать? (С)
Я думаю, это самый простой способ.

Автор: andriano 4.01.2010 15:41

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

Автор: Unconnected 5.01.2010 2:10

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

Автор: RathaR 5.01.2010 2:18

Ага, y=kx+b выводиться из (y₁-y₂)x+(x₂-x₁)y+(x₁*y₂-x₂*y₁).
http://ru.wikipedia.org/wiki/Уравнения_прямой#.D0.A4.D0.BE.D1.80.D0.BC.D1.83.D0.BB.D1.8B

Автор: Unconnected 5.01.2010 2:42

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

Автор: andriano 5.01.2010 15:32

Это в перлы.

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

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

Автор: RathaR 5.01.2010 18:23

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

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

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

Автор: TarasBer 5.01.2010 19:53

Ага разбирая отдельно случай вертикальных отрезков, горизонтальных, нулевого определитеся системы. Это отвратительное решение в лоб.
Как делал бы я.
Задаём прямую, содержащую отрезок 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 мин.


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

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

Автор: TarasBer 5.01.2010 21:20

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

Автор: sheka 5.01.2010 22:17

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

Автор: Lapp 6.01.2010 4:00

"Пятьдесят прОцентов наших дОцентов говорят пОртфель"? (С)
TarasBer, выразись, пожалуйста, конкретнее, какую именно тему ты имеешь в виду. И, желательно, с волшебным словом..

Автор: andriano 6.01.2010 4:03

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

Автор: Lapp 6.01.2010 5:01

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

Под волшебным словом я имел в виду слово "пожалуйста".

М

Демонстрации независимости взглядов в этой теме больше не поощряются! Приветствуется дружественность, корректность, терпимость и вежливость

Автор: RathaR 6.01.2010 6:38

эм... я в непонятках... я так понимаю, что написал что-то неправильно? "пересекаються" пишеться без мягкого знака? Тогда, извините, чем богаты тем и рады... русский язык вели в школе 1 год в 5 класе , ато я и так каждое третье слово перед тем как запостить, в гугле прописую, дабы убедиться в правильности его написания, вобщем, стараюсь как могу, а по сабжу "пересекаються" поправлять меня он не решился, везде так пишут, видимо ошибка распространенная Так что изивините уж...

Автор: Lapp 6.01.2010 7:00

Именно так. И это главное.
Я, в свою очередь, прекрасно знаю, что мой английский весьма далек от идеала. Но я стараюсь, как могу. И никто ни разу мне тут за 10 лет не сказал, что что-то чего-то режет (а тем более передразнить "режеть"). Поправить при необходимости - это другое дело, и это я приветствую.

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

RathaR'у от меня +1 за правильную реакцию.

Автор: TarasBer 6.01.2010 17:36

> а по сабжу "пересекаються" поправлять меня он не решился, везде так пишут, видимо ошибка распространенная

И это печально. А в украинском разве нет правил тся-ться? Впрочем, вы можете и сейчас подправить пост.

> И это был не лучший способ указать на ошибку

Странно, мой шуточный пост не пытался никого обидеть. Вы всегда воспринимаете серьёзно посты без смайликов?
Мне что, специально выделять все двусмысленные места закрывающейся скобочкой? Без неё юмор уже никто не понимает?

> и лучше было специально выделить специально совершаемую ошибку

А в комедиях без закадрового смеха тоже уже никто юмор не понимает?
Короче, кто шутку понял, тот понял. А ставить в тексте указатель <- [тут типа шутка, надо не обижаться, а смеяться] - это тупость. Поэтому я никогда не пишу посты со смайликами. Я вообще их использую только в сетевых играх, когда время на написание сообщения очень критично.

Автор: Lapp 7.01.2010 5:40

Тарас, не нужно брать на себя обязанности модератора. Не нравится, как написано - не отвечай. В каждом почти твоем ответе разговор про ошибки в написании. И везде не просто так, а с подковыркой.

Твое личное отношение к смайлам и т.п. известно (помню его с первого прочтения твоего профиля). Пойми, это твое отношение, и не навязывай его другим. А шутить советую на менее опасные темы. Любое передразнивание легко объявить шуткой - я хоть и тупой по твоим меркам, но это могу понять.

М

В дальнейшем, пожалуйста, воздержись от замечаний по поводу орфографии/пунктуации. Если очень хочется - без подколок, шуток и со словом "пожалуйста".

и я бы на твоем месте извинился за эту "шутку"..

Автор: TarasBer 7.01.2010 18:47

[offtop]
Вот вы опять всё приняли на свой счёт. Хотя у меня здесь ни с кем счётов нет. А смайлы ставить я НЕ буду - это моё право, и не надо мне их навязывать, тем более, что сто лет без них как-то жили, и ничего.

Хорошо, я извиняюсь за шутку перед всеми, кто её не понял.
[/offtop]

Автор: Lapp 8.01.2010 3:27

Вот и хорошо ))

Автор: sheka 13.08.2012 20:48

То же самое, но чуть больше слов
http://users.livejournal.com/_winnie/152327.html

Добавлено через 1 мин.
Прошу прощения, не заметил, что оно на Сях.