Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11678
Последний выпуск: 19.06.2015

Математика: алгоритм определения пересечения двух отрезков

277
17 марта 2009 года
nof
193 / / 03.04.2006
Заранее извиняюсь, если ошибся с разделом, но просто пишу на си, поэтому и алгоритм хотел бы на нём =)

Так вот, у меня всю жизнь было плохо с математикой и столкнулся с такой проблемой. Есть два отрезка с совершенно рандомными координатами от -10000 до +10000, нужно определить пересекаются ли данные отрезки или нет. В интернете пытался найти готовый алгоритм - не получилось. Видимо, задача тривиальна..

У кого есть идеи или кто сталкивался с таким вопросом, подскажите пожалуйста. От готового решения также не откажусь =) Заранее, спасибо!
7
17 марта 2009 года
hardcase
4.5K / / 09.08.2005
Цитата: nof
нужно определить пересекаются ли данные отрезки или нет. В интернете пытался найти готовый алгоритм - не получилось. Видимо, задача тривиальна..

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

277
17 марта 2009 года
nof
193 / / 03.04.2006
Цитата: hardcase
Находим точку пересечения двух прямых, и если она есть, проверяем, лежит ли она на обоих отрезках.
Найти пересечение элементарно - нужно решить систему уравнений прямых.


Это при условие, что у нас есть уравнения описывающие данные отрезки. Но у нас есть только начальные и конечные точки отрезков.

357
17 марта 2009 года
SergPas
527 / / 03.02.2007
Есть такая замечательная книга Френсиса Хилла "OpenGL. Программирование компьютерной графики". В ней есть решение задачи определения точки пересечения 2-х отрезков прямой, заданных в параметрической (то что нужно) и/или в точечной нормальной формах...
11
17 марта 2009 года
oxotnik333
2.9K / / 03.08.2007
Цитата: nof
Это при условие, что у нас есть уравнения описывающие данные отрезки. Но у нас есть только начальные и конечные точки отрезков.


уравнение прямой y= k*x + b
где k тангенс угла наклона прямой (отношение противолежащего катета к прилежащему, катеты можно легко найти, зная координаты точек отрезка)
b - некая постоянная (то значение Y где прямая пересекает ось OY)

7
17 марта 2009 года
hardcase
4.5K / / 09.08.2005
Цитата: nof
Это при условие, что у нас есть уравнения описывающие данные отрезки. Но у нас есть только начальные и конечные точки отрезков.


Внимаетельно смотрим на формулы. Там есть ответы на все ваши вопросы.

286
17 марта 2009 года
plastictown
306 / / 08.01.2006
Берем канонические уравнения:

таковые легко получить имея две точки прямой (x1, y1, z1), (x2, y2, z2)

(x-x1) (y-y1) (z-z1)
------= ----- = ------
(x2-x1) (y2-y1) (z2-z1)

где знаменатели дробей соответственно равны m, n и p

Для двух прямых имеем:

m1, n1, p1
m2, n2, p2

Если отношения m1/m2 равно n1/n2 и равно p1/p2, то прямые параллельны, в потивном случае они пересекаются.

Для двумерного случая дробь с координатой z не нужна.

Далее, если прямые не параллельны, находим точку пересечения, решая систему уравнений, как это было сказано тов. hardcase

Цитата:

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

286
17 марта 2009 года
plastictown
306 / / 08.01.2006
Цитата: SergPas
Есть такая замечательная книга Френсиса Хилла "OpenGL. Программирование компьютерной графики". В ней есть решение задачи определения точки пересечения 2-х отрезков прямой, заданных в параметрической (то что нужно) и/или в точечной нормальной формах...



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

Я бы посоветовал книгу Дмитрия Письменного "Конспект лекций по высшей математике" ( 1-ю часть). Там есть аналитическая геометрия, к которой как раз и относится первоначальный вопрос. К тому же в весьма доступной форме. Да и вообще по аналитической геометрии в недрах паутины материала предостаточно.

236
17 марта 2009 года
Rebbit
1.1K / / 01.08.2005
Цитата: oxotnik333
уравнение прямой y= k*x + b
где k тангенс угла наклона прямой


Только такое уравнение не подходит для вертикальных прямых так как у 90 градусов нет тангенса. Ето надо учитывать.

Цитата: plastictown

(x-x1) (y-y1) (z-z1)
------= ----- = ------
(x2-x1) (y2-y1) (z2-z1)


Ну и тут по сути надо учитывать то же самое. В знаменателе может и 0 получится.

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

357
17 марта 2009 года
SergPas
527 / / 03.02.2007
Цитата: plastictown
Имея такую книгу, могу сказать, что найти её не так просто. На сайте издательства она быват далеко не всегда, не говоря о магазинах.

Я бы посоветовал книгу Дмитрия Письменного "Конспект лекций по высшей математике" ( 1-ю часть). Там есть аналитическая геометрия, к которой как раз и относится первоначальный вопрос. К тому же в весьма доступной форме. Да и вообще по аналитической геометрии в недрах паутины материала предостаточно.


