WWW.ИСХОДНИКИ.РУ cpp.sources.ru
java.sources.ru web.sources.ru soft.sources.ru
jdbc.sources.ru asp.sources.ru api.sources.ru

  Форум на исходниках
  C / C++ / Visual C++
  Пересечение прямых

СПРОСИТЬ  ОТВЕТИТЬ
профайл | регистрация | faq

Автор Тема:   Пересечение прямых
bond опубликован 13-08-2001 01:01 MSK   Click Here to See the Profile for bond   Click Here to Email bond  
Есть задача: требуется определить пересекаются ли два прямых отрезка на плоскости(есть PointStart и PointEnd для обоих отрезков).Пробовал математически решить,но привидение пикселей к int все
проваливает.Кто поможет?
Kosha опубликован 13-08-2001 01:37 MSK     Click Here to See the Profile for Kosha  Click Here to Email Kosha     
Ну, в win есть такие функции (в GDI), но они работают только с целыми, насколько я помню.

Почитай MSDN, точно было такое. Еще есть аналогичные функции в DirectX

Emerald опубликован 13-08-2001 03:00 MSK     Click Here to See the Profile for Emerald  Click Here to Email Emerald     
Насколько у меня развито мышление, то разница между концами и началами отрезков должна быть равна 0 -- тогда они не пересекаются. Т.е. (начало1-начало2) == (конец1-конец2).
OlegO опубликован 13-08-2001 11:54 MSK     Click Here to See the Profile for OlegO  Click Here to Email OlegO     
Emerald >> ¬Ї¬Ц ¬б¬а¬Я¬с¬Э ¬С¬Э¬Ф¬а¬в¬Ъ¬д¬Ю¬С ???

¬¦¬г¬Э¬Ъ ¬Я¬С¬Х¬а ¬е¬г¬Э¬а¬У¬Ъ¬Ц ¬б¬Ц¬в¬Ц¬г¬Ц¬й¬Ц¬Я¬Ъ¬с ¬а¬д¬в¬Ц¬Щ¬Ь¬а¬У,
¬д¬а ¬Ь¬С¬Ь ¬У¬С¬в¬Ъ¬С¬Я¬д ¬в¬Ц¬С¬Э¬Ъ¬Щ¬С¬и¬Ъ¬с:

- ¬±¬в¬с¬Ю¬С¬с Ax+By+C=0 ¬б¬а ¬Х¬У¬е¬Ю ¬д¬а¬й¬Ь¬С¬Ю P1(x1,y1), P2(x2,y2):
A=y2-y1
B=x1-x2
C=-A*x1-B*y1=y1*x2-x1*y2

- ¬І¬С¬г¬г¬д¬а¬с¬Я¬Ъ¬Ц ¬а¬д ¬д¬а¬й¬Ь¬Ъ S(x0,y0) ¬Х¬а ¬б¬в¬с¬Ю¬а¬Ы
r=(A*x0+B*y0+C)/Ўо(A©ч+B©ч)
¬Ь¬С¬Ь Q ¬Ю¬н ¬а¬Т¬а¬Щ¬Я¬С¬й¬Ъ¬Ю:
Q(P1(x1,y1),P2(x2,y2),S(x0,y0))=r*Ўо(A©ч+B©ч)=x(y2-y1)+y(x1-x2)+y1*x2-x1*y2

- ¬Є ¬д¬а¬Ф¬Х¬С ¬е¬г¬Э¬а¬У¬Ъ¬Ц ¬б¬Ц¬в¬Ц¬г¬Ц¬й¬Ц¬Я¬Ъ¬с ¬Х¬У¬е¬з ¬а¬д¬в¬Ц¬Щ¬Ь¬а¬У (a,b) ¬Ъ (A,B) :
Q(a,b;A)*Q(a,b;B)<0 && Q(A,B;a)*Q(A,B;b)<0

¬б¬в¬Ъ¬Ю¬Ц¬в ¬ж-¬Ъ Q ¬Я¬С ¬±¬С¬г¬Ь¬С¬Э¬Ц:

function Q(ax,ay,bx,by,tx,ty:longint):real;
begin
Q:=tx*(by-ay)+ty*(ax-bx)+ay*bx-ax*by;
end;

