|
|
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
КартежникmaytonЭто как "по цвету" ? Ну я думал закрашивать фигуры(тока еще не придумал как), и каждой присваивать свой цвет, они могут повторятся но не должны совпадать с фоном за фигурой. Найти максимально удаленные точки фигуры. Если заданная точка находится в этом получившемся прямоугольнике, то остается проверить ее цвет Не максимально удаленные точки, а искать по координатам минимальный x и y, максимальный x и y. Потом получится прямоугольник ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2009, 21:04:52 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
Плохой метод. Ты отказываешься от математически строгого алгоритма в пользу численного метода, который к тому-же потребует дополнительную память. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2009, 21:11:15 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
maytonПлохой метод. Ты отказываешься от математически строгого алгоритма в пользу численного метода, который к тому-же потребует дополнительную память. Это же на время. Чтоб другие функции программы сделать. А функцию inpoly(в многоугольнике) могу в любой момент переделать. Как только алгоритм оптимизирую и доведу до ума. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2009, 21:14:23 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
Лентяй ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2009, 21:22:30 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
maytonЛентяй Что есть то есть. Просто не думал что застряну на этом ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2009, 21:23:30 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
1) x1:=x*cosang+y*sinang; y1:=x*sinang-y*cosang; это формула нахождения координат точки при провороте системы координат вокруг своей оси. Если взять одну точку прямоугольника как начало координат, а одну из сторон, выходящих с этой точки, как базис, то можно высчитать синус и косинус угла, на который надо провернуть систему координат, что бы стороны прямоугольника совпали с осями координат. тогда по выше приведённой формуле можно будет найти новые координаты всех точек. Тогда всё сводится к простому сравнению (так как теперь стороны прямоугольника перпендикулярны осям координат), или же к умножению (так как перпендикуляры проведённые параллельно к осям координат разобьют прямоугольник на 4 меньших прямоугольника, сумма площадей которых равна площади данного. Если точка лежит вне этого прямоугольника, то и площадь образованых прямоугольников будет больше, площади данного). P.S. Данное сообщение просто немного глубже описывает (и немного изменяет) раннее данный mayton'ом ответ. Годиться только для прямоугольника :) 2) Если же отбрасывать луч с точки влево (по-моему самый оптимальный и действенный алгоритм), то тут я не могу понять, почему maytonДа. Этот метод годится только для выпуклых. Вогнутые надо будет разбивать на объединение нескольких выпуклых или делать сложные проверки с "исключением" впуклой области, если есть возможность. В качестве примера - проверка попадания точки в "бублик" аппроксимированный многоугольником. Нарисуйте пожалуйста кто-нибуть фигуру, к котрой данный метод будет неприменим... )) (просто к сожалению я не понял что это за фигура: "бублик" аппроксимированный многоугольником :) ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2009, 18:19:35 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
Програмёр (просто к сожалению я не понял что это за фигура: "бублик" аппроксимированный многоугольником :) )представь себе кольцо ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2009, 23:23:52 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
egorychПрограмёр (просто к сожалению я не понял что это за фигура: "бублик" аппроксимированный многоугольником :) )представь себе кольцо Представил... Но кольцо полностью подходит под этот алгоритм... ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2009, 23:41:26 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
кольцо - всегда особый случай. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2009, 00:06:42 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
egorychкольцо - всегда особый случай. Согласен ))) Но во-первых, в данном случае мы не можем говорить про идеальное кольцо (так, как наше кольцо будет многоугольником с очень большим количеством граней). А во-вторых, даже если мы и будем иметь идеальное кольцо (хотя с "во-первых" следует, что не будем), то отброшенный влево из точки луч пересечёт: 1 грань - если точка будет внутри кольца, 0 или 2 грани - если она будет за пределами кольца ))) тут всё просто... ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2009, 00:38:29 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
Единственное, что могу ещё добавить, так это то, что в данном алгоритме есть несколько исключений, и так как я не очень понимаю тот код, что привели на форуме ранее, то перечислю все исключения которые вижу (в случае, если их не учли, считаю что лучше бы это сделать): 1. Когда точка принадлежит одной из граней многоугольника (получим пересечение двух граней, но точка будет лежать в пределах многоугольника) 2. Если одна или больше граней многоугольника принадлежат лучу, отброшенному с точки (ну то есть иными словами они совпадают с лучём, тогда и луч будет проходить через 2 или более точек). 3. Когда данная точка совпадает с одной из вершин многоугольника. Хм... вроде всё... придумаю ещё какое-то исключение - напишу ;) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2009, 00:53:56 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
наш волшебный луч может попасть в вершину, мы же говорим о многоугольниках. этот момент придётся проверить. ЗЫ математически всё верно, но: нам таки потребуется как-то посчитать угол, на который мы поворачиваем систему координат. ЗЫЫ проблемы округления встанут перед нами во всей красе при таком способе. компьютер плохо справляется с вычислениями вещественных чисел ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2009, 00:54:33 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
egorychнаш волшебный луч может попасть в вершину, мы же говорим о многоугольниках. этот момент придётся проверить. ЗЫ математически всё верно, но: нам таки потребуется как-то посчитать угол, на который мы поворачиваем систему координат. ЗЫЫ проблемы округления встанут перед нами во всей красе при таком способе. компьютер плохо справляется с вычислениями вещественных чисел там, где с лучём - ничего не поворачивается... Если же это идёт обсуждение описанного мной метода, то да... там есть поворот, но угол поворота высчитывать не надо, так как нам нужны только косинус и синус этого угла (а их можно найти по координатам точек, ограничивающих выбранную как базис грань (ну типа х/длина = синус, а у/длина = косинус) ). Да и вообще я ведь признался, что приведённый мной метод довольно отстойный ))) Так что лучше юзать алгоритм с лучём ;) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2009, 02:03:11 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
Вот еще нашел кое что с Дельфи ворлд Код: 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. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2009, 09:15:07 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
КартежникВот еще нашел кое что с Дельфи ворлд Ого!!!! А чё это столько кода много? это же тот же самый алгоритм насколько я понял ... Хотя я уже заметил лишнее ))) Например то, что они сверяют количество пересечений с обеих сторон, а это лишнее ))) достаточно только с одной стороны... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2009, 13:00:52 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
Нашел программу где это задача реализована(это ГИС одного города), и вроде все правильно работает и главное быстро. Мне кажется они используют цвет прямоугольника. Но вряд ли они со мной поделятся алгоритмом. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2009, 13:09:24 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
Остановись на этом (с предыдущей страницы): Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Он и для невыпуклых тоже. Если точка на границе - результат не определен. Так и должно быть, она же и не снаружи и не внутри. Если нужна принадлежность границе, то это проверяй отдельно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.02.2009, 13:11:16 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
pirovindosОстановись на этом (с предыдущей страницы): Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Он и для невыпуклых тоже. Если точка на границе - результат не определен. Так и должно быть, она же и не снаружи и не внутри. Если нужна принадлежность границе, то это проверяй отдельно. Принято считать, что граница - это всё же ещё многоугольник ))) (Хотя тут зависит от задачи автора ). В данном случае результат на границах делиться пополам )) Ну то есть принадлежность границе ограничивающей многоугольник справа даст положительный результат, слева - отрицательный :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.02.2009, 13:19:02 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
http://algolist.manual.ru/maths/geom/belong/poly2d.php - вот оно ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.02.2009, 14:11:15 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
ПрограмёрПринято считать, что граница - это всё же ещё многоугольник ))) (Хотя тут зависит от задачи автора ). В данном случае результат на границах делиться пополам )) Ну то есть принадлежность границе ограничивающей многоугольник справа даст положительный результат, слева - отрицательный :) Я-бы сделал так. Левая верхняя и верхняя граница многоугольника - считается входящей в него. Правая и нижняя - не принадлежит. Мои рассуждения легко проверить, если представить множество плотно расположенных прямоугольников. Это более честно (ИМХО). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.02.2009, 14:27:41 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
maytonПрограмёрПринято считать, что граница - это всё же ещё многоугольник ))) (Хотя тут зависит от задачи автора ). В данном случае результат на границах делиться пополам )) Ну то есть принадлежность границе ограничивающей многоугольник справа даст положительный результат, слева - отрицательный :) Я-бы сделал так. Левая верхняя и верхняя граница многоугольника - считается входящей в него. Правая и нижняя - не принадлежит. Мои рассуждения легко проверить, если представить множество плотно расположенных прямоугольников. Это более честно (ИМХО). Включать или не включать границу и какую ее часть - полностью зависит от прикладной задачи. Данная функция никакой полезной информации о принадлежности границе не дает. Нужно считать отдельно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.02.2009, 15:30:26 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
pirovindos Включать или не включать границу и какую ее часть - полностью зависит от прикладной задачи. Данная функция никакой полезной информации о принадлежности границе не дает. Нужно считать отдельно. Нет ))) Она даёт... и я уже описал какую (насколько я понял тот код)... И единственный недостаток алгоритма - это недочёт при прохождении луча через одну из вершин многоугольника и случай, когда одна из сторон принадлежит данному лучу (ну то есть, если она паралельна оси х и находится на уровне точки по оси у ... тогда луч пройдёт ровно по данной линии, что может дать очень непредсказуемый результат) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.02.2009, 16:23:19 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
Ну для меня расположение точки на границе не имеет большого значения(что там один пиксель). Осталось только решить проблему прохождения луча через вершину и когда одна из сторон принадлежит лучу ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.02.2009, 17:14:19 |
|
||
|
Как определить принадлежит ли точка прямоугольнику
|
|||
|---|---|---|---|
|
#18+
Этот алгоритм корректно работает в случае, если интересующая точка имеет координату "у", совпадающую с координатами "у" одной или нескольких вершин. Поскольку данный алгоритм никаких "лучей" не рассматирвает, то "прохождение луча" через вершину или даже через сторону многоугольника не влияет на правильность ответа. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.02.2009, 18:13:22 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=35790159&tid=1344672]: |
0ms |
get settings: |
7ms |
get forum list: |
13ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
30ms |
get topic data: |
8ms |
get forum data: |
4ms |
get page messages: |
51ms |
get tp. blocked users: |
1ms |
| others: | 233ms |
| total: | 351ms |

| 0 / 0 |
