Принадлежность точки отрезку. Почему не работает классика?

Определить принадлежность точки отрезку, казалось бы, вполне себе тривиальная задача из школьного курса геометрии. Однако, есть определенные нюансы, которые заставляют усомниться в верности классической формулы:

$\displaystyle \frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}$

Содержание скрыть

Причины и постановка задачи

Классическое уравнение

Расширенная классика

Модификация уравнения

Итоговая функция

Почему такая большая функция получилась?

Классика всегда в моде или Математика — царица наук

Скачать

Причины и постановка задачи

Запросы «как найти принадлежность точки отрезку» уводят на страницу «Пересечение прямых, угол и координаты пересечения», где есть пункт «Принадлежность точки отрезку». В нем рассматривается факт принадлежности точки отрезку, уже после того, как мы определили точку пересечения прямых. То есть точка уже принадлежит прямым, и это абсолютно точно. Осталось только определиться, точка в отрезке между двумя точками отрезка, либо где-то на прямой мимо них.

Людям свойственно искать готовые решения, и код, представленный в статье вряд ли удовлетворит запросу «как найти принадлежность точки отрезку, заданный двумя точками«. Поэтому здесь задачу так и сформулируем:

Есть отрезок, заданный точками P1(x1,y1) и P2 (x2,y2) . Необходимо определить, принадлежит ли точка P(x,y) этому отрезку.

Классическое уравнение

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

Для совместимости с Delphi 7 введем тип вещественной точки:

type
{$IF CompilerVersion < 26}
  TxPoint = record
    X: Single;
    Y: Single;
  end;
{$ELSE} // >= XE5
  TxPoint = TPointF;
{$IFEND}

type

{$IF CompilerVersion < 26}

TxPoint = record

X: Single;

Y: Single;

end;

{$ELSE} // >= XE5

TxPoint = TPointF;

{$IFEND}

Почему бы не сделать сразу TPointF вместо типа TxPoint? Просто у меня гора старых исходников, где используется этот тип, а никакого TPointF не было ни в помине, ни в планах. Delphi 7 казалась вершиной инженерной мысли на тот момент.

В предложение uses дописываем следующее (ради TPointF, и чтобы компилятор XE не доставал хинтами):

interface

uses
  Windows, SysUtils, Classes, Graphics, Controls, Forms,
  ...
  {$IF CompilerVersion > 25} // >= XE5
  , System.Types
  {$IFEND}
  ;

interface

uses

Windows, SysUtils, Classes, Graphics, Controls, Forms,

...

{$IF CompilerVersion > 25} // >= XE5

, System.Types

{$IFEND}

;

Почему именно XE5? Если честно, нет возможности проверить, не ставить же ради этого всю линейку дельфей. Но в XE5 вещественная точка точно есть, а в Delphi 7 ее точно нет. Вот этим и объясняется выбор версии компилятора в директиве. Одни говорят, что TPointF появился в XE2, другие — аж в Delphi 2010. Короче, с таким директивным условием будет работать везде и точка.

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

function PtInSegment(const P1, P2, P: TxPoint; const Epsilon: extended;
  var res: TxPoint): Integer;
begin
  Result := 0;
  res := p;
  if
    // проверка Y-координаты
    SameValue(Abs(p1.Y-p.Y) + Abs(p2.Y-p.Y), Abs(p2.Y-p1.Y), Epsilon) and
    // проверка X-координаты
    SameValue(Abs(p1.X-p.X) + Abs(p2.X-p.X), Abs(p2.X-p1.X), Epsilon) and
    // используется классическая формула
    SameValue((p.x-p1.x)*(p2.y-p1.y) - (p.y-p1.y)*(p2.x-p1.x), 0, Epsilon)
  then
    Result := 3;
end;

function PtInSegment(const P1, P2, P: TxPoint; const Epsilon: extended;

var res: TxPoint): Integer;

begin

Result := 0;

res := p;

// проверка Y-координаты

SameValue(Abs(p1.Y-p.Y) + Abs(p2.Y-p.Y), Abs(p2.Y-p1.Y), Epsilon) and

// проверка X-координаты

SameValue(Abs(p1.X-p.X) + Abs(p2.X-p.X), Abs(p2.X-p1.X), Epsilon) and

// используется классическая формула

SameValue((p.x-p1.x)*(p2.y-p1.y) - (p.y-p1.y)*(p2.x-p1.x), 0, Epsilon)

then

Result := 3;

end;

SameValue — сравнивает два вещественных числа с учетом погрешности Epsilon. Находится в модуле Math, который надо подключить в предложении uses секции implementation.

Что происходит. Вначале проверяется допустимость координаты точки внутри координат отрезка. Условие необходимое, но недостаточное. Если координата может принадлежать отрезку, третьим условием проверяем нахождение точки на прямой, проходящей через точки отрезка.

Рис.1. Курсор точно на линии, но не определяет, что точка принадлежит отрезку

Если мы попытаемся по координатам курсора мыши определить, попала ли точка в отрезок, нас ждет фиаско. Складывается ощущение, что формула не работает, алгебра — отстой, все в жизни не так.

Расширенная классика

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

// сравнить две точки с учетом погрешности
function PtEqual(const P1,P2: TxPoint;
  const Epsilon: extended = 0.0): Boolean;
begin
  Result := SameValue(P1.X, P2.X, Epsilon) and
    SameValue(P1.Y, P2.Y, Epsilon);
end;

// классика с учетом попадания на точки P1 и P2
// режим нахождения на отрезке: 0 - мимо, 1 - p1, 2 - p2, 3 - между p1 и p2
function PtInSegmentEx(const P1, P2, P: TxPoint; const Epsilon: extended;
  var res: TxPoint): Integer;
begin
  Result := 0;
  res := p;
  if PtEqual(P1, P, Epsilon) then
    Result := 1
  else
  if PtEqual(P2, P, Epsilon) then
    Result := 2
  else
  if SameValue(Abs(p1.Y-p.Y) + Abs(p2.Y-p.Y), Abs(p2.Y-p1.Y), Epsilon) and
     SameValue(Abs(p1.X-p.X) + Abs(p2.X-p.X), Abs(p2.X-p1.X), Epsilon) and
     SameValue((p.x-p1.x)*(p2.y-p1.y) - (p.y-p1.y)*(p2.x-p1.x), 0, Epsilon)
  then
    Result := 3;
end;

// сравнить две точки с учетом погрешности

function PtEqual(const P1,P2: TxPoint;

const Epsilon: extended = 0.0): Boolean;

begin

Result := SameValue(P1.X, P2.X, Epsilon) and

SameValue(P1.Y, P2.Y, Epsilon);

end;

// классика с учетом попадания на точки P1 и P2

// режим нахождения на отрезке: 0 - мимо, 1 - p1, 2 - p2, 3 - между p1 и p2

function PtInSegmentEx(const P1, P2, P: TxPoint; const Epsilon: extended;

var res: TxPoint): Integer;

begin

Result := 0;

res := p;

if PtEqual(P1, P, Epsilon) then

Result := 1

else

if PtEqual(P2, P, Epsilon) then

Result := 2

else

if SameValue(Abs(p1.Y-p.Y) + Abs(p2.Y-p.Y), Abs(p2.Y-p1.Y), Epsilon) and

SameValue(Abs(p1.X-p.X) + Abs(p2.X-p.X), Abs(p2.X-p1.X), Epsilon) and

SameValue((p.x-p1.x)*(p2.y-p1.y) - (p.y-p1.y)*(p2.x-p1.x), 0, Epsilon)

then

Result := 3;

end;

Ну, во-первых, вот и разгадка, куда делись значения 1 и 2 из результатов предыдущей функции. Во-вторых, теперь в конечные точки отрезка попадает отлично, но между ними по-прежнему не хочет работать.

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

Выведем в интерфейс значения dx = (p2.x-p1.x), dy = (p2.y-p1.y) и т.д. Плюс результат работы функции (p.x-p1.x)*(p2.y-p1.y) — (p.y-p1.y)*(p2.x-p1.x). И убедимся, что при самых казалось бы максимально возможных приближениях к отрезку, результат ошеломляет своей двух- или трехзначной непохожестью на ноль.

Рис.2. Теперь определяет конечные точки, но между ними по-прежнему работает так себе…

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

На рисунке 2 прицел точно на линии, но разность координат, которую получаем из классического уравнения, и которая должна быть равна нулю, между тем равна:

f(x,y)=(x-x₁) * (y₂-y₁) — (y-y₁) * (x₂-x₁) = -16

Функция применима в точных расчетах, но не в векторном редакторе.

Модификация уравнения

Очевидно, надо вычислять как-то иначе. Например вычислять Y по имеющейся координате X и сравнивать с имеющейся координатой Y. Если разница меньше заданного Epsilon — точка принадлежит отрезку. Выразим Y из используемого уравнения прямой. Итак, дано:

$\displaystyle \frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}$

Выразим Y:

$\displaystyle y=\frac{(x-x_1) \times (y_2-y_1)}{x_2-x_1}+y_1$

И напишем еще одну функцию, в которой учтем ситуацию, когда (X₂-X₁) может быть равно нулю. Это ситуация вертикальной (или почти вертикальной) прямой.

function PtInSeg(const P1, P2, P: TxPoint; const Epsilon: extended;
  var res: TxPoint): Integer;
begin
  Result := 0;
  res := p;
  // сравнить с точкой P1
  if PtEqual(P1, P, Epsilon) then
  begin
    res := p1;
    Result := 1;
  end else
  // сравнить с точкой P2
  if PtEqual(P2, P, Epsilon) then
  begin
    res := p2;
    Result := 2
  end else
  // проверить на вхождение в координатный допуск отрезка
  if SameValue(Abs(p1.Y-p.Y) + Abs(p2.Y-p.Y), Abs(p2.Y-p1.Y), Epsilon) and
    SameValue(Abs(p1.X-p.X) + Abs(p2.X-p.X), Abs(p2.X-p1.X), Epsilon) then
  begin
    Result := 3;
    // это почти вертикальная линия, Y уже проверен условием выше
    if SameValue(p1.X,p2.X,Epsilon) then
    begin
      res.x := p1.X + (p2.X - p1.X) / 2;
      Exit;
    end;
    // посчитать Y и сравнить с точкой P
    res.Y := (p.X-p1.x)*(p2.Y-p1.y)/(p2.X-p1.x) + p1.Y;
    if SameValue(p.Y, res.y, Epsilon) then
      Exit;
    Result := 0;
  end;
end;

function PtInSeg(const P1, P2, P: TxPoint; const Epsilon: extended;

var res: TxPoint): Integer;

begin

Result := 0;

res := p;

// сравнить с точкой P1

if PtEqual(P1, P, Epsilon) then

begin

res := p1;

Result := 1;

end else

// сравнить с точкой P2

if PtEqual(P2, P, Epsilon) then

begin

res := p2;

Result := 2

end else

// проверить на вхождение в координатный допуск отрезка

if SameValue(Abs(p1.Y-p.Y) + Abs(p2.Y-p.Y), Abs(p2.Y-p1.Y), Epsilon) and

SameValue(Abs(p1.X-p.X) + Abs(p2.X-p.X), Abs(p2.X-p1.X), Epsilon) then

begin

Result := 3;

// это почти вертикальная линия, Y уже проверен условием выше

if SameValue(p1.X,p2.X,Epsilon) then

begin

res.x := p1.X + (p2.X - p1.X) / 2;

Exit;

end;

// посчитать Y и сравнить с точкой P

res.Y := (p.X-p1.x)*(p2.Y-p1.y)/(p2.X-p1.x) + p1.Y;

if SameValue(p.Y, res.y, Epsilon) then

Exit;

Result := 0;

end;

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

Рис.3. Все здорово определяет с учетом погрешности *Epsilon=12 pix*

Но, даже если мы упростили себе процесс «попадания» в отрезок, мы должны знать точные координаты на отрезке. Для этого у нас и появился тип вещественной точки TxPoint и возвращаемый параметр res. В этой версии функции мы производим расчет реальной точки на отрезке.

На рисунке 3 расчетная точка и ее координаты выделена коричневым цветом.

Однако, все равно есть нюанс. Если линия сильно вертикальна, то есть расстояние (X₂-X₁) невелико, попадать в линию все равно трудно.

Рис.3.1. На почти вертикальной линии функция снова капризничает

Связано с тем, что при уменьшении делителя, коим разность по X выступает в нашем случае, сильно вырастает результат, и чем расстояние (X₂-X₁) меньше, тем труднее попасть в Epsilon.

Итоговая функция

В стремлении к совершенству, всегда что-то незамысловатое, в пару строк кода, разрастается в какую-то все учитывающую портянку листинга.

Давайте проверять, что больше (X₂-X₁) или (Y₂-Y₁), и в зависимости от результата, будем высчитывать либо Y, либо X. Формулу для X не привожу, он очевидна.

function PtInSegEx(const P1, P2, P: TxPoint; const Epsilon: extended;
  var res: TxPoint): Integer;
var
  dx, dy, px, py: Single;
begin
  Result := 0;
  res := p;
  if PtEqual(P1, P, Epsilon) then
  begin
    res := p1;
    Result := 1
  end else
  if PtEqual(P2, P, Epsilon) then
  begin
    res := p2;
    Result := 2
  end else
  begin
    // просто для понятности кода
    dx := (p2.X-p1.X);
    dy := (p2.Y-p1.Y);
    px := (p.X-p1.X);
    py := (p.Y-p1.Y);

    // линия почти вертикальна
    if SameValue(dx,0,Epsilon) then
    begin
      // во избежание деления на ноль.
      // ситуация мифическая, т.к. проверена уже выше в точках, но...
      if SameValue(dy,0) then
        res.X := p1.X + dx/2
      else
        res.X := py*dx/dy + p1.x;
      // сравнить X точки с расчетным значением
      if SameValue(p.x, res.x, Epsilon) and
      // и проверить координату Y, которая должна быть в диапазон Y1..Y2
         SameValue(Abs(p1.Y-p.Y) + Abs(p2.Y-p.Y), Abs(p2.Y-p1.Y), Epsilon)
      then
        Result := 3;
      exit;
    end;

    // линия почти горизонтальна
    if SameValue(dy,0,Epsilon) then
    begin
      // dx=0 уже отработан условием выше, деления на 0 не боимся
      res.Y := px*dy/dx + p1.Y;
      if SameValue(p.y, res.y, Epsilon) and
         SameValue(Abs(p1.x-p.x) + Abs(p2.x-p.x), Abs(p2.x-p1.x), Epsilon)
      then
        Result := 3;
      exit;
    end;
    // проверка координат точки на валидность координатам отрезка
    if SameValue(Abs(p1.Y-p.Y) + Abs(p2.Y-p.Y), Abs(p2.Y-p1.Y), Epsilon) and
      SameValue(Abs(p1.X-p.X) + Abs(p2.X-p.X), Abs(p2.X-p1.X), Epsilon) then
    begin
      // x2-x1 больше подходит в качестве делителя,
      // считаем и сравниваем Y
      if (abs(dx) > abs(dy)) then
      begin
        res.Y := px*dy/dx + p1.Y;
        if SameValue(p.Y, res.Y, Epsilon) then
          Result := 3;
      end else
      // иначе считаем и сравниваем X
      begin
        res.X := py*dx/dy + p1.x;
        if SameValue(p.x, res.X, Epsilon) then
          Result := 3;
      end;
    end;
  end;
end;

function PtInSegEx(const P1, P2, P: TxPoint; const Epsilon: extended;

var res: TxPoint): Integer;

var

dx, dy, px, py: Single;

begin

Result := 0;

res := p;

if PtEqual(P1, P, Epsilon) then

begin

res := p1;

Result := 1

end else

if PtEqual(P2, P, Epsilon) then

begin

res := p2;

Result := 2

end else

begin

// просто для понятности кода

dx := (p2.X-p1.X);

dy := (p2.Y-p1.Y);

px := (p.X-p1.X);

py := (p.Y-p1.Y);

// линия почти вертикальна

if SameValue(dx,0,Epsilon) then

begin

// во избежание деления на ноль.

// ситуация мифическая, т.к. проверена уже выше в точках, но...

if SameValue(dy,0) then

res.X := p1.X + dx/2

else

res.X := py*dx/dy + p1.x;

// сравнить X точки с расчетным значением

if SameValue(p.x, res.x, Epsilon) and

// и проверить координату Y, которая должна быть в диапазон Y1..Y2

SameValue(Abs(p1.Y-p.Y) + Abs(p2.Y-p.Y), Abs(p2.Y-p1.Y), Epsilon)

then

Result := 3;

exit;

end;

// линия почти горизонтальна

if SameValue(dy,0,Epsilon) then

begin

// dx=0 уже отработан условием выше, деления на 0 не боимся

res.Y := px*dy/dx + p1.Y;

if SameValue(p.y, res.y, Epsilon) and

SameValue(Abs(p1.x-p.x) + Abs(p2.x-p.x), Abs(p2.x-p1.x), Epsilon)

then

Result := 3;

exit;

end;

// проверка координат точки на валидность координатам отрезка

if SameValue(Abs(p1.Y-p.Y) + Abs(p2.Y-p.Y), Abs(p2.Y-p1.Y), Epsilon) and

SameValue(Abs(p1.X-p.X) + Abs(p2.X-p.X), Abs(p2.X-p1.X), Epsilon) then

begin

// x2-x1 больше подходит в качестве делителя,

// считаем и сравниваем Y

if (abs(dx) > abs(dy)) then

begin

res.Y := px*dy/dx + p1.Y;

if SameValue(p.Y, res.Y, Epsilon) then

Result := 3;

end else

// иначе считаем и сравниваем X

begin

res.X := py*dx/dy + p1.x;

if SameValue(p.x, res.X, Epsilon) then

Result := 3;

end;

Рис.4. На почти вертикальной линии стало все отлично

Почему такая большая функция получилась?

В функции помимо факта принадлежности точки отрезку, также осуществляется проверка на конечные точки — чтобы можно было менять их расположение мышкой. Также, функция возвращает «истинную» точку на отрезке, полученную из приближенной, содержащую погрешность Epsilon.

Можно сократить, не считать конечные точки, не анализировать «вертикальность» и «горизонтальность». Можно взять за настоящую ту точку, которую анализируем и не считать «истинную». Код в этом случае сильно сократиться. Поэтому лучше иметь полный комплект, из которого можно удалить «лишнее» на ваш взгляд.

Зачем нужны такие ощутимо большие проверки на вертикальность и горизонтальность. Ну, во-первых мы освобождаем от условий последний блок вычислений, во-вторых, если убрать, скажем, проверку на dy, погрешность станет в два раза меньше. Потому что отработает это условие: Abs(p1.Y-p.Y) + Abs(p2.Y-p.Y). Имея идеальную горизонтальную линию, подведя курсор на Epsilon допустимый интервал, мы получим в итоге Epsilon + Epsilon = 2 * Epsilon и условие конечно не сработает. Сработает, если подведем на расстояние в два раза меньшее Epsilon.

Если всех этих тонкостей не требуется, можно смело использовать либо эту, либо вообще эту функцию.

Классика всегда в моде или Математика — царица наук

Теперь давайте полученную в результате предыдущей функции вещественную точку res подставим в первую функцию. И убедимся, что теоретическая принадлежность точки отрезку работает прекрасно, просто в пространстве грубых целочисленных точек мы не в состоянии гарантированно получить такую точку, которая удовлетворила бы уравнению. Но если мы ее рассчитаем и получим значения с плавающей запятой — все заработает как надо.

Рис.5. Результат применения рассчитанной точки для первой функции

На рисунке 5 добавлен результат функции f(x,y)=(x-x₁) * (y₂-y₁) — (y-y₁) * (x₂-x₁) для рассчитанной точки на отрезке. Он равен, как и следовало ожидать, нулю. А также результат вызова первой функции, которая использует это уравнение и возвращает 3, если точка принадлежит отрезку. Что мы воочию и видим.

1)Поэтому в графике надо избегать типов TPoint, даже если это вызывает необходимость постоянно их округлять для функций GDI.

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

Скачать

Друзья, спасибо за внимание!

Надеюсь, материал был полезен.

Не пропустите новых интересных штуковин, подписывайтесь на телегу. )))

Если есть вопросы, с удовольствием отвечу.

Исходники и исполняемый файл для GDI и Delphi 7. Проверен в XE 7, XE 10.

Исходники (Delphi 7, XE7, XE10) 11 Кб

Исполняемый файл (zip) 213 Кб

Исполняемый файл c GDI+ (zip) 216 Кб

Как подключить GDI+ в Delphi 7 и без проблем скомпилировать в XE 7, XE 10 читаем в этой статье. Там же забираем исходники.

Чтобы нарисовать отрезок, нажмите мышь и, не отпуская, ведите курсор. При отпускании отрезок зафиксируется. При повторном нажатии начнет рисоваться новый отрезок.

За концы отрезка можно таскать. Если попали на отрезок, т.е. видна коричневая точка, можно таскать весь отрезок.

Исходники намеренно выложены в D7 варианте.

При компиляции в XE10 следует снять галочку с Enable High-DPI

5 11 голоса

Рейтинг статьи

11 комментариев

Старые

Новые Популярные

Межтекстовые Отзывы

Посмотреть все комментарии

BlackWitcher

Участник

2 лет назад

Четко, понятно и вполне доступным языком описан нюанс, позволяющий сэкономить массу времени для подобных задач. Спасибо!

Ответить

Roman

Автор

Ответить на BlackWitcher

2 лет назад

Спасибо на добром слове! )))

Ответить

Crystaly

3 месяцев назад

я делал ~~намного~~ проще, геометрически:

// ---------------------------------------------------------
// Выяснить - координаты (x,y) рядом с заданным отрезком (x1,y1)(x2,y2) или нет?
// ---------------------------------------------------------
function IsCloseToLine(x, y, x1, y1, x2, y2, delta : Integer) : Boolean;
var
  delta2 : Integer;     // чувствительность обнаружения отрезка (возведено в квадрат)
  a2, b2, c2 : TFloat;    // квадраты сторон треугольника (обязательно вещественный тип !)
  s2 : TFloat;        // квадрат площади треугольника
begin
  delta2 := sqr(delta);       // Возвести в квадрат - для ускорения вычислений
  a2 := sqr(x - x1) + sqr(y - y1);  // квадрат 1-й стороны треугольника
  b2 := sqr(x - x2) + sqr(y - y2);  // квадрат 2-й стороны треугольника
  c2 := sqr(x1 - x2) + sqr(y1 - y2); // квадрат длины связи
  s2 := (sqr(a2 + b2 + c2) - 2*(sqr(a2) + sqr(b2) + sqr(c2))) / 16; // формула Герона (для квадратов сторон)
  // первая проверка - попадают координаты (x,y) внутрь окружности вокруг отрезка (x1,y1)(x2,y2)?
  // вторая проверка - расстояние координаты (x,y) до отрезка (x1,y1)(x2,y2) меньше "дельты"?
  Result := ((a2 + b2) < c2) and ((4 * s2 / c2) < delta2);
end;

// ---------------------------------------------------------

// Выяснить - координаты (x,y) рядом с заданным отрезком (x1,y1)(x2,y2) или нет?

// ---------------------------------------------------------

function IsCloseToLine(x, y, x1, y1, x2, y2, delta : Integer) : Boolean;

var

delta2 : Integer; // чувствительность обнаружения отрезка (возведено в квадрат)

a2, b2, c2 : TFloat; // квадраты сторон треугольника (обязательно вещественный тип !)

s2 : TFloat; // квадрат площади треугольника

begin

delta2 := sqr(delta); // Возвести в квадрат - для ускорения вычислений

a2 := sqr(x - x1) + sqr(y - y1); // квадрат 1-й стороны треугольника

b2 := sqr(x - x2) + sqr(y - y2); // квадрат 2-й стороны треугольника

c2 := sqr(x1 - x2) + sqr(y1 - y2); // квадрат длины связи

s2 := (sqr(a2 + b2 + c2) - 2*(sqr(a2) + sqr(b2) + sqr(c2))) / 16; // формула Герона (для квадратов сторон)

// первая проверка - попадают координаты (x,y) внутрь окружности вокруг отрезка (x1,y1)(x2,y2)?

// вторая проверка - расстояние координаты (x,y) до отрезка (x1,y1)(x2,y2) меньше "дельты"?

Result := ((a2 + b2) < c2) and ((4 * s2 / c2) < delta2);

end;

Пояснения.
x, y — координаты клика мышки в канве
x1, y1, x2, y2 — координаты концов отрезка в канве
delta — точность обнаружения отрезка, количество точек канвы
Концы отрезка и точка образуют треугольник. Сначала проверяю, находится ли точка около отрезка. Для этого сравниваю квадрат длины отрезка и сумму квадратов расстояний от точки до концов отрезка. Если сумма меньше, значит точка внутри окружности описанной вокруг отрезка (то что надо) ( если равны — точка на окружности; если больше — вне окружности)
Если точка внутри окружности, определяю расстояние от точки до отрезка, Расстояние (высота треугольника) равно удвоенная площадь разделить на длину основания. основание — длина отрезка. Площадь считается по формуле Герона (так как известны длины строн треугольника)
Чтобы не делать лишних вычислений, не вычисляю корни, все вычисления делаю в квадратах, соотношения остаются верны.
Цифра 2 в именах переменных (кроме x2, y2) обозначает квадрат (вторая степень)

Ответить

Roman

Автор

Ответить на Crystaly

3 месяцев назад

Это очень хороший и красивый способ.
Ещё бы дополнить вещественностью координат, возвратом реальной точки на прямой, и анализом, куда попали — мимо, на концы отрезка или на отрезок между.
И это была бы просто бомба.

Еще способ. Найти перпендикуляр из точки к отрезку и сравнить длины. Работает шустро и точку на прямой возвращает, даже если она не на отрезке.

// Найти перпендикуляр из точки P3 на прямую (P1,P2)
// https://t.me/ip76ru/89
function CalcPerpendicularBase(
  const P1,P2,P3: TPointF): TPointF;
var dx, dy, L, A: Double;
begin
  dx := P2.x-P1.x;
  dy := P2.y-P1.y;
  L := dx*dx + dy*dy;
  if IsZero(L) then exit(P1);
  A := ((P3.x-P1.x)*dx + (P3.y-P1.y)*dy) / L;
  Result := PointF(P1.x + A*dx, P1.y + A*dy);
end;

// P-точка мыши, P1,P2 - концы отрезка, P0 - точка на прямой
function IsSnapToLine(const P,P1,P2: TPointF; Eps : Double;
  out P0: TPointF): Integer;
var L1, L2, L0: Double;
begin
  P0 := CalcPerpendicularBase(P1,P2,P);
  if P0.Distance(P) > Eps then exit(0);
  L1 := P0.Distance(P1);
  L2 := P0.Distance(P2);
  L0 := P1.Distance(P2);
  if IsZero(L1+L2-L0, Eps) then exit(3) else exit(0);
end;

// Найти перпендикуляр из точки P3 на прямую (P1,P2)

// https://t.me/ip76ru/89

function CalcPerpendicularBase(

const P1,P2,P3: TPointF): TPointF;

var dx, dy, L, A: Double;

begin

dx := P2.x-P1.x;

dy := P2.y-P1.y;

L := dx*dx + dy*dy;

if IsZero(L) then exit(P1);

A := ((P3.x-P1.x)*dx + (P3.y-P1.y)*dy) / L;

Result := PointF(P1.x + A*dx, P1.y + A*dy);

end;

// P-точка мыши, P1,P2 - концы отрезка, P0 - точка на прямой

function IsSnapToLine(const P,P1,P2: TPointF; Eps : Double;

out P0: TPointF): Integer;

var L1, L2, L0: Double;

begin

P0 := CalcPerpendicularBase(P1,P2,P);

if P0.Distance(P) > Eps then exit(0);

L1 := P0.Distance(P1);

L2 := P0.Distance(P2);

L0 := P1.Distance(P2);

if IsZero(L1+L2-L0, Eps) then exit(3) else exit(0);

end;

Ответить

Crystaly

Ответить на Roman

3 месяцев назад

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

Если это надо для конкретной задачи, то почему бы и нет. Мой пример из задачи (простейший 2D-CAD), где был массив отрезков (с вещественными «мировыми» координатами) которые отображались на канве. Надо было мышкой тыкать по канве и выбирать отрезки. Оказалось, что вычисления в координатах канвы проще, чем в вещественных координатах. Предварительно вещественные координаты отрезков пересчитываются в координаты канвы и далее передаются в функцию IsCloseToLine(…)

расчет реальной точки на прямой

это практически для чего можно применить?

куда попали — мимо, на концы отрезка или на отрезок между.

это практически для чего можно применить?

Ответить

Roman

Автор

Ответить на Crystaly

3 месяцев назад

Если это надо для конкретной задачи, то почему бы и нет.

Интересует работа? Delphi, графика?

Ответить

Crystaly

Ответить на Roman

3 месяцев назад

Интересует

Ответить

Roman

Автор

Ответить на Crystaly

3 месяцев назад

Ответил в телегу

Ответить

Roman

Автор

Ответить на Crystaly

2 месяцев назад

Возможно, с телегой не угадал и напугал адресата ))) Ответил в чат, который в личном кабинете

Ответить

Roman

Автор

Ответить на Crystaly

3 месяцев назад

Повторюсь, это очень хорошее решение.

Я не стал описывать разные варианты решения, в том числе и приведённый в комментарии выше про перпендикуляр, потому что не по теме статьи. Статья отвечает на вопрос, почему простая формула не работает, как сделать так, чтобы она заработала, и что формула на самом деле верна. Есть индивиды, знаете, которые ставят под сомнение.

Так вот, вашего варианта у меня не было. Поэтому, спасибо )))
Возможно, засяду написать именно про это — принадлежит ли точка отрезку, и какие способы есть. Ваш способ безусловно включу. Поэтому было бы неплохо указать про себя побольше в профиле, и вообще о себе, может другие ссылки есть, телега там, сайт ))) Я дам ссылку, что дескать это подсказал Crystaly. С удовольствием прорекламирую.

Расчёт реальной точки на прямой, попадание на концы отрезков — масса применений. Например, определить, это я продолжаю строить уже построенную ломаную, или делаю разветвление, новую ломаную, которая прилипает в этой точке. Мне сейчас что двигать — точку или весь отрезок? Хочу вытянуть кривую из отрезка — мне нужна прям супер-вещественная точка на этом отрезке.

Ответить

Crystaly

Ответить на Roman

3 месяцев назад

Ага понял. Вспомнились «точки привязки» в Автокаде.Я не просто так спрашивал, иногда есть какой-то алгоритм, но не знаешь где его практически применить с пользой.

Ответить