Пересечение отрезка с окружностью

[svv]

Geen
А что?

[Geen]

svv в сообщении #1280450 писал(а):

Geen
А что?

Отодвинем отрезок от окружности в десять раз (вдоль перпендикуляра из центра окружности на отрезок) - знаки не изменяться...

[arseniiv]

Чтобы уж наверняка работало, там должна быть не $O$, а интересующая точка пересечения прямой и окружности $C$. Правда, если хотя бы одно из произведений нулевое, это должно считаться как разные знаки (правильнее сформулировать так: первое и минус второе (или наоборот) произведения неотрицательны; это выражает, что точка пересечения лежит по ту же сторону (нестрого) от каждого конца отрезка, что и другой конец).

Geen в сообщении #1280458 писал(а):

Отодвинем отрезок от окружности в десять раз (вдоль перпендикуляра из центра окружности на отрезок)

Это как раз ничего не портит:

svv в сообщении #1280426 писал(а):

Допустим, мы уже знаем, что прямая, на которой лежит отрезок $AB$, пересекает окружность с центром в $O$ и радиусом $r$.

(Или я не понял.)

[svv]

arseniiv, именно.

Geen
Наш язык таков, что возможности ещё теснее придвинуть предположения к их следствиям я не нашёл...

[atlakatl]

Упростим постановку: перенесём центр окружности в $(0;0)$.
Тогда координаты концов отрезка перейдут в $x_1=x_1-x_0$ и т.д.
Проверяем концы отрезка на $L_{1,2}<R$, - если выполняется для одного конца и не выполняется для другого, то пересечение.
Если оба конца отрезка на $L_{1,2}>R$, то проверяем, меньше ли расстояние до центра от середины отрезка, чем от каждого из концов. Если да, то находим минимальное расстояние до прямой, заданной точками $(x_1, y_1), (x_2, y_2)$:
$L_{\min}=\frac{x_2y_1-x_1y_2}{\sqrt{(y_2-y_1)^2+(x_2-x_1)^2}}$
Если $L_{\min}<R$, то имеем две точки пересечения отрезка с окружностью.

[atlakatl]

Переложил вышеизложенное на Паскаль:

program okr_otr; //Пересекает ли отрезок окружность?
var x0, y0, x1, y1, x2, y2, r, l1, l2, lsr, lmin :real;
begin
write('x0 центра окружности:'); readln(x0);
write('y0 центра окружности:'); readln(y0);
write('радиус r окружности:'); readln(r);
write('x1 отрезка:'); readln(x1);
write('y1 отрезка:'); readln(y1);
write('x2 отрезка:'); readln(x2);
write('y2 отрезка:'); readln(y2);
x1:=x1-x0; x2:=x2-x0; y1:=y1-y0; y2:=y2-y0;
l1:=sqrt(x1*x1+y1*y1); l2:=sqrt(x2*x2+y2*y2);
if ((l1<r) AND (l2>r)) OR ((l1>r) AND (l2<r)) then writeln('Одно пересечение')
else
  if (l1<r) AND (l2<r) then writeln('Пересечений нет')
  else
    begin
      lsr:=sqrt(power((x1+x2)/2,2)+power((y1+y2)/2,2));
      if (lsr>l1) OR (lsr>l2) then writeln('Пересечений нет')
      else
        begin
          lmin:=(x2*y1-x1*y2)/sqrt(power((y2-y1),2)+power((x2-x1),2));
          if lmin>r then writeln('Пересечений нет')
          else writeln('Два пересечения');
        end;
    end;
end.

[arseniiv]

Начнём разбор:

atlakatl в сообщении #1280479 писал(а):

$L_{\min}=\frac{x_2y_1-x_1y_2}{\sqrt{(y_2-y_1)^2+(x_2-x_1)^2}}$

Модуль забыли. И нет чтобы по-человечески написать $\lVert\mathrm r_1\wedge\mathrm r_2\rVert/\lVert\mathrm r_2-\mathrm r_1\rVert$ ($\wedge$ здесь понимается как внешнее или псевдоскалярное по желанию; во втором случае будет, конечно, модуль скаляра, а не норма бивектора).

-- Пн янв 01, 2018 20:30:03 --

atlakatl в сообщении #1280479 писал(а):

Если оба конца отрезка на $L_{1,2}>R$, то проверяем, меньше ли расстояние до центра от середины отрезка, чем от каждого из концов. Если да <…>

А если нет, чего? Возможны разные случаи.

-- Пн янв 01, 2018 20:33:51 --

Ну и код (и его вывод: введённые числа будут идти после двоеточий сразу без пробела) тоже можно было сделать красивее, и это не говоря о [syntax lang="pascal"] вместо [code]. Кроме того, код, вроде, никто и не просил. Или код программы целиком, а не отдельной функции.

-- Пн янв 01, 2018 20:36:01 --

Вообще же всё было устроено выше, и дальше там уже ничего не получится сократить. В одном из случаев придётся честно сравнивать, лежат точки пересечения на отрезке или нет. (А если нужно не только количество или факт пересечений, то тем более незачем срезать.)

[grizzly]

