powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как определить принадлежит ли точка прямоугольнику
25 сообщений из 108, страница 3 из 5
Как определить принадлежит ли точка прямоугольнику
    #35789047
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
КартежникmaytonЭто как "по цвету" ?
Ну я думал закрашивать фигуры(тока еще не придумал как), и каждой присваивать свой цвет, они могут повторятся но не должны совпадать с фоном за фигурой. Найти максимально удаленные точки фигуры. Если заданная точка находится в этом получившемся прямоугольнике, то остается проверить ее цвет
Не максимально удаленные точки, а искать по координатам минимальный x и y, максимальный x и y.
Потом получится прямоугольник
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35789056
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Плохой метод. Ты отказываешься от математически строгого алгоритма в пользу численного метода, который к тому-же потребует дополнительную память.
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35789060
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПлохой метод. Ты отказываешься от математически строгого алгоритма в пользу численного метода, который к тому-же потребует дополнительную память.
Это же на время. Чтоб другие функции программы сделать. А функцию inpoly(в многоугольнике) могу в любой момент переделать. Как только алгоритм оптимизирую и доведу до ума.
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35789068
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Лентяй
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35789072
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЛентяй
Что есть то есть. Просто не думал что застряну на этом
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35789728
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
1)
x1:=x*cosang+y*sinang; y1:=x*sinang-y*cosang;

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

P.S. Данное сообщение просто немного глубже описывает (и немного изменяет) раннее данный mayton'ом ответ. Годиться только для прямоугольника :)
2)
Если же отбрасывать луч с точки влево (по-моему самый оптимальный и действенный алгоритм), то тут я не могу понять, почему
maytonДа. Этот метод годится только для выпуклых. Вогнутые надо будет разбивать на объединение нескольких выпуклых или делать сложные проверки с "исключением" впуклой области, если есть возможность. В качестве примера - проверка попадания точки в "бублик" аппроксимированный многоугольником. Нарисуйте пожалуйста кто-нибуть фигуру, к котрой данный метод будет неприменим... )) (просто к сожалению я не понял что это за фигура: "бублик" аппроксимированный многоугольником :) )
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35789912
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Програмёр (просто к сожалению я не понял что это за фигура: "бублик" аппроксимированный многоугольником :) )представь себе кольцо
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35789927
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
egorychПрограмёр (просто к сожалению я не понял что это за фигура: "бублик" аппроксимированный многоугольником :) )представь себе кольцо

Представил... Но кольцо полностью подходит под этот алгоритм... )))
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35789945
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
кольцо - всегда особый случай.
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35789957
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
egorychкольцо - всегда особый случай.

Согласен ))) Но во-первых, в данном случае мы не можем говорить про идеальное кольцо (так, как наше кольцо будет многоугольником с очень большим количеством граней). А во-вторых, даже если мы и будем иметь идеальное кольцо (хотя с "во-первых" следует, что не будем), то отброшенный влево из точки луч пересечёт: 1 грань - если точка будет внутри кольца, 0 или 2 грани - если она будет за пределами кольца ))) тут всё просто... )))
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35789964
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Единственное, что могу ещё добавить, так это то, что в данном алгоритме есть несколько исключений, и так как я не очень понимаю тот код, что привели на форуме ранее, то перечислю все исключения которые вижу (в случае, если их не учли, считаю что лучше бы это сделать):
1. Когда точка принадлежит одной из граней многоугольника (получим пересечение двух граней, но точка будет лежать в пределах многоугольника)
2. Если одна или больше граней многоугольника принадлежат лучу, отброшенному с точки (ну то есть иными словами они совпадают с лучём, тогда и луч будет проходить через 2 или более точек).
3. Когда данная точка совпадает с одной из вершин многоугольника.
Хм... вроде всё... придумаю ещё какое-то исключение - напишу ;)
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35789965
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
наш волшебный луч может попасть в вершину, мы же говорим о многоугольниках. этот момент придётся проверить.
ЗЫ математически всё верно, но: нам таки потребуется как-то посчитать угол, на который мы поворачиваем систему координат.
ЗЫЫ проблемы округления встанут перед нами во всей красе при таком способе. компьютер плохо справляется с вычислениями вещественных чисел
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35789989
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
egorychнаш волшебный луч может попасть в вершину, мы же говорим о многоугольниках. этот момент придётся проверить.
ЗЫ математически всё верно, но: нам таки потребуется как-то посчитать угол, на который мы поворачиваем систему координат.
ЗЫЫ проблемы округления встанут перед нами во всей красе при таком способе. компьютер плохо справляется с вычислениями вещественных чисел

