Сегменттердің қиылысуын қалай анықтауға болады. Екі кесіндінің қиылысу нүктесін анықтау. Қиылысу нүктесі

Қиылысу нүктесі

Бізге олардың коэффиценттерімен және -мен анықталатын екі түзу берілсін. Олардың қиылысу нүктесін табу керек немесе түзулердің параллель екенін білу керек.

Шешім

Егер екі түзу параллель болмаса, онда олар қиылысады. Қиылысу нүктесін табу үшін екі түзу теңдеулер жүйесін құрып, оны шешу жеткілікті:

Крамер формуласын қолдана отырып, біз дереу жүйенің шешімін табамыз, ол қалаған болады қиылысу нүктесі:

Егер бөлгіш нөлге тең болса, яғни.

онда жүйеде шешімдер жоқ (тікелей параллельжәне сәйкес келмейді) немесе шексіз көп (тікелей сәйкестік). Егер осы екі жағдайды ажырату қажет болса, сызықтардың коэффициенттері коэффициенттерімен бірдей пропорционалдық коэффициентімен пропорционал екенін тексеру қажет және , ол үшін екі анықтауышты есептеу жеткілікті; егер олар екеуі де болса нөлге тең болса, онда сызықтар сәйкес келеді:

Іске асыру

struct pt(қос x, y;); құрылымдық сызық(қос a, b, c;); қосылатын EPS =1e-9; қос дет (қос а, қос б, қос в, қос d)(қайтару a * d - b * c;) bool қиылысу (m сызық, n сызық, pt & res)(қос zn = det (m.a, m.b, n.a) , n.b);егер(abs(zn)< EPS)returnfalse; res.x=- det (m.c, m.b, n.c, n.b)/ zn; res.y=- det (m.a, m.c, n.a, n.c)/ zn;returntrue;} bool parallel (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS;} bool equivalent (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS &&abs(det (m.a, m.c, n.a, n.c))< EPS &&abs(det (m.b, m.c, n.b, n.c))< EPS;}

« сериясынан сабақ Геометриялық алгоритмдер»

Сәлем құрметті оқырман.

1-кеңес: Екі түзудің қиылысу нүктесінің координаталарын қалай табуға болады

Тағы үш жаңа функция жазайық.

LinesCross() функциясы анықтайды қиылысуекі болсын сегмент. Онда сегменттердің өзара орналасуы векторлық көбейтінділердің көмегімен анықталады. Векторлық туындыларды есептеу үшін VektorMulti() функциясын жазамыз.

RealLess() функциясы салыстыру операциясын орындау үшін пайдаланылады.<” (строго меньше) для вещественных чисел.

1-тапсырма. Екі кесінді координаталары арқылы берілген. анықтайтын программа жазыңыз бұл сегменттер қиылысады ма?қиылысу нүктесін таппай.

Шешім
. Екіншісі нүктелер арқылы беріледі.

Кесінді мен нүктені және .

Нүкте сызықтың сол жағында жатыр, ол үшін векторлық көбейтінді > 0, өйткені векторлар оң бағытталған.

Нүкте векторлық туындысы болатын түзудің оң жағында орналасқан < 0, так как векторы отрицательно ориентированы.

Нүктелер түзудің қарама-қарсы жағында жатуы үшін шарттың орындалуы жеткілікті.< 0 (векторные произведения имели противоположные знаки).

Ұқсас пайымдауды кесінді мен нүктелер үшін де жүргізуге болады.

Сонымен, егер , содан кейін сегменттер қиылысады.

Бұл шартты тексеру үшін LinesCross() функциясы, ал векторлық туындыларды есептеу үшін VektorMulti() функциясы қолданылады.

ax, ay – бірінші вектордың координаталары,

bx, by – екінші вектордың координаттары.

Geometr4 бағдарламасы; (2 сегмент қиылыса ма?) Const _Eps: Real=1e-4; (есептеу дәлдігі) var x1,y1,x2,y2,x3,y3,x4,y4: real; var v1,v2,v3,v4: real;function RealLess(Const a, b: Real): Логикалық; (Қатаң аз) start RealLess:= b-a> _Eps end; (RealLess)функциясы VektorMulti(ax,ay,bx,by:real): real; (ax,ay - a координаттары bx,by - b координаттары) begin vektormulti:= ax*by-bx*ay; end;Function LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:real): логикалық; (Кесінділер қиылыса ма?) басталады v1:=vektormulti(x4-x3,y4-y3,x1-x3,y1-y3); v2:=vektormulti(x4-x3,y4-y3,x2-x3,y2-y3); v3:=vektormulti(x2-x1,y2-y1,x3-x1,y3-y1); v4:=vektormulti(x2-x1,y2-y1,x4-x1,y4-y1); егер RealLess(v1*v2,0) және RealLess(v3*v4,0) (v1v2)<0 и v3v4<0, отрезки пересекаются} then LinesCross:= true else LinesCross:= false end; {LinesCross}begin {main} writeln(‘Введите координаты отрезков: x1,y1,x2,y2,x3,y3,x4,y4’); readln(x1,y1,x2,y2,x3,y3,x4,y4); if LinesCross(x1,y1,x2,y2,x3,y3,x4,y4) then writeln (‘Да’) else writeln (‘Нет’) end.

Бағдарламаның орындалу нәтижелері:

Кесінділердің координаталарын енгізіңіз: -1 1 2 2.52 2 1 -1 3
Иә.

Біз олардың координаталары арқылы көрсетілген сегменттердің қиылысуын анықтайтын бағдарлама жаздық.

Келесі сабақта нүктенің үшбұрыштың ішінде жатқанын анықтауға болатын алгоритм құрамыз.

Құрметті оқырман.

Сіз «Геометриялық алгоритмдер» сериясынан бірнеше сабақтармен таныстыңыз. Барлығы қол жетімді түрде жазылған ба? Осы сабақтар туралы пікір қалдырсаңыз, мен өте ризамын. Мүмкін бірдеңені әлі де жақсарту керек шығар.

Құрметпен, Вера Господарец.

Екі сегмент берілсін. Біріншісі нүктелер арқылы беріледі P 1 (x 1 ;y 1)Және P 2 (x 2 ;y 2). Екіншісі ұпаймен беріледі P 3 (x 3 ;y 3)Және P 4 (x 4 ;y 4).

Сегменттердің өзара орналасуын векторлық туындылар арқылы тексеруге болады:

Сегментті қарастырыңыз P 3 P 4және нүктелер P 1Және P2.

Нүкте P 1сызықтың сол жағында жатыр P 3 P 4, ол үшін векторлық өнім v 1 > 0, өйткені векторлар оң бағытталған.
Нүкте P2сызықтың оң жағында орналасқан, ол үшін векторлық көбейтінді v 2< 0 , өйткені векторлар теріс бағытталған.

Нүкте жасау үшін P 1Және P2түзудің қарама-қарсы жақтарына жату P 3 P 4, бұл шарттың орындалуы үшін жеткілікті v 1 v 2< 0 (векторлық өнімдер қарама-қарсы белгілерге ие болды).

Ұқсас пайымдауды сегмент үшін де жүргізуге болады P 1 P 2және ұпайлар P 3Және P 4.

Сонымен, егер v 1 v 2< 0 Және v 3 v 4< 0 , содан кейін сегменттер қиылысады.

Екі вектордың векторлық көбейтіндісі мына формула бойынша есептеледі:

Қайда:
балта, ай— бірінші вектордың координаталары,
bx, бойынша— екінші вектордың координаталары.

Координаталары арқылы белгіленген екі түрлі нүкте арқылы өтетін түзудің теңдеуі.

Түзуде сәйкес келмейтін екі нүкте берілсін: P 1координаттарымен ( x 1 ;y 1)Және P2координаталарымен (x 2 ; y 2).

Сызықтардың қиылысуы

Сәйкесінше, нүктесінде басы бар вектор P 1және бір нүктеде аяқталады P2координаттары бар (x 2 -x 1 , y 2 -y 1). Егер P(x, y)түзудегі ерікті нүкте, содан кейін вектордың координаталары P 1 Pтең (x - x 1, y - y 1).