Я не говорю о бумажной версии этой книги, я говорю об электронном варианте, который найти в рунете как расплюнуть...;) В ней как раз и рассматриваются вопросы по сабжу... Также обсуждаются вопросы и перекрывающихся прямых, и т.д. и т.п. Да и представленные в ней алгоритмы универсальны...

277
17 марта 2009 года
nof
193 / / 03.04.2006
Ребят, извините мою безграмотность + я ещё не начал проверять на практике то, что вы описали, но на глаз: речь ведь идёт об отрезках, а вы все пишите о прямых. Мне не нужно искать точку пересечения прямых, мне нужно знать пересекаются отрезки или нет.
236
17 марта 2009 года
Rebbit
1.1K / / 01.08.2005
Тоесть отрезки не на плоскости или в пространстве, а на прямой ?? Ги-ги. Ето же тривиально. Можно написать пару ифов. Типа если начало второго отрезка лежит после начала первого и конец....... и так далее. А можно просто взять 4 точки и.... Короче примерно так как я писал тут с отрезками времени
201
17 марта 2009 года
aks
2.5K / / 14.07.2006
Блин, автор ну перечитай еще раз что тебе уже посоветовал hardcase. И должно быть стыдно - ибо в данной задаче программирования то особо нету, а есть только школьная геометрия, не более.
236
17 марта 2009 года
Rebbit
1.1K / / 01.08.2005
Цитата: aks
Блин, автор ну перечитай еще раз что тебе уже посоветовал hardcase. И должно быть стыдно - ибо в данной задаче программирования то особо нету, а есть только школьная геометрия, не более.


Да нет там геометрии если я правильно понял. У нево только одна координата Х. Отрезки в одномерном пространстве.

357
17 марта 2009 года
SergPas
527 / / 03.02.2007
Цитата: nof
Ребят, извините мою безграмотность + я ещё не начал проверять на практике то, что вы описали, но на глаз: речь ведь идёт об отрезках, а вы все пишите о прямых. Мне не нужно искать точку пересечения прямых, мне нужно знать пересекаются отрезки или нет.


Вы и не будете искать точку пересечения, если это не надо... Вы найдёте один единственный параметр и если он будет лежать вне интервала [0;1], то отрезки прямых не пересекаются. Короче, читайте, учите, ищите, разбирайтесь... Литературу Вам указали...

56K
21 декабря 2009 года
Crazy Driver
2 / / 21.12.2009
Пипец, все такие умные, но ничего конкретного человеку так и не предложили. Всё почитай, да поищи, да этоже элементарно. Если элементарно, так напиши.
Короче вот функция на java (с портированием на C я думаю проблем не будет :), определяющая пересекаются ли два отрезка на плоскости:
 
Код:
boolean transection (double ax1, double ay1, double ax2, double ay2, double bx1, double by1, double bx2, double by2)
{
    double v1=(bx2-bx1)*(ay1-by1)-(by2-by1)*(ax1-bx1);
    double v2=(bx2-bx1)*(ay2-by1)-(by2-by1)*(ax2-bx1);
    double v3=(ax2-ax1)*(by1-ay1)-(ay2-ay1)*(bx1-ax1);
    double v4=(ax2-ax1)*(by2-ay1)-(ay2-ay1)*(bx2-ax1);
    return ((v1*v2<=0) && (v3*v4<=0));
}

Функция возвращает true если отрезки A и B пересекаются.
ax1, ay1 - координаты первой точки отрезка A ну и т.д.

Вот ищу нечто подобное для определения пересекает ли отрезок круг.
Если известны координаты отрезка, координаты центра круга и его радиус.
7
21 декабря 2009 года
hardcase
4.5K / / 09.08.2005
Цитата: Crazy Driver
Пипец, все такие умные, но ничего конкретного человеку так и не предложили. Всё почитай, да поищи, да этоже элементарно. Если элементарно, так напиши.


Ссылка на решение задачи была дана в #6. Автор, кстати, просил хотя бы алгоритм.

Цитата: Crazy Driver

Вот ищу нечто подобное для определения пересекает ли отрезок круг.
Если известны координаты отрезка, координаты центра круга и его радиус.


Решите аналитически систему уравнений:
а) окружности
б) прямой
"Линейка", первый курс.

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

56K
21 декабря 2009 года
Crazy Driver
2 / / 21.12.2009
Цитата: hardcase
Ссылка на решение задачи была дана в #6. Автор, кстати, просил хотя бы алгоритм.


Это ссылка не на решение задачи, а на статью Википедии о прямой.
И естественно никаких алгоритмов там нет.

Цитата: hardcase

Решите аналитически систему уравнений:
а) окружности
б) прямой
"Линейка", первый курс.


Очень "полезный" совет, никогдаб не догадался.

7
21 декабря 2009 года
hardcase
4.5K / / 09.08.2005
Цитата: Crazy Driver
Это ссылка не на решение задачи, а на статью Википедии о прямой.


