Пересечение прямых - Форум на исходниках

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
Есть задача: требуется определить пересекаются ли два прямых отрезка на плоскости(есть PointStart и PointEnd для обоих отрезков).Пробовал математически решить,но привидение пикселей к int все
проваливает.Кто поможет?
Kosha опубликован 13-08-2001 01:37 MSK
Ну, в win есть такие функции (в GDI), но они работают только с целыми, насколько я помню.
Почитай MSDN, точно было такое. Еще есть аналогичные функции в DirectX
Emerald опубликован 13-08-2001 03:00 MSK
Насколько у меня развито мышление, то разница между концами и началами отрезков должна быть равна 0 -- тогда они не пересекаются. Т.е. (начало1-начало2) == (конец1-конец2).
OlegO опубликован 13-08-2001 11:54 MSK
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
¬Є¬Щ¬У¬Ц¬Я¬с¬р¬г¬о :) ¬Ц¬л¬Ц ¬в¬С¬Щ
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
Что то из 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.

Автор	Тема: Пересечение прямых
bond	опубликован 13-08-2001 01:01 MSK Есть задача: требуется определить пересекаются ли два прямых отрезка на плоскости(есть PointStart и PointEnd для обоих отрезков).Пробовал математически решить,но привидение пикселей к int все проваливает.Кто поможет?
Kosha	опубликован 13-08-2001 01:37 MSK Ну, в win есть такие функции (в GDI), но они работают только с целыми, насколько я помню. Почитай MSDN, точно было такое. Еще есть аналогичные функции в DirectX
Emerald	опубликован 13-08-2001 03:00 MSK Насколько у меня развито мышление, то разница между концами и началами отрезков должна быть равна 0 -- тогда они не пересекаются. Т.е. (начало1-начало2) == (конец1-конец2).
OlegO	опубликован 13-08-2001 11:54 MSK Emerald >> ¬Ї¬Ц ¬б¬а¬Я¬с¬Э ¬С¬Э¬Ф¬а¬в¬Ъ¬д¬Ю¬С ??? ¬¦¬г¬Э¬Ъ ¬Я¬С¬Х¬а ¬е¬г¬Э¬а¬У¬Ъ¬Ц ¬б¬Ц¬в¬Ц¬г¬Ц¬й¬Ц¬Я¬Ъ¬с ¬а¬д¬в¬Ц¬Щ¬Ь¬а¬У, ¬д¬а ¬Ь¬С¬Ь ¬У¬С¬в¬Ъ¬С¬Я¬д ¬в¬Ц¬С¬Э¬Ъ¬Щ¬С¬и¬Ъ¬с: - ¬±¬в¬с¬Ю¬С¬с Ax+By+C=0 ¬б¬а ¬Х¬У¬е¬Ю ¬д¬а¬й¬Ь¬С¬Ю P1(x1,y1), P2(x2,y2): A=y2-y1 B=x1-x2 C=-Ax1-By1=y1x2-x1y2 - ¬І¬С¬г¬г¬д¬а¬с¬Я¬Ъ¬Ц ¬а¬д ¬д¬а¬й¬Ь¬Ъ S(x0,y0) ¬Х¬а ¬б¬в¬с¬Ю¬а¬Ы r=(Ax0+By0+C)/Ўо(A©ч+B©ч) ¬Ь¬С¬Ь Q ¬Ю¬н ¬а¬Т¬а¬Щ¬Я¬С¬й¬Ъ¬Ю: Q(P1(x1,y1),P2(x2,y2),S(x0,y0))=rЎо(A©ч+B©ч)=x(y2-y1)+y(x1-x2)+y1x2-x1y2 - ¬Є ¬д¬а¬Ф¬Х¬С ¬е¬г¬Э¬а¬У¬Ъ¬Ц ¬б¬Ц¬в¬Ц¬г¬Ц¬й¬Ц¬Я¬Ъ¬с ¬Х¬У¬е¬з ¬а¬д¬в¬Ц¬Щ¬Ь¬а¬У (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)+aybx-ax*by; end;
OlegO	опубликован 13-08-2001 12:00 MSK ¬Є¬Щ¬У¬Ц¬Я¬с¬р¬г¬о :) ¬Ц¬л¬Ц ¬в¬С¬Щ Emerald >> ¬Ї¬Ц ¬б¬а¬Я¬с¬Э ¬С¬Э¬Ф¬а¬в¬Ъ¬д¬Ю¬С ??? ¬¦¬г¬Э¬Ъ ¬Я¬С¬Х¬а ¬е¬г¬Э¬а¬У¬Ъ¬Ц ¬б¬Ц¬в¬Ц¬г¬Ц¬й¬Ц¬Я¬Ъ¬с ¬а¬д¬в¬Ц¬Щ¬Ь¬а¬У, ¬д¬а ¬Ь¬С¬Ь ¬У¬С¬в¬Ъ¬С¬Я¬д ¬в¬Ц¬С¬Э¬Ъ¬Щ¬С¬и¬Ъ¬с: - ¬±¬в¬с¬Ю¬С¬с Ax+By+C=0 ¬б¬а ¬Х¬У¬е¬Ю ¬д¬а¬й¬Ь¬С¬Ю P1(x1,y1), P2(x2,y2): A=y2-y1 B=x1-x2 C=-Ax1-By1=y1x2-x1y2 - ¬І¬С¬г¬г¬д¬а¬с¬Я¬Ъ¬Ц ¬а¬д ¬д¬а¬й¬Ь¬Ъ S(x0,y0) ¬Х¬а ¬б¬в¬с¬Ю¬а¬Ы r=(Ax0+By0+C)/Ўо(A©ч+B©ч) ¬Ь¬С¬Ь Q ¬Ю¬н ¬а¬Т¬а¬Щ¬Я¬С¬й¬Ъ¬Ю: Q(P1(x1,y1),P2(x2,y2),S(x0,y0))=rЎо(A©ч+B©ч)=x(y2-y1)+y(x1-x2)+y1x2-x1y2 - ¬Є ¬д¬а¬Ф¬Х¬С ¬е¬г¬Э¬а¬У¬Ъ¬Ц ¬б¬Ц¬в¬Ц¬г¬Ц¬й¬Ц¬Я¬Ъ¬с ¬Х¬У¬е¬з ¬а¬д¬в¬Ц¬Щ¬Ь¬а¬У (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)+aybx-ax*by; end;
OlegO	опубликован 13-08-2001 12:13 MSK Что то из Worda копирование не проходит, хотя текст при заполнении читаем :(: Попытка №3 :) Если надо условие пересечения отрезков, то как вариант: - Прямая Ax+By+C=0 по двум точкам P1(x1,y1), P2(x2,y2): A = y2-y2 B = x1-x2 C = -Ax1-By1 = y1x2 - x1y2 - Расстояние от точки S(x0,y0) до прямой: r = Ax0 + By0 + C /sqrt(AA + BB) обозначим как Q(P1(x1,y1),P2(x2,y2),S(x0,y0)) = rsqrt(AA+BB) = x0(y2-y1)+y0(x1-x2) + y1x2 - x1y2 - Тогда условие пересечения двуч отрезков(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)+aybx-ax*by; end;