Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Delphi: Звук, графика и видео > Точка в фигуре

Автор: vasisualiiL 25.10.2006, 06:27

У меня на форме нарисованна фигура из множества точек. Когда я кликаю мышкой, как мне определить
попал я внутрь фигруы или нет? Подскажите пожалуйста... smile

Автор: Romikgy 25.10.2006, 09:09

а что за фигура?

Автор: Alexeis 25.10.2006, 09:17

Для этого можно воспользоваться возможностями винды.
1) Создается регион, например полигональный (по точкам периметра) или из квадратов (сканируя по строкам)
Функции CreatePolygonRgn, CreatePolyPolygonRgn, CreateRectRgn, CombineRgn
2) Проверяем попадание в заданный регион точки PtInRegion

Более подробно о этих функциях можно узнать в MSDN в разделе "Region Functions" (Windows GDI)

Добавлено @ 09:19
У меня был где-то даже код создания такого региона по битмапу (задается цвет прозрачности и все что другого цвета становится регионом)

Автор: vasisualiiL 25.10.2006, 09:32

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

Автор: vasisualiiL 25.10.2006, 10:11

и еще хуже smile

по-моему придется обойтись без winapi smile

Автор: Alexeis 25.10.2006, 10:49

Цитата(vasisualiiL @ 25.10.2006, 10:11

)

по-моему придется обойтись без winapi

Это как

под Kylix?

Автор: vasisualiiL 25.10.2006, 11:07

Угу и под него то же.

Добавлено @ 11:09
А вообще с Kylix ещё вопрос, просто это надо решить по разным причинам без winapi smile

Автор: Alexeis 25.10.2006, 11:21

Тогда нужно заносить точки периметра каждого блока в матрицу
Например если картинка такая
--------------------------------------------------------------
|12345678901234567890123456789012345678|
|-------------------------------------------------------------|
|00000000000111111100000011111111100000|
|00000000011110001111110000001111111111|
|00000000000111111100000000111000000000|
---------------------------------------------------------------
например
первая строка будет иметь значения (12,18)(25,33)
Вторая строка будет иметь значения (10, 13)(17,22)(29,38)
Третья строка будет иметь значения (12, 18)(27,29)
Если у нас точка скажем (1, 19), то мы выбираем первую строку и проверяем, попало ли значение 19 - в один из указанных диапазонов. В данном случае 19 > 18 > 12 и 19 < 25 < 33, т.е. не попало ни в один из диапазонов. Можно сделать свою структуру
1) число диапазонов
2) второе динамический массив диапазонов.

Т.о. Получим для каждой строки по одной такой структуре.

Автор: Rodman 25.10.2006, 11:27

Ну ты же ее по координатам формируешь (если она у тебя из точек состоит)

нельзя что ли обрабатывать OnMouseDown и по координатам сравнивать???

Автор: maxim1000 25.10.2006, 11:32

первый вопрос, без прояснения которого нормально и обсудить-то не получится:
как задана фигура?
1. используется ли информация с Canvas формы?
2. или есть какое-то внутреннее представление?
в первом случае GetPixel
во втором - зависит от способа задания фигуры

Автор: vasisualiiL 25.10.2006, 11:59

Наверное плохо объяснил ( ну бывает smile

) есть массив с коррдинатами точек, по этому массиву отрисовывем (или не отрисовываем) фигуру, и есть некакя точка с координатами (х,у) не важно как полученная, кликом ли мышкой или через переменную, и необходимо определить попадает ли эта точка в контур. Фигура может бать самой призвольной формы и слюбым количеством вершин (ух писать устал smile

)

Добавлено @ 12:01

Цитата(alexeis1 @ 25.10.2006, 11:21

)

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

и т.д.

К своему стыду ничего не понял smile

Автор: Alexeis 25.10.2006, 12:02

vasisualiiL, Фигура односвязная или многосвязная (целая или из кусков)? Есть ли пустоты?

Добавлено @ 12:08

Цитата(vasisualiiL @ 25.10.2006, 11:59

)

К своему стыду ничего не понял

Такое представление удобно если картинка задана битмапом. Единицы - это то что внутри области нули все что снаружи. Один диапазон это фрагмент (часть строки) состоящий из одних только единиц. Задается он по Х координате (начало, конец) по Y координате определяется номер строки.
Таким образом если начало<X<конец - то точка внутри фигуры иначе она либо в другом диапазоне этой же строки или вне фигуры.

Автор: vasisualiiL 25.10.2006, 12:09

Фигура целая, просто замкнутый контур.
готов выложить маленький рисунок, но не знаю как... smile

Автор: Rodman 25.10.2006, 12:17

Когда пишешь сообщение внизу можно прикрепить файл... так и кинь

Автор: vasisualiiL 25.10.2006, 12:30

Вот примерно так smile

Маленько грубовато... но принцип понятен

Автор: maxim1000 25.10.2006, 12:31

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

Автор: Rodman 25.10.2006, 12:41

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

Автор: Alexeis 25.10.2006, 12:46

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

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

Автор: rounin 25.10.2006, 14:11

Код


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;

Автор: Bitter 26.10.2006, 00:49

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

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

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

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