VPF::Точка в фигуре - Форум программистов

maxim1000

Дата 25.10.2006, 12:31 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 1
Всего: 110

если фигура задана последовательностью точек контура, то есть простой способ: проводим луч в любом направлении (удобно в горизонтальном или вертикальном) и считаем, сколько раз он пересечёт контур
если чётное количество раз - точка за пределами фигуры, иначе - внутри

--------------------

qqq

Rodman

Дата 25.10.2006, 12:41 (ссылка)

(нет голосов)

Загрузка ...

CIO

Профиль
Группа: Участник
Сообщений: 6144
Регистрация: 7.5.2006
Где: Ukraine ⇛ Kyiv ci ty

Репутация: нет
Всего: 122

Твоя фигура описывается по формулам? Если да то просто проверяй вхождение х и у...

--------------------

CRM с функцией АвтоОбзвона

Лотереи мира

Alexeis

Дата 25.10.2006, 12:46 (ссылка)

(нет голосов)

Загрузка ...

Амеба

Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

Репутация: 55
Всего: 459

maxim1000, Это похоже на мой способ если линию проводить горизонтально. smile

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

--------------------

Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

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

rounin

Дата 25.10.2006, 14:11 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 10.5.2006

Репутация: 1
Всего: 1

Код


function PtInPolygon(const P: array of TPointF; N: Integer; X, Y: TFloat): Boolean;
var
  i, j, k, Count, Intersect: Integer;
  t: TFloat;
        function MaxY(i, j: Integer; var k: Integer): TFloat;
        begin
          if P[i].Y > P[j].Y then
          begin Result := P[i].Y; k := i; end else
          begin Result := P[j].Y; k := j; end;
        end;

        function MinY(i, j: Integer; var k: Integer): TFloat;
        begin
          if P[i].Y > P[j].Y then
          begin Result := P[j].Y; k := j; end else
          begin Result := P[i].Y; k := i; end;
        end;
begin
  Count := N;
  Intersect := 0;
  for i := 0 to Count - 1 do
  begin
    j := (i+1)mod Count;
    if not(    ( Y<P[i].Y )and( Y<P[j].Y )   )and
       not(    ( Y>P[i].Y )and( Y>P[j].Y )   )and
       not(    P[i].Y =  P[j].Y              )then
         if MaxY(i, j, k) = Y then
         begin
           if P[k].X > X then Inc(Intersect)
         end
         else
         if not (MinY(i, j, k) = Y) then
         begin
           t := (Y - P[i].Y )/( P[j].Y - P[i].Y );
           if (t>0)and(t<1)and(P[i].X+t*(P[j].X-P[i].X)>X)then Inc(Intersect);
         end;
  end;
  Result := Intersect mod 2 = 1;
end;

Это сообщение отредактировал(а) rounin - 26.10.2006, 13:21

Bitter

Дата 26.10.2006, 00:49 (ссылка)

(нет голосов)

Загрузка ...

Опытный лентяй

Профиль
Группа: Завсегдатай
Сообщений: 1209
Регистрация: 15.8.2004
Где: Харьков, Ukraine

Репутация: 6
Всего: 27

А я тут вот какой алгоритм придумал (правда он сложноват, но зато подходит и для 3D случая):

Для того, чтобы определить находится ли точка внутри выпуклого(!) многоугольника, необходимо вычислить углы между нормалью i-й грани и вектором от точки до середины i-й грани. Если все углы больше 90 градусов, значит точка лежит внутри многоугольника.

Чтобы определить лежит ли точка внутри произвольного многоугольника, необходимо сначала разбить его на треугольники (треугольник - выпуклая фигура). Если точка лежит в одном из треугольников - она попадает в область всей фигуры.

В 3D случае объект нужно разбивать на пирамиды.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Delphi: Звук, графика и видео \| Следующая тема »