Векторлық көбейтіндіні пайдалану, векторлардың коллинеарлық шарты P 1 PЖәне P 1 P 2былай жазуға болады:
|P 1 P,P 1 P 2 |=0, яғни. (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
немесе
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0

Соңғы теңдеу келесі түрде қайта жазылады:
ax + by + c = 0, (1)
Қайда
a = (y 2 -y 1),
b = (x 1 -x 2),
c = x 1 (y 1 -y 2) + y 1 (x 2 -x 1)

Сонымен, түзу (1) түріндегі теңдеу арқылы анықталуы мүмкін.

Түзулердің қиылысу нүктесін қалай табуға болады?
Айқын шешім сызықтық теңдеулер жүйесін шешу болып табылады:

балта 1 +1-ге =-c 1
балта 2 +2-ге =-c 2 (2)

Таңбаларды енгізіңіз:

Мұнда Dжүйенің анықтаушысы болып табылады және Dx, Dy— коэффиценттер бағанын сәйкес белгісізмен бос мүшелер бағанымен ауыстыру нәтижесінде пайда болатын анықтауыштар. Егер D ≠ 0, онда (2) жүйе анықталған, яғни оның бірегей шешімі бар. Бұл шешімді келесі формулалар арқылы табуға болады: x 1 =D x /D, y 1 =D y /D, олар Крамер формулалары деп аталады. Екінші ретті анықтауыштың қалай есептелетінін жылдам еске түсіру. Анықтауыш екі диагоналды ажыратады: негізгі және қосалқы. Негізгі диагональ анықтауыштың жоғарғы сол жақ бұрышынан төменгі оң жақ бұрышқа дейінгі бағытта алынған элементтерден тұрады. Бүйірлік диагональ - жоғарғы оң жақтан төменгі солға қарай. Екінші ретті анықтауыш негізгі диагональ элементтерінің көбейтіндісін шегеріп, екінші ретті диагональ элементтерінің көбейтіндісіне тең.

Екі сегмент берілсін. Біріншісі нүктелер арқылы беріледі P 1 (x 1 ;y 1)Және P 2 (x 2 ;y 2). Екіншісі ұпаймен беріледі P 3 (x 3 ;y 3)Және P 4 (x 4 ;y 4).

Сегменттердің өзара орналасуын векторлық туындылар арқылы тексеруге болады:

Сегментті қарастырыңыз P 3 P 4және нүктелер P 1Және P2.

Нүкте P 1сызықтың сол жағында жатыр P 3 P 4, ол үшін векторлық өнім v 1 > 0, өйткені векторлар оң бағытталған.
Нүкте P2сызықтың оң жағында орналасқан, ол үшін векторлық көбейтінді v 2< 0 , өйткені векторлар теріс бағытталған.

Нүкте жасау үшін P 1Және P2түзудің қарама-қарсы жақтарына жату P 3 P 4, бұл шарттың орындалуы үшін жеткілікті v 1 v 2< 0 (векторлық өнімдер қарама-қарсы белгілерге ие болды).

Ұқсас пайымдауды сегмент үшін де жүргізуге болады P 1 P 2және ұпайлар P 3Және P 4.

Сонымен, егер v 1 v 2< 0 Және v 3 v 4< 0 , содан кейін сегменттер қиылысады.

Екі вектордың векторлық көбейтіндісі мына формула бойынша есептеледі:

Қайда:
балта, ай- бірінші вектордың координаталары,
bx, бойынша- екінші вектордың координаталары.

Координаталары арқылы белгіленген екі түрлі нүкте арқылы өтетін түзудің теңдеуі.

Түзуде сәйкес келмейтін екі нүкте берілсін: P 1координаттарымен ( x 1 ;y 1)Және P2координаталарымен (x 2 ; y 2). Сәйкесінше, нүктесінде басы бар вектор P 1және бір нүктеде аяқталады P2координаттары бар (x 2 -x 1 , y 2 -y 1). Егер P(x, y)түзудегі ерікті нүкте, содан кейін вектордың координаталары P 1 Pтең (x - x 1, y – y 1).

Векторлық көбейтіндіні пайдалану, векторлардың коллинеарлық шарты P 1 PЖәне P 1 P 2былай жазуға болады:
|P 1 P ,P 1 P 2 |=0, яғни. (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
немесе
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0

Соңғы теңдеу келесі түрде қайта жазылады:
ax + by + c = 0, (1)
Қайда
a = (y 2 -y 1),
b = (x 1 -x 2),
c = x 1 (y 1 -y 2) + y 1 (x 2 -x 1)

Сонымен, түзу (1) түріндегі теңдеу арқылы анықталуы мүмкін.

Түзулердің қиылысу нүктесін қалай табуға болады?
Айқын шешім сызықтық теңдеулер жүйесін шешу болып табылады:

балта 1 +1-ге =-c 1
балта 2 +2-ге =-c 2 (2)

Таңбаларды енгізіңіз:

Мұнда Dжүйенің анықтаушысы болып табылады және Dx, Dy- коэффиценттер бағанасын сәйкес белгісізмен бос мүшелер бағанымен ауыстыру нәтижесінде пайда болатын анықтауыштар. Егер D ≠ 0, онда (2) жүйе анықталған, яғни оның бірегей шешімі бар. Бұл шешімді келесі формулалар арқылы табуға болады: x 1 =D x /D, y 1 =D y /D, олар Крамер формулалары деп аталады. Екінші ретті анықтауыштың қалай есептелетінін жылдам еске түсіру. Анықтауыш екі диагоналды ажыратады: негізгі және қосалқы. Негізгі диагональ анықтауыштың жоғарғы сол жақ бұрышынан төменгі оң жақ бұрышқа дейінгі бағытта алынған элементтерден тұрады. Бүйірлік диагональ - жоғарғы оң жақтан төменгі солға қарай. Екінші ретті анықтауыш негізгі диагональ элементтерінің көбейтіндісін шегеріп, екінші ретті диагональ элементтерінің көбейтіндісіне тең.