Задача о пересечении отрезков

Например, взять векторные произведения и глянуть на знаки.

http://alglib.manual.ru/geometry/sectint.php

кого с кем произведения? ))) че то я не пойму с ходу как тут вект произведение так вот сразу поможет....

по шагам

0) найти точку пересенчения прямых содержащих отрезки.

1) проверить принадлежность этой точки 1-му отрезку.

2) проверить принадлежность этой точки 2-му отрезку.

F1(x,y)=A1x+B1y+C1 и F2(x,y)=A2x+B2y+C2 - два уравнения прямых, на которых лежат отрезки. Если отрезки пересекаются, то уравнения имеют общие корни x и y.

пары коэффициентов ABC(A=y2-y1, B=x1-x2, C=-A*x1-B*y1) однозначно 
определяются координатами концов обоих отрезков. Осталось решить 
систему уравнений относительно x и y:

A1x+B1y+C1=0 
A2x+B2y+C2=0

Искомые решения и будут пересечением отрезков. 

Код, рисующий один отрезок на массиве пикселов bm[i][yi], такой:

////////////////////// начало рисования отрезка ////////////////////////
//      строим аналитически по 2-м координатам(x1,y1 и x2,y2) уравнение прямой,
//      на которой аналитически рисуем отрезок
//      F(x,y)=A*x+B*y+C
        int A=y2-y1; int B=x1-x2; int C=-A*x1-B*y1;
//        printf ("x1=%d, y1=%d, x2=%d, y2=%d\n", x1, y1, x2, y2);
        for (j=y1; j<=y2; j++) if (A != 0){
          int xj=(int)(-(B*j+C)/A);
          bm[xj][j]=0;
        }
        for (j=y2; j<=y1; j++) if (A != 0){
          int xj=(int)(-(B*j+C)/A);
          bm[xj][j]=0;
        }
        for (i=x1; i<=x2; i++) if (B != 0){
          int yi=(int)(-(A*i+C)/B);
          bm[i][yi]=0;
        }
        for (i=x2; i<=x1; i++) if (B != 0){
          int yi=(int)(-(A*i+C)/B);
          bm[i][yi]=0;
        }
// http://stratum.ac.ru/textbooks/kgrafic/additional/addit13.html
// надо переделать на алгоритм Брезенхема
////////////////////// конец рисования отрезка ////////////////////////

> F1(x,y)=A1x+B1y+C1 и F2(x,y)=A2x+B2y+C2 - два уравнения прямых, на которых лежат отрезки. Если отрезки пересекаются, то уравнения имеют общие корни x и y.

Считаешь детерминант и смотришь на знак.

Ептить... сплошные астрономы из того анекдота "а Аризоне все овцы черные"!

Это необходимое условие, но недостаточное. То что прямые содержащие отрезки пересекаются, не значит что пересекаются сам отрезки. Пример:

| -

я бы взял бы два массива, содержащих точки этих отрезков, если в этих массивах есть общие x и y(либо решил систему и подставил значения для отрезков), значит отрезки пересекаются. потому как там округления идут при помощи int, так что аналитика врядли совпадет на сетке пикселов(если надо отрисовывать конечно).

должно быть аналитическое решение, но оно так с ходу не придумалось.

А как проверить принадлежность точки отрезку.

Кста, об астрономах:

Находишь т.пересечения, а затем, сравниваешь её с проекциями координат концов отрезков.

>А как проверить принадлежность точки отрезку.

Кроме того, что точка должна лежать на пересечении двух ПРЯМЫХ, она должна быть в пределах этих отрезков:

M(a,b) - найденная точка
x1 <= a <= x2
y1 <= b <= y2

Элементарно, Ватсон. Вопрос был о том пересекаются они или нет.

Таки по шагам

нума анцъ) сдвинуть начало координат в одну из вершин какого-нибудь отрезка

2) получится 3 вектора

3) теперь остается только понять их относительное положение друг к другу

4) искать учебник по линейной алгебре и учиться, учиться, учиться...

Может кого повторю, но я что-то вспомнил такой метод.
Метод чисто координатный

0) начало
1) сотрировать по возрас танию X, Y координаты
2) смотреть что внутри чего, использовать 2-4 сравнения
3) делать правильный вывод
oo) всё

И чего это дает? один отрезок может лежать полностью в квадрате образованном вершинами другого, и при этом сов. его не пересекать.

yuriy123 - сдвиг нач. координат не дает тут вааще ничего.

Selectery - точку пересечиния нуно проверять для каждого оторезка индивидуально, причем это моно делать токо по одной из координат (напр по X). Условие по второй координате будет выполненао автоматом т.к. точка принадлежит прямой содержащей отрезок.

отрнезки (x1,y1)-(x2,y2) (x3,y3)-(x4,y4)

M=(x,y)

x1<x2?(x1<=x && x<=x2):(x1>=x && x>=x2)