arseniiv в сообщении #1280534 писал(а):

...ничего не получится сократить. В одном из случаев придётся честно сравнивать, лежат точки пересечения на отрезке или нет.

Всё же чуть проще, кажется, смотреть не точки пересечения прямой с окружностью, а точку пересечения прямой с перпендикуляром к ней, восстановленным из центра окружности.

[atlakatl]

Про модуль да, забыл.
"По-человечески" написать можно, но в Паскале таких функций нет, всё равно придётся переходить к расчётной формуле.
Про "разные случаи" дошло:

Случай 3 я не учёл.
Надо проще. Если оба конца отрезка дальше $R$, то просто находим $L_{\min}$, сравнивая её с $R$

[arseniiv]

grizzly
Это подходит только для случая, когда оба конца отрезка вне окружности, а для нахождения точек пересечения это, в принципе, можно не проверять.

-- Пн янв 01, 2018 21:21:05 --

atlakatl в сообщении #1280550 писал(а):

но в Паскале таких функций нет

Так написали бы. Код от этого станет длиннее в строках, но кому нужно число строк?

atlakatl в сообщении #1280550 писал(а):

Если оба конца отрезка дальше $R$, то просто находим $L_{\min}$, сравнивая её с $R$

Вы точно учли случай ниже?

[atlakatl]

arseniiv в сообщении #1280555 писал(а):

Вы точно учли случай ниже?

Этот случай я пытался учесть вначале.
Надо подумать. Праздник ещё.

[EXE]

Все случаи. Прямая через две точки: пересекает, не пересекает, касается окружности.
Нам надо касается, пересекает.
Проверка на: точка отрезку принадлежит, не принадлежит через “гомотопическое” уравнение отрезка. Если параметр в переделах от 0 до 1, то принадлежит.

[arseniiv]

Или через скалярные, как svv предлагал. Ничего нового не получится.

[atlakatl]

Сделал по svv. Ну и в паскалевский тег обрамил:

Используется синтаксис Pascal

program okr_otr; //Пересекает ли отрезок окружность?
var x0, y0, x1, y1, x2, y2, r, l1, l2 :real;
var per :boolean;
begin
x0:=0; y0:=0; r:=2; //координаты центра и радиус окружности
x1:=2.3; y1:=-10; x2:=1.995; y2:=10; //координаты концов отрезка
x1:=x1-x0; x2:=x2-x0; y1:=y1-y0; y2:=y2-y0;
l1:=sqrt(x1*x1+y1*y1); l2:=sqrt(x2*x2+y2*y2);
if ((l1<=r) AND (l2>=r)) OR ((l1>=r) AND (l2<=r)) then per:=TRUE
else if (l1<r) AND (l2<r) then per:=FALSE //Оба конца внутри окружности
  else //Оба конца за окружностью
    begin
      var p1:=x1*(x2-x1)+y1*(y2-y1); var p2:=x2*(x2-x1)+y2*(y2-y1);
      if ((p1>=0) AND (p2<=0) OR (p1<=0) AND (p2>=0)) AND (abs((x2*y1-x1*y2)/sqrt((power((y2-y1),2)+power((x2-x1),2))))<=r) then per:=TRUE
      else per:=FALSE;
    end;
if per then writeln('Пересекает') else writeln('Пересечений нет');
end.
 

[Rak so dna]

Igor2323 только не вздумайте вставлять вот это:

atlakatl в сообщении #1280622 писал(а):

Сделал по svv. Ну и в паскалевский тег обрамил:

Используется синтаксис Pascal

program okr_otr; //Пересекает ли отрезок окружность?
var x0, y0, x1, y1, x2, y2, r, l1, l2 :real;
var per :boolean;
begin
x0:=0; y0:=0; r:=2; //координаты центра и радиус окружности
x1:=2.3; y1:=-10; x2:=1.995; y2:=10; //координаты концов отрезка
x1:=x1-x0; x2:=x2-x0; y1:=y1-y0; y2:=y2-y0;
l1:=sqrt(x1*x1+y1*y1); l2:=sqrt(x2*x2+y2*y2);
if ((l1<=r) AND (l2>=r)) OR ((l1>=r) AND (l2<=r)) then per:=TRUE
else if (l1<r) AND (l2<r) then per:=FALSE //Оба конца внутри окружности
  else //Оба конца за окружностью
    begin
      var p1:=x1*(x2-x1)+y1*(y2-y1); var p2:=x2*(x2-x1)+y2*(y2-y1);
      if ((p1>=0) AND (p2<=0) OR (p1<=0) AND (p2>=0)) AND (abs((x2*y1-x1*y2)/sqrt((power((y2-y1),2)+power((x2-x1),2))))<=r) then per:=TRUE
      else per:=FALSE;
    end;
if per then writeln('Пересекает') else writeln('Пересечений нет');
end.
 

себе в код, иначе (даже после исправления всех синтаксических ошибок) ваша прога вылетит, например при x0=0, y0=0, x1=2, y1=2, x2=2, y2=2, r=1 (и при большом множестве других значений). Лучше сами аккуратно оформите все случаи.