Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Delphi Новый топик    Ответить
 Определение принадлежности точки многоугольнику  [new]
_Vasilisk_
Member

Откуда: Украина, Харьков
Сообщений: 12885
Достался мне в наследство код. Код ОЧЕНЬ грязный и местами очень трудно дешифруемый на предмет "А что автор имел в виду".

Но я не о том. Есть там функция определения принадлежности точки многоугольнику. Может кто-то посмотреть его на предмет адекватности алгоритма и реализации самого алгоритма?

Потому, что я не могу понять, что за алгоритм использован
function IsInPoly(const ARegion: array of TPoint; const ASearchPoint:
  TPoint): Boolean;
var
  LPrevPoint, LCurPoint: TPoint;
  Li: Integer;
  DX, DY, StepX, StepY: Integer;
  Step: Double;
  Rotation: Double;
begin
  LPrevPoint := ARegion[0];
  Rotation := 0;
  for Li := 1 to Length(ARegion) - 1 do begin
    LCurPoint := ARegion[Li];
    DX := LCurPoint.X - LPrevPoint.X;
    DY := LCurPoint.Y - LPrevPoint.Y;
    StepX := LPrevPoint.X - ASearchPoint.X;
    StepY := LPrevPoint.Y - ASearchPoint.Y;
    if (StepX <> 0) or (StepY <> 0) then begin
      Step := (DX * StepY - DY * StepX) / (StepX * StepX + StepY * StepY);
      Rotation := Rotation + Step;
    end;
    LPrevPoint := LCurPoint;
  end;
  Result := (Abs(Rotation) > 5);
end;
Тут, как я понял (DX, DY) - это вектор от предыдущей точки к следующей, а (StepX, StepY) от искомой к предыдущей. А что такое Step и Rotation?


С уважением, Vasilisk

Сообщение было отредактировано: 3 июн 21, 19:33
3 июн 21, 19:41    [22331085]     Ответить | Цитировать Сообщить модератору
 Re: Определение принадлежности точки многоугольнику  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 2075
_Vasilisk_,

похоже на подсчет оборотов:

если сумма углов равна +-2*pi, то внутри,
если 0, то снаружи.
3 июн 21, 20:17    [22331091]     Ответить | Цитировать Сообщить модератору
 Re: Определение принадлежности точки многоугольнику  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 2075
вот здесь http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf

показано, что step - приближение для угла при большом числе вершин
3 июн 21, 20:36    [22331100]     Ответить | Цитировать Сообщить модератору
 Re: Определение принадлежности точки многоугольнику  [new]
defecator
Member

Откуда:
Сообщений: 39787
а мне нравится моя реализация

function PointInPolygon(const P: TPoint; const Points: array of TPoint): boolean;
type
  PPoints = ^TPoints;
  TPoints = array[0..0] of TPoint;
var
  Rgn: HRgn;
begin
  Rgn := CreatePolygonRgn(PPoints(@Points)^, High(Points) + 1, WINDING);
  try
    Result := PtInRegion(Rgn, P.X, P.Y);
  finally
    DeleteObject(Rgn);
  end;
end;
3 июн 21, 21:05    [22331103]     Ответить | Цитировать Сообщить модератору
 Re: Определение принадлежности точки многоугольнику  [new]
_avz
Member

Откуда: Пермь
Сообщений: 2845
defecator,

Хотел написать "Халявщик!", но призадумался: а как реализовано у меня?
глянул - блин, так же...
4 июн 21, 09:11    [22331193]     Ответить | Цитировать Сообщить модератору
 Re: Определение принадлежности точки многоугольнику  [new]
Гаджимурадов Рустам
Member

Откуда:
Сообщений: 62803
_avz> у меня ... так же...

Скорость с нормальными алгоритмами пробовали сравнить?

Posted via ActualForum NNTP Server 1.5

4 июн 21, 15:01    [22331408]     Ответить | Цитировать Сообщить модератору
 Re: Определение принадлежности точки многоугольнику  [new]
defecator
Member

Откуда:
Сообщений: 39787
Гаджимурадов Рустам
_avz> у меня ... так же...

Скорость с нормальными алгоритмами пробовали сравнить?


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

Понятно, что для приложений, которым биллиарды полигонов нужно обрабатывать, будут и алгоритмы другие
4 июн 21, 16:17    [22331478]     Ответить | Цитировать Сообщить модератору
 Re: Определение принадлежности точки многоугольнику  [new]
_avz
Member

Откуда: Пермь
Сообщений: 2845
Гаджимурадов Рустам,

Увы.
Руки до оптимизации не доходят.

Десятки тысяч полигонов на экране перебирает без особо заметных тормозов при тычке мышью, и ладно
4 июн 21, 16:23    [22331480]     Ответить | Цитировать Сообщить модератору
Все форумы / Delphi Ответить