там, где с лучём - ничего не поворачивается... Если же это идёт обсуждение описанного мной метода, то да... там есть поворот, но угол поворота высчитывать не надо, так как нам нужны только косинус и синус этого угла (а их можно найти по координатам точек, ограничивающих выбранную как базис грань (ну типа х/длина = синус, а у/длина = косинус) ).

Да и вообще я ведь признался, что приведённый мной метод довольно отстойный ))) Так что лучше юзать алгоритм с лучём ;)
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35790040
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот еще нашел кое что с Дельфи ворлд
Код: plaintext
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.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
 function  PtInRgn(TestPolygon :  array   of  TPoint;  const  P : TPoint): boolean;
  var 
   ToTheLeftofPoint, ToTheRightofPoint : byte;
   np : integer;
   OpenPolygon : boolean;
   XIntersection : real;
  begin 
   ToTheLeftofPoint :=  0 ;
   ToTheRightofPoint :=  0 ;
   OpenPolygon := False;

    {Prufen ob das Polygon geschlossen ist} 
    {tests if the polygon is closed} 

    if   not  ((TestPolygon[ 0 ].X = TestPolygon[High(TestPolygon)].X)  and 
     (TestPolygon[ 0 ].Y = TestPolygon[High(TestPolygon)].Y))  then 
     OpenPolygon := True;

    {Tests fur jedes Paar der Punkte, um zu sehen wenn die Seite zwischen 
   ihnen, die horizontale Linie schneidet, die TestPoint durchlauft} 
    {tests for each couple of points to see if the side between them 
   crosses the horizontal line going through TestPoint} 

    for  np :=  1   to  High(TestPolygon)  do 
      if  ((TestPolygon[np -  1 ].Y <= P.Y)  and 
       (TestPolygon[np].Y > P.Y))  or 
       ((TestPolygon[np -  1 ].Y > P.Y)  and 
       (TestPolygon[np].Y <= P.Y))
        {Wenn es so ist}      {if it does} 
        then 
      begin 
        {berechnet die x Koordinate des Schnitts} 
        {computes the x coordinate of the intersection} 

       XIntersection := TestPolygon[np -  1 ].X +
         ((TestPolygon[np].X - TestPolygon[np -  1 ].X) /
         (TestPolygon[np].Y - TestPolygon[np -  1 ].Y)) * (P.Y - TestPolygon[np -  1 ].Y);

        {Zahler entsprechend verringern} 
        {increments appropriate counter} 
        if  XIntersection < P.X  then  Inc(ToTheLeftofPoint);
        if  XIntersection > P.X  then  Inc(ToTheRightofPoint);
      end ;

    {Falls das Polygon offen ist, die letzte Seite testen} 
    {if the polygon is open, test for the last side} 

    if  OpenPolygon  then 
    begin 
     np := High(TestPolygon);   {Thanks to William Boyd - 03/06/2001} 
      if  ((TestPolygon[np].Y <= P.Y)  and 
       (TestPolygon[ 0 ].Y > P.Y))  or 
       ((TestPolygon[np].Y > P.Y)  and 
       (TestPolygon[ 0 ].Y <= P.Y))  then 
      begin 
       XIntersection := TestPolygon[np].X +
         ((TestPolygon[ 0 ].X - TestPolygon[np].X) /
         (TestPolygon[ 0 ].Y - TestPolygon[np].Y)) * (P.Y - TestPolygon[np].Y);

        if  XIntersection < P.X  then  Inc(ToTheLeftofPoint);
        if  XIntersection > P.X  then  Inc(ToTheRightofPoint);
      end ;
    end ;

    if  (ToTheLeftofPoint  mod   2  =  1 )  and  (ToTheRightofPoint  mod   2  =  1 )  then  Result := True
    else 
     Result := False;
  end ;  {PtInRgn} 

...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35790159
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
КартежникВот еще нашел кое что с Дельфи ворлд


Ого!!!! А чё это столько кода много? это же тот же самый алгоритм насколько я понял ...
Хотя я уже заметил лишнее ))) Например то, что они сверяют количество пересечений с обеих сторон, а это лишнее ))) достаточно только с одной стороны...
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35790165
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нашел программу где это задача реализована(это ГИС одного города), и вроде все правильно работает и главное быстро. Мне кажется они используют цвет прямоугольника. Но вряд ли они со мной поделятся алгоритмом.
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35791418
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Остановись на этом (с предыдущей страницы):

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
int pnpoly(int npol, float * xp, float * yp, float x, float y)
 {
   int c =  0 ;
   for (int i =  0 , j = npol -  1 ; i < npol; j = i++) 
   {
     if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) &&
       (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
         c = !c;
   }
   return c;
 }

Он и для невыпуклых тоже.
Если точка на границе - результат не определен. Так и должно быть, она же и не снаружи и не внутри. Если нужна принадлежность границе, то это проверяй отдельно.
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35791454
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
pirovindosОстановись на этом (с предыдущей страницы):

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
int pnpoly(int npol, float * xp, float * yp, float x, float y)
 {
   int c =  0 ;
   for (int i =  0 , j = npol -  1 ; i < npol; j = i++) 
   {
     if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) &&
       (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
         c = !c;
   }
   return c;
 }

Он и для невыпуклых тоже.
Если точка на границе - результат не определен. Так и должно быть, она же и не снаружи и не внутри. Если нужна принадлежность границе, то это проверяй отдельно.
Принято считать, что граница - это всё же ещё многоугольник ))) (Хотя тут зависит от задачи автора ). В данном случае результат на границах делиться пополам )) Ну то есть принадлежность границе ограничивающей многоугольник справа даст положительный результат, слева - отрицательный :)
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35791628
Evgeniy_SH
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
http://algolist.manual.ru/maths/geom/belong/poly2d.php - вот оно
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35791673
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ПрограмёрПринято считать, что граница - это всё же ещё многоугольник ))) (Хотя тут зависит от задачи автора ). В данном случае результат на границах делиться пополам )) Ну то есть принадлежность границе ограничивающей многоугольник справа даст положительный результат, слева - отрицательный :)
Я-бы сделал так. Левая верхняя и верхняя граница многоугольника - считается входящей в него. Правая и нижняя - не принадлежит. Мои рассуждения легко проверить, если представить множество плотно расположенных прямоугольников. Это более честно (ИМХО).
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35791817
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПрограмёрПринято считать, что граница - это всё же ещё многоугольник ))) (Хотя тут зависит от задачи автора ). В данном случае результат на границах делиться пополам )) Ну то есть принадлежность границе ограничивающей многоугольник справа даст положительный результат, слева - отрицательный :)
Я-бы сделал так. Левая верхняя и верхняя граница многоугольника - считается входящей в него. Правая и нижняя - не принадлежит. Мои рассуждения легко проверить, если представить множество плотно расположенных прямоугольников. Это более честно (ИМХО).
Включать или не включать границу и какую ее часть - полностью зависит от прикладной задачи. Данная функция никакой полезной информации о принадлежности границе не дает. Нужно считать отдельно.
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35791937
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
pirovindos
Включать или не включать границу и какую ее часть - полностью зависит от прикладной задачи. Данная функция никакой полезной информации о принадлежности границе не дает. Нужно считать отдельно.

Нет ))) Она даёт... и я уже описал какую (насколько я понял тот код)... И единственный недостаток алгоритма - это недочёт при прохождении луча через одну из вершин многоугольника и случай, когда одна из сторон принадлежит данному лучу (ну то есть, если она паралельна оси х и находится на уровне точки по оси у ... тогда луч пройдёт ровно по данной линии, что может дать очень непредсказуемый результат)
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35792102
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну для меня расположение точки на границе не имеет большого значения(что там один пиксель). Осталось только решить проблему прохождения луча через вершину и когда одна из сторон принадлежит лучу
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35792273
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Этот алгоритм корректно работает в случае, если интересующая точка имеет координату "у", совпадающую с координатами "у" одной или нескольких вершин.
Поскольку данный алгоритм никаких "лучей" не рассматирвает, то "прохождение луча" через вершину или даже через сторону многоугольника не влияет на правильность ответа.
...
Рейтинг: 0 / 0
Как определить принадлежит ли точка прямоугольнику
    #35792298
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Спасибо всем, много полезного узнал. Но задача усложнилась. Дальше буду думать сам
...
Рейтинг: 0 / 0
25 сообщений из 108, страница 3 из 5
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как определить принадлежит ли точка прямоугольнику
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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