Переходим по ссылке, находим подраздел "Взаимное расположение нескольких прямых на плоскости" и (о чудо!) обнаруживаем там формулу, которую вы записали в своем предыдущем посте. А как найти коэффициенты канонического уравнения? - спросите вы. А очень просто: на той же самой странице есть уравнение прямой проходящей через две заданные точки. Имеющий глаза да узрит решение.

Цитата: Crazy Driver
И естественно никаких алгоритмов там нет.


С каких это пор язык математики перестал выражать суть исполняемых компьютером действий?

Для общего развития: слова алгоритм и арифметика восходят к одному корню.

Цитата: Crazy Driver
Очень "полезный" совет, никогдаб не догадался.

Ну так и вперед! Че, лень пошевелить мозгами, ага?

[quote="некто"]
Зачем тогда вообще отвечать на форуме? Можно просто на все посты давать две ссылки на википедию и на Google
[/quote]
Каков вопрос - таков ответ.

9.0K
21 декабря 2009 года
grag63
71 / / 23.01.2006
Надеюсь следующие рассуждения помогут в решении задачи:
исходные данные: отрезок AB, радиус R.
Возможные варианты:
1) растояния до точек отрезка < R -> отрезок внутри окружности
2) одно из растояний до отрезка > R, а другое < R -> ответ очевиден
3) AR & BR > R - строим перпендикуляр от центра окружности к отрезку (точка C)
CR > R -> отрезок находится за пределами окружности.
357
22 декабря 2009 года
SergPas
527 / / 03.02.2007
Цитата:
исходные данные: отрезок AB, радиус R.


А центр окружности разве не нужен? :D

Цитата: grag63
Надеюсь следующие рассуждения помогут в решении задачи:
исходные данные: отрезок AB, радиус R.
Возможные варианты:
1) растояния до точек отрезка < R -> отрезок внутри окружности
2) одно из растояний до отрезка > R, а другое < R -> ответ очевиден
3) AR & BR > R - строим перпендикуляр от центра окружности к отрезку (точка C)
CR > R -> отрезок находится за пределами окружности.


А решить одно квадратное уравнение с одним неизвестным уже не по силам? ;)

9.0K
23 декабря 2009 года
grag63
71 / / 23.01.2006
А центр окружности разве не нужен?
а как же без него?
И точку С необходимо проверит на принадлежность отрезку, и...

А решить одно квадратное уравнение с одним неизвестным уже не по силам?
Может проще привести уравнение, чем каждый раз отвечать вопросом на вопрос???
1.8K
23 декабря 2009 года
GreenRiver
451 / / 20.07.2008
Господин топик-стартер не желает не только решать уравнения уровня третьего класса,
он даже не желает набрать в гугле пересечение отрезков и выбрать из десятков готовых решений...
71K
21 апреля 2011 года
Anton Nazarov
1 / / 21.04.2011
Есть готовая функция на C# для нахождения точки пересечения двух отрезков, заданных точками, один из которых горизонтальный или вертикальный, может кому пригодится. http://pastie.org/1819393
Код:
// нахождение точки пересечения отрезка, заданного точками p1 p2 c вертикальным/горизонтальным отрезком, заданным точками p3 p4
        public Point Crossing(Point p1, Point p2, Point p3, Point p4)
        {
            if (p3.X == p4.X)   // вертикаль
            {
                double y = p1.Y + ((p2.Y - p1.Y) * (p3.X - p1.X)) / (p2.X - p1.X);
                if (y > Math.Max(p3.Y, p4.Y) || y < Math.Min(p3.Y, p4.Y) || y > Math.Max(p1.Y, p2.Y) || y < Math.Min(p1.Y, p2.Y))   // если за пределами отрезков
                    return new Point(0, 0);
                else
                    return new Point(p3.X, (int)y);
            }
            else            // горизонталь
            {
                double x = p1.X + ((p2.X - p1.X) * (p3.Y - p1.Y)) / (p2.Y - p1.Y);
                if (x > Math.Max(p3.X, p4.X) || x < Math.Min(p3.X, p4.X) || x > Math.Max(p1.X, p2.X) || x < Math.Min(p1.X, p2.X))   // если за пределами отрезков
                    return new Point(0, 0);
                else
                    return new Point((int)x, p3.Y);
            }
        }
98K
17 января
freddyspb
1 / / 17.01.2017
Код выше не работает для перпендикулярных отрезков.
Вот пример получения точки пересечения для 2 перпендикулярных отрезков (может кому пригодится):
 
Код:
function getCrossPoint(p1, p2, p3, p4) {
 
    if ( Math.min(p1.x, p2.x) > p3.x || Math.max(p1.x, p2.x) < p3.x
      || Math.min(p3.y, p4.y) > p1.y || Math.max(p3.y, p4.y) < p1.y) {    
      // не пересекаются
      return {x: 0, y: 0};
    } else
      return {x: p3.x, y: p1.y};    
  }

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог