powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Определение принадлежности точки многоугольнику
8 сообщений из 8, страница 1 из 1
Определение принадлежности точки многоугольнику
    #40075496
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Достался мне в наследство код. Код ОЧЕНЬ грязный и местами очень трудно дешифруемый на предмет "А что автор имел в виду".

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

Потому, что я не могу понять, что за алгоритм использован
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
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
...
Рейтинг: 0 / 0
Определение принадлежности точки многоугольнику
    #40075499
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_,

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

если сумма углов равна +-2*pi, то внутри,
если 0, то снаружи.
...
Рейтинг: 0 / 0
Определение принадлежности точки многоугольнику
    #40075506
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вот здесь http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf

показано, что step - приближение для угла при большом числе вершин
...
Рейтинг: 0 / 0
Определение принадлежности точки многоугольнику
    #40075509
Фотография defecator
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
а мне нравится моя реализация

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
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;
...
Рейтинг: 0 / 0
Определение принадлежности точки многоугольнику
    #40075571
Фотография _avz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
defecator,

Хотел написать "Халявщик!", но призадумался: а как реализовано у меня?
глянул - блин, так же...
...
Рейтинг: 0 / 0
Определение принадлежности точки многоугольнику
    #40075697
Гаджимурадов Рустам
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_avz> у меня ... так же...

Скорость с нормальными алгоритмами пробовали сравнить?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Определение принадлежности точки многоугольнику
    #40075721
Фотография defecator
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
Гаджимурадов Рустам
_avz> у меня ... так же...

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


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

Понятно, что для приложений, которым биллиарды полигонов нужно обрабатывать, будут и алгоритмы другие
...
Рейтинг: 0 / 0
Определение принадлежности точки многоугольнику
    #40075722
Фотография _avz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Гаджимурадов Рустам,

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

Десятки тысяч полигонов на экране перебирает без особо заметных тормозов при тычке мышью, и ладно
...
Рейтинг: 0 / 0
8 сообщений из 8, страница 1 из 1
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Определение принадлежности точки многоугольнику
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]