OlegO опубликован 13-08-2001 12:00 MSK     Click Here to See the Profile for OlegO  Click Here to Email OlegO     
¬Є¬Щ¬У¬Ц¬Я¬с¬р¬г¬о :) ¬Ц¬л¬Ц ¬в¬С¬Щ
Emerald >> ¬Ї¬Ц ¬б¬а¬Я¬с¬Э ¬С¬Э¬Ф¬а¬в¬Ъ¬д¬Ю¬С ???

¬¦¬г¬Э¬Ъ ¬Я¬С¬Х¬а ¬е¬г¬Э¬а¬У¬Ъ¬Ц ¬б¬Ц¬в¬Ц¬г¬Ц¬й¬Ц¬Я¬Ъ¬с ¬а¬д¬в¬Ц¬Щ¬Ь¬а¬У,
¬д¬а ¬Ь¬С¬Ь ¬У¬С¬в¬Ъ¬С¬Я¬д ¬в¬Ц¬С¬Э¬Ъ¬Щ¬С¬и¬Ъ¬с:

- ¬±¬в¬с¬Ю¬С¬с Ax+By+C=0 ¬б¬а ¬Х¬У¬е¬Ю ¬д¬а¬й¬Ь¬С¬Ю P1(x1,y1), P2(x2,y2):
A=y2-y1
B=x1-x2
C=-A*x1-B*y1=y1*x2-x1*y2

- ¬І¬С¬г¬г¬д¬а¬с¬Я¬Ъ¬Ц ¬а¬д ¬д¬а¬й¬Ь¬Ъ S(x0,y0) ¬Х¬а ¬б¬в¬с¬Ю¬а¬Ы
r=(A*x0+B*y0+C)/Ўо(A©ч+B©ч)
¬Ь¬С¬Ь Q ¬Ю¬н ¬а¬Т¬а¬Щ¬Я¬С¬й¬Ъ¬Ю:
Q(P1(x1,y1),P2(x2,y2),S(x0,y0))=r*Ўо(A©ч+B©ч)=x(y2-y1)+y(x1-x2)+y1*x2-x1*y2

- ¬Є ¬д¬а¬Ф¬Х¬С ¬е¬г¬Э¬а¬У¬Ъ¬Ц ¬б¬Ц¬в¬Ц¬г¬Ц¬й¬Ц¬Я¬Ъ¬с ¬Х¬У¬е¬з ¬а¬д¬в¬Ц¬Щ¬Ь¬а¬У (a,b) ¬Ъ (A,B) :
Q(a,b;A)*Q(a,b;B)<0 && Q(A,B;a)*Q(A,B;b)<0

¬б¬в¬Ъ¬Ю¬Ц¬в ¬ж-¬Ъ Q ¬Я¬С ¬±¬С¬г¬Ь¬С¬Э¬Ц:

function Q(ax,ay,bx,by,tx,ty:longint):real;
begin
Q:=tx*(by-ay)+ty*(ax-bx)+ay*bx-ax*by;
end;

OlegO опубликован 13-08-2001 12:13 MSK     Click Here to See the Profile for OlegO  Click Here to Email OlegO     
Что то из Worda копирование не проходит, хотя текст при заполнении читаем :(:
Попытка №3 :)

Если надо условие пересечения отрезков, то как вариант:

- Прямая A*x+B*y+C=0 по двум точкам P1(x1,y1), P2(x2,y2):
A = y2-y2
B = x1-x2
C = -A*x1-B*y1 = y1*x2 - x1*y2
- Расстояние от точки S(x0,y0) до прямой:
r = A*x0 + B*y0 + C /sqrt(A*A + B*B)

обозначим как
Q(P1(x1,y1),P2(x2,y2),S(x0,y0)) = r*sqrt(A*A+B*B) = x0*(y2-y1)+y0*(x1-x2) + y1*x2 - x1*y2

- Тогда условие пересечения двуч отрезков(a,b) и (A,B):
Q(a,b;A)*Q(a,b;B)<0 && Q(A,B;a)*Q(A,B;b)<0

пример ф-и на паскале:

function Q(ax,ay,bx,by,tx,ty:longint):real;
begin
Q:=tx*(by-ay)+ty*(ax-bx)+ay*bx-ax*by;
end;


СПРОСИТЬ  ОТВЕТИТЬ
Перейти:


E-mail | WWW.ИСХОДНИКИ.RU

Powered by: Ultimate Bulletin Board, Freeware Version 5.10a
Purchase our Licensed Version- which adds many more features!
© Infopop Corporation (formerly Madrona Park, Inc.), 1998 - 2000.