x3<x4?(x3<=x && x<=x4):(x3>=x && x>=x4)

Народ, е-мое, ну скоко моно тупить над задачей по ангему для 1-го курса заборостроительного ПТУ? :-)

google знаеш, да? Хороший весч.

http://softsurfer.com/Archive/algorithm_0104/algorithm_0104B.htm

> Народ, е-мое, ну скоко моно тупить над задачей по ангему для 1-го курса заборостроительного ПТУ? :-)

Тупишь как раз ты, ежели не можешь сделать то, что должен уметь пэтэушник.

"Ты Юр на грубость нарываишси..."(с)

Я не пользуюсь Гуглом и др поискавиками для тривиальных вещей к-е быстрее сделать самому чем набирать запрос и потом ище копать вывод.

И что тут дает сдвиг начала координат? Для поиска точки пересечения ничего, поскоку матрицу ето не диагонализарует (сам же сказал три вектора а не два). Да и найти точку пересечения моно без всяикх свдигов.

Для проверки принадлежности тоже ничего не дает.

>Тупишь как раз ты, ежели не можешь сделать то, что должен уметь пэтэушник.

Я плакаль... посмотри дискуссию что ли внимательно, а... Верные ответы были еще токо у Selectera

А одна звезда еще не дает права хамить, тем более безосновательно:-)

не собирался я расжовывать что значит 2) и 3)

Определись что тебе надо, узнать факт пересечения или найти точку пересечения?

> Я не пользуюсь Гуглом и др поискавиками для тривиальных вещей к-е быстрее сделать самому чем набирать запрос и потом ище копать вывод.

А зря. google:Sweep Algorithms

ПЕРВАЯ ссылка http://www.cs.duke.edu/courses/spring04/cps234/papers/NP82.pdf

Вот Универсальный Алгоритм Решения Любой Задачи:

1) начало

2) середина

3) конец.

И не спрашивайте меня что есть что, я не собираюсь вам этого расжевывать:-)))))

Мне ничего не надо. А автору темы нужен был факт пересечения. Про точку песечения - еще раз - в данном случае НЕ НАДО ТАМ НИЧЕГО НИКУДА ДВИГАТЬ. Такая система из двух лин. уравнений решается вообще в уме. Сдвиг начала координат имеет смысл когда ты существенно упрощаешь матрицу, здесь ее упрощать некуда. Да, при решении факт. ты делаешь этот сдвиг, можно и так рассматривать, но акцентировать на этом деле внимание ИМНО не стоит - все равно что гордо кричать что при вычисления 1+2*3 ты учитываешь приоритет операций:-)

Александр Александрович Шишкин - что нибуть говорит? :-) Вот он бы научил родину любить...

Если ты по любому поводу лезешь в Гугл - флаг в руки:-)

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

> че то я не пойму с ходу как тут вект произведение так вот сразу поможет....

Неужто АА Шишкин не потрудися рассказать? Векторное произведение покажет как расположены точки относительно выбранного направления. Это может быть не оптимально. Весь вопрос в количестве отрезков.

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

А зачем мне знать как расположены точки относительно данного направления? То что направление одного отрезка попадает в створ другого еще не значит что они пересекаются. Хотя конечно если первый отрезок попадает в створ второго, а второй в створ первого то пересекаются... согласен, это метод номер два:-)

>Только я не вижу твоих постов содержащих что-то кроме наездов и понтов.

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

> Вот Универсальный Алгоритм Решения Любой Задачи:
> 1) начало
> 2) середина
> 3) конец.
> И не спрашивайте меня что есть что, я не собираюсь вам этого
> расжевывать:-)))))

> AIv (*) (18.04.2005 14:46:23)

А почему бы и нет ?

;-D

Ты МГУшник?

Уже давно закончил.......

Антихриста на тебя нет, императивщик проклятый! ;0

Правильно делать так:

выход=function(вход).

Точку пересечения находить вовсе не обязательно -- это лишняя операция деления, а деление дорого.
Два отрезка пересекаются тогда и только тогда, когда концы одного отрезка лежат с в разных полуплоскостях относительно прямой проведенной через другой отрезок, и наоборот.
Чобы проверить лежат ли точки в разных полуплоскостях относительно прямой следует подставить их координаты в уравнение прямой (вида a*x + b*y) и сравнить знаки.
И того получается 8 операций умножения, 4 сложения и 4 сравнения с нулём. Можно сделать и меньше.

(На каком фаультете учился?)

вы оба не правы. Универсальный Алгоритм решения любой задачи таков:

1) подумать
2) записать ответ

> Два отрезка пересекаются тогда и только тогда

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

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

Это yuriy123 уже предлогал, и я с етим уже согласился, см выше.

(второму-анонимусу - ЭТО ПРАЛЬНО, посколько есть ключевое слово И НАОБОРОТ)

Физфак.

Алгоритм Свазерленда-Коена