ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как определить принадлежит ли точка прямоугольнику
108 сообщений из 108, показаны все 5 страниц
  все  
Как определить принадлежит ли точка прямоугольнику
    #35785960
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Может формула есть какая? Или ссылки на статьи.
...
Рейтинг: 0 / 0
29.01.2009, 16:06:26
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786021
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
а нарисовать на бумажке прямоугольник, оси координат и точку слабо?
...
Рейтинг: 0 / 0
29.01.2009, 16:20:47
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786024
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
egorychа нарисовать на бумажке прямоугольник, оси координат и точку слабо?
Здесь я могу добавить кому слабо, можете не отвечать
...
Рейтинг: 0 / 0
29.01.2009, 16:22:26
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786137
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Это не так легко как тебе кажется
...
Рейтинг: 0 / 0
29.01.2009, 16:45:41
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786161
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
ну если и прямоугольник и точка находятся в N-мерном пространстве, то, да, это чуток сложнее рисования на бумажке
...
Рейтинг: 0 / 0
29.01.2009, 16:51:16
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786185
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Прямоугольник и точка находятся в N мерном пространстве, где N=2. Тут возникают проблемы когда стороны прямоугольника не параллельны(и не перпендикулярны) не одной оси(X и Y)
...
Рейтинг: 0 / 0
29.01.2009, 16:56:39
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786273
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
КартежникПрямоугольник и точка находятся в N мерном пространстве, где N=2. Тут возникают проблемы когда стороны прямоугольника не параллельны(и не перпендикулярны) не одной оси(X и Y)
Берёшь одну из сторон прямоугольника за базис. Разворачиваешь прямоугольник относительно нуля координат так, чтобы базис был перпендикулярен оси ОХ (например). Для разворота используешь матрицу линейных преобразований. По этой-же матрице развернёшь точку. В новой системе координат решаешь тривиальную задачу типа x1<x<x2 и y1<y<y2.
...
Рейтинг: 0 / 0
29.01.2009, 17:25:31
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786279
zloy den
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zloy den
Участник
Представьте что прямоугольник-некая замкнутая область, состоящая из 4-х прямых. Тогда вам надо будет лишь определиться-находится ли точка в нужной для каждой прямой полуплоскости(все они направлены внутрь прямоугольника) или нет. Если хоть для одной из сторон условие не сработало, то точка находится снаружи. На листке бумаги было бы намного понятнее
P.S. чего-то вспомнились методы оптимизации
...
Рейтинг: 0 / 0
29.01.2009, 17:27:50
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786280
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
maytonКартежникПрямоугольник и точка находятся в N мерном пространстве, где N=2. Тут возникают проблемы когда стороны прямоугольника не параллельны(и не перпендикулярны) не одной оси(X и Y)
Берёшь одну из сторон прямоугольника за базис. Разворачиваешь прямоугольник относительно нуля координат так, чтобы базис был перпендикулярен оси ОХ (например). Для разворота используешь матрицу линейных преобразований. По этой-же матрице развернёшь точку. В новой системе координат решаешь тривиальную задачу типа x1<x<x2 и y1<y<y2.

Все понятно.Спасибо
...
Рейтинг: 0 / 0
29.01.2009, 17:27:53
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786285
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
zloy denПредставьте что прямоугольник-некая замкнутая область, состоящая из 4-х прямых. Тогда вам надо будет лишь определиться-находится ли точка в нужной для каждой прямой полуплоскости(все они направлены внутрь прямоугольника) или нет. Если хоть для одной из сторон условие не сработало, то точка находится снаружи. На листке бумаги было бы намного понятнее
P.S. чего-то вспомнились методы оптимизации
А как определить этот "внутрь"
...
Рейтинг: 0 / 0
29.01.2009, 17:31:27
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786312
zloy den
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zloy den
Участник
Надо выбрать ту полуплоскость, в которой лежит противоположная сторона. Каждую сторону стоит изобразить в виде уравнения прямой, тогда коэффициент наклона у противоположных сторон будет одинаков, различаться они будут только сдвигом относительно оси х
...
Рейтинг: 0 / 0
29.01.2009, 17:40:04
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786321
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
zloy denНадо выбрать ту полуплоскость, в которой лежит противоположная сторона. Каждую сторону стоит изобразить в виде уравнения прямой, тогда коэффициент наклона у противоположных сторон будет одинаков, различаться они будут только сдвигом относительно оси х
А ну теперь понятно, можно даже и для разных многоугольников использовать
...
Рейтинг: 0 / 0
29.01.2009, 17:43:16
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786327
zloy den
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zloy den
Участник
Картежник
А ну теперь понятно, можно даже и для разных многоугольников использовать

Ага. Именно потому и вспомнились оптимизационные задачи
...
Рейтинг: 0 / 0
29.01.2009, 17:44:52
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786332
zloy den
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zloy den
Участник
Дополнение: для выпуклых многоугольников
...
Рейтинг: 0 / 0
29.01.2009, 17:45:46
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786337
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Все ОК
...
Рейтинг: 0 / 0
29.01.2009, 17:46:32
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786364
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
zloy denДополнение: для выпуклых многоугольников
Еще дополнение: Для невывернутых наизнантку прямоугольников.
...
Рейтинг: 0 / 0
29.01.2009, 17:54:20
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786370
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirovindos
Участник
Есть еще пара способов, работают и для невыпуклых. Если ТС не хватило сказанного, то поделюсь.
...
Рейтинг: 0 / 0
29.01.2009, 17:55:52
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786372
zloy den
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zloy den
Участник
mayton
Еще дополнение: Для невывернутых наизнантку прямоугольников.

Ы?
...
Рейтинг: 0 / 0
29.01.2009, 17:56:00
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786374
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
pirovindosЕсть еще пара способов, работают и для невыпуклых. Если ТС не хватило сказанного, то поделюсь.
Для невыпуклых тоже пригодятся
...
Рейтинг: 0 / 0
29.01.2009, 17:57:19
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786465
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirovindos
Участник
1. "Посчитать вычет". Посчитать на какой угол повернется вектор направленный с началом в нужной точке и концом в вершине многоугольника, при обходе концом вектора ВСЕХ+1 вершин многоугольника по порядку от первой и до первой. Если на 0 градусов - то вне, если на 360, то внутри.
2. Почитать количество пересечений со сторонами многоугольника любого луча из нужной точки . Если четное, то вне, если нечетное - то внутри. Осторожно: есть тонкости при попадании луча точно в вершину.
...
Рейтинг: 0 / 0
29.01.2009, 18:38:22
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786471
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Еще тут кое что надумал. с заданой точки на 4 стороны отправить лучи. Каждый луч должен пересекать нечетное кол-во прямых заданного многоугольника.
...
Рейтинг: 0 / 0
29.01.2009, 18:41:13
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786479
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
pirovindos
2. Почитать количество пересечений со сторонами многоугольника любого луча из нужной точки . Если четное, то вне, если нечетное - то внутри. Осторожно: есть тонкости при попадании луча точно в вершину.
Ух ты повторил твою идею
...
Рейтинг: 0 / 0
29.01.2009, 18:44:08
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786480
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirovindos
Участник
А зачем в 4 стороны?
Прямая многоугольника - это что?
...
Рейтинг: 0 / 0
29.01.2009, 18:44:15
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786483
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
pirovindosА зачем в 4 стороны?
Прямая многоугольника - это что?
В 4 стороны: допустим паралелные осям.
Прямая многоугольника(A,B,C,D,E- углы) - это AB,BC,CD,DE,EA
...
Рейтинг: 0 / 0
29.01.2009, 18:46:45
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786486
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Я же говорю повторил твою идею
...
Рейтинг: 0 / 0
29.01.2009, 18:47:53
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786489
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirovindos
Участник
1. В одну хватит.
2. Ясно - не прямая, а отрезок границы. Под "прямой" обычно имеют в виду - бесконечную прямую, в отличие от отрезка.
...
Рейтинг: 0 / 0
29.01.2009, 18:48:27
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786492
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
А понятно буду иметь ввиду
...
Рейтинг: 0 / 0
29.01.2009, 18:50:08
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786494
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
pirovindos1. В одну хватит.
2. Ясно - не прямая, а отрезок границы. Под "прямой" обычно имеют в виду - бесконечную прямую, в отличие от отрезка.
Точно, ноль же тоже четное
...
Рейтинг: 0 / 0
29.01.2009, 18:51:36
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786515
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
pirovindos Осторожно: есть тонкости при попадании луча точно в вершину.
При попадании в вершину, придется использовать 4 луча
...
Рейтинг: 0 / 0
29.01.2009, 19:06:40
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786535
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
pirovindos1. "Посчитать вычет". Посчитать на какой угол повернется вектор направленный с началом в нужной точке и концом в вершине многоугольника, при обходе концом вектора ВСЕХ+1 вершин многоугольника по порядку от первой и до первой. Если на 0 градусов - то вне, если на 360, то внутри.

В этом случае не подойдет кажется
...
Рейтинг: 0 / 0
29.01.2009, 19:26:46
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786539
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirovindos
Участник
Могут все 4 в вершины попасть. Так что лучше аккуратно разобраться при попадании в вершину.

Или придется считать все направления на вершины и пускать луч мимо всех - но тогда половина работы по первому способу сделана :).
...
Рейтинг: 0 / 0
29.01.2009, 19:30:29
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786541
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirovindos
Участник
Картежникpirovindos1. "Посчитать вычет". Посчитать на какой угол повернется вектор направленный с началом в нужной точке и концом в вершине многоугольника, при обходе концом вектора ВСЕХ+1 вершин многоугольника по порядку от первой и до первой. Если на 0 градусов - то вне, если на 360, то внутри.

В этом случае не подойдет кажется

Подойдет. Даже если улитку нарисуешь, тоже подойдет.
...
Рейтинг: 0 / 0
29.01.2009, 19:32:10
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786542
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Вот именно при попадании всех четырех означает что внутри
...
Рейтинг: 0 / 0
29.01.2009, 19:32:29
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786544
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
КартежникВот именно при попадании всех четырех означает что внутри
Хотя нет ошибся
...
Рейтинг: 0 / 0
29.01.2009, 19:33:04
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35786558
nik_x
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nik_x
Участник
Так прямоугольник, или многоугольник?

Проверка принадлежности точки многоугольнику: http://algolist.manual.ru/maths/geom/belong/poly2d.php
...
Рейтинг: 0 / 0
29.01.2009, 19:53:35
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35787106
Фотография Worobjoff
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Worobjoff
Участник
Код: plaintext
1.
2.
Dim rc as New Rectangle( 0 , 0 , 100 , 100 )
Dim p as new Point( 55 , 44 )
Console.WriteLine( rc.Contains(p) )
...
Рейтинг: 0 / 0
30.01.2009, 09:30:28
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35787107
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Worobjoff
Код: plaintext
Dim rc as New Rectangle( 0 , 0 , 100 , 100 )
а наклон как задавать?
...
Рейтинг: 0 / 0
30.01.2009, 09:31:46
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35787264
Фотография Worobjoff
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Worobjoff
Участник
упс.... показалось что на сайте VB.NET отвечаю...

miksoftWorobjoff
Код: plaintext
Dim rc as New Rectangle( 0 , 0 , 100 , 100 )
а наклон как задавать?Если это CS, то и для сложных фигур там есть функция определения принадлежности точки.
...
Рейтинг: 0 / 0
30.01.2009, 10:27:11
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35787847
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Картежникpirovindos1. "Посчитать вычет". Посчитать на какой угол повернется вектор направленный с началом в нужной точке и концом в вершине многоугольника, при обходе концом вектора ВСЕХ+1 вершин многоугольника по порядку от первой и до первой. Если на 0 градусов - то вне, если на 360, то внутри.

В этом случае не подойдет кажется
Еще был неплохой алгоритм (не помню названия), основанный на четности пересечений границ многоугольника горизонтальной прямой. Случаи перечечения вершин надо рассматривать отдельно.
...
Рейтинг: 0 / 0
30.01.2009, 12:50:33
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35788176
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Вот самый подходящий к моей задаче:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
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
30.01.2009, 14:24:56
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35788228
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
правда как он это делает так и не врубился
...
Рейтинг: 0 / 0
30.01.2009, 14:37:26
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35788253
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я догадываюсь. Но что-бы быть уверенным, лучше уточнить что означают векторы float * xp, float * yp, float x, float y.
...
Рейтинг: 0 / 0
30.01.2009, 14:43:22
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35788278
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
maytonЯ догадываюсь. Но что-бы быть уверенным, лучше уточнить что означают векторы float * xp, float * yp, float x, float y.
xp - координаты x-ов(1.. npol)
yp - координаты y-ов(1.. npol)
(xp[1],yp[1]) - точка первого угла многоугольника и т.д.
(x,y) - заданная точка
...
Рейтинг: 0 / 0
30.01.2009, 14:48:28
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35788284
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
КартежникmaytonЯ догадываюсь. Но что-бы быть уверенным, лучше уточнить что означают векторы float * xp, float * yp, float x, float y.
xp - координаты x-ов(1.. npol)
yp - координаты y-ов(1.. npol)
(xp[1],yp[1]) - точка первого угла многоугольника и т.д.
(x,y) - заданная точка
Ошибка
xp - координаты x-ов(0.. npol-1)
yp - координаты y-ов(0.. npol-1)
...
Рейтинг: 0 / 0
30.01.2009, 14:50:28
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35788748
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirovindos
Участник
Картежникправда как он это делает так и не врубился
Перебирает все отрезки границы, которые пересекает прямая параллельная оси х, и вычисляет в какой полуплоскости (справа или слева от отрезка) находится интересующая точка. А потом берет четность всех случаев, когда "слева". Если нечетное, то внутри, если четное, то снаружи.
...
Рейтинг: 0 / 0
30.01.2009, 17:33:17
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35788760
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Вроде пока работает, если что придется применять метод по цвету точки и многоугольника.
...
Рейтинг: 0 / 0
30.01.2009, 17:38:35
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35789033
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да. Этот метод годится только для выпуклых. Вогнутые надо будет разбивать на объединение нескольких выпуклых или делать сложные проверки с "исключением" впуклой области, если есть возможность. В качестве примера - проверка попадания точки в "бублик" аппроксимированный многоугольником.
...
Рейтинг: 0 / 0
30.01.2009, 20:49:59
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35789034
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
maytonДа. Этот метод годится только для выпуклых. Вогнутые надо будет разбивать на объединение нескольких выпуклых или делать сложные проверки с "исключением" впуклой области, если есть возможность. В качестве примера - проверка попадания точки в "бублик" аппроксимированный многоугольником.
Тогда с чего начинал, к тому и приду. По цвету определять.
...
Рейтинг: 0 / 0
30.01.2009, 20:52:47
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35789038
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Это как "по цвету" ?
...
Рейтинг: 0 / 0
30.01.2009, 20:55:40
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35789042
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
maytonЭто как "по цвету" ?
Ну я думал закрашивать фигуры(тока еще не придумал как), и каждой присваивать свой цвет, они могут повторятся но не должны совпадать с фоном за фигурой. Найти максимально удаленные точки фигуры. Если заданная точка находится в этом получившемся прямоугольнике, то остается проверить ее цвет
...
Рейтинг: 0 / 0
30.01.2009, 20:59:16
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35789047
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
КартежникmaytonЭто как "по цвету" ?
Ну я думал закрашивать фигуры(тока еще не придумал как), и каждой присваивать свой цвет, они могут повторятся но не должны совпадать с фоном за фигурой. Найти максимально удаленные точки фигуры. Если заданная точка находится в этом получившемся прямоугольнике, то остается проверить ее цвет
Не максимально удаленные точки, а искать по координатам минимальный x и y, максимальный x и y.
Потом получится прямоугольник
...
Рейтинг: 0 / 0
30.01.2009, 21:04:52
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35789056
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Плохой метод. Ты отказываешься от математически строгого алгоритма в пользу численного метода, который к тому-же потребует дополнительную память.
...
Рейтинг: 0 / 0
30.01.2009, 21:11:15
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35789060
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
maytonПлохой метод. Ты отказываешься от математически строгого алгоритма в пользу численного метода, который к тому-же потребует дополнительную память.
Это же на время. Чтоб другие функции программы сделать. А функцию inpoly(в многоугольнике) могу в любой момент переделать. Как только алгоритм оптимизирую и доведу до ума.
...
Рейтинг: 0 / 0
30.01.2009, 21:14:23
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35789068
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Лентяй
...
Рейтинг: 0 / 0
30.01.2009, 21:22:30
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35789072
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
maytonЛентяй
Что есть то есть. Просто не думал что застряну на этом
...
Рейтинг: 0 / 0
30.01.2009, 21:23:30
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35789728
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
1)
x1:=x*cosang+y*sinang; y1:=x*sinang-y*cosang;

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

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

Представил... Но кольцо полностью подходит под этот алгоритм... )))
...
Рейтинг: 0 / 0
31.01.2009, 23:41:26
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35789945
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
кольцо - всегда особый случай.
...
Рейтинг: 0 / 0
01.02.2009, 00:06:42
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35789957
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
egorychкольцо - всегда особый случай.

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

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

Да и вообще я ведь признался, что приведённый мной метод довольно отстойный ))) Так что лучше юзать алгоритм с лучём ;)
...
Рейтинг: 0 / 0
01.02.2009, 02:03:11
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #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
01.02.2009, 09:15:07
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35790159
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
КартежникВот еще нашел кое что с Дельфи ворлд


Ого!!!! А чё это столько кода много? это же тот же самый алгоритм насколько я понял ...
Хотя я уже заметил лишнее ))) Например то, что они сверяют количество пересечений с обеих сторон, а это лишнее ))) достаточно только с одной стороны...
...
Рейтинг: 0 / 0
01.02.2009, 13:00:52
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35790165
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Нашел программу где это задача реализована(это ГИС одного города), и вроде все правильно работает и главное быстро. Мне кажется они используют цвет прямоугольника. Но вряд ли они со мной поделятся алгоритмом.
...
Рейтинг: 0 / 0
01.02.2009, 13:09:24
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35791418
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
02.02.2009, 13:11:16
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #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
02.02.2009, 13:19:02
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35791628
Evgeniy_SH
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Evgeniy_SH
Участник
http://algolist.manual.ru/maths/geom/belong/poly2d.php - вот оно
...
Рейтинг: 0 / 0
02.02.2009, 14:11:15
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35791673
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ПрограмёрПринято считать, что граница - это всё же ещё многоугольник ))) (Хотя тут зависит от задачи автора ). В данном случае результат на границах делиться пополам )) Ну то есть принадлежность границе ограничивающей многоугольник справа даст положительный результат, слева - отрицательный :)
Я-бы сделал так. Левая верхняя и верхняя граница многоугольника - считается входящей в него. Правая и нижняя - не принадлежит. Мои рассуждения легко проверить, если представить множество плотно расположенных прямоугольников. Это более честно (ИМХО).
...
Рейтинг: 0 / 0
02.02.2009, 14:27:41
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35791817
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirovindos
Участник
maytonПрограмёрПринято считать, что граница - это всё же ещё многоугольник ))) (Хотя тут зависит от задачи автора ). В данном случае результат на границах делиться пополам )) Ну то есть принадлежность границе ограничивающей многоугольник справа даст положительный результат, слева - отрицательный :)
Я-бы сделал так. Левая верхняя и верхняя граница многоугольника - считается входящей в него. Правая и нижняя - не принадлежит. Мои рассуждения легко проверить, если представить множество плотно расположенных прямоугольников. Это более честно (ИМХО).
Включать или не включать границу и какую ее часть - полностью зависит от прикладной задачи. Данная функция никакой полезной информации о принадлежности границе не дает. Нужно считать отдельно.
...
Рейтинг: 0 / 0
02.02.2009, 15:30:26
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35791937
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
pirovindos
Включать или не включать границу и какую ее часть - полностью зависит от прикладной задачи. Данная функция никакой полезной информации о принадлежности границе не дает. Нужно считать отдельно.

Нет ))) Она даёт... и я уже описал какую (насколько я понял тот код)... И единственный недостаток алгоритма - это недочёт при прохождении луча через одну из вершин многоугольника и случай, когда одна из сторон принадлежит данному лучу (ну то есть, если она паралельна оси х и находится на уровне точки по оси у ... тогда луч пройдёт ровно по данной линии, что может дать очень непредсказуемый результат)
...
Рейтинг: 0 / 0
02.02.2009, 16:23:19
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35792102
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Ну для меня расположение точки на границе не имеет большого значения(что там один пиксель). Осталось только решить проблему прохождения луча через вершину и когда одна из сторон принадлежит лучу
...
Рейтинг: 0 / 0
02.02.2009, 17:14:19
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35792273
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirovindos
Участник
Этот алгоритм корректно работает в случае, если интересующая точка имеет координату "у", совпадающую с координатами "у" одной или нескольких вершин.
Поскольку данный алгоритм никаких "лучей" не рассматирвает, то "прохождение луча" через вершину или даже через сторону многоугольника не влияет на правильность ответа.
...
Рейтинг: 0 / 0
02.02.2009, 18:13:22
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35792298
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Спасибо всем, много полезного узнал. Но задача усложнилась. Дальше буду думать сам
...
Рейтинг: 0 / 0
02.02.2009, 18:24:39
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35792315
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
И чё усложнилось? Мы перенеслись в 3D ?
...
Рейтинг: 0 / 0
02.02.2009, 18:32:29
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35792318
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
maytonИ чё усложнилось? Мы перенеслись в 3D ?
нет, это так подобие 3d. Но все же...
...
Рейтинг: 0 / 0
02.02.2009, 18:33:54
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35792369
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirovindos
Участник
2 Картежник
Какова исходная задача? А то так и в 9D можно забраться.
...
Рейтинг: 0 / 0
02.02.2009, 19:15:34
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35792379
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
pirovindos2 Картежник
Какова исходная задача? А то так и в 9D можно забраться.
Нет до 9d не дойдет. Это последнее. Просто пока что с канвасом работаю. Потом хотел с GDI и Open Gl попробовать. Где быстрее будет работать, то и оставлю. А исходная задача мне кажется ясна. Это типа электронной карты с домами. В другом топике искал как данные получить, теперь как отобразить. Вообщем сам себе задачу ставлю. Чтоб без дела не сидеть.
...
Рейтинг: 0 / 0
02.02.2009, 19:22:26
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35792387
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Картежникpirovindos2 Картежник
Какова исходная задача? А то так и в 9D можно забраться.
Нет до 9d не дойдет. Это последнее. Просто пока что с канвасом работаю. Потом хотел с GDI и Open Gl попробовать. Где быстрее будет работать, то и оставлю. А исходная задача мне кажется ясна. Это типа электронной карты с домами. В другом топике искал как данные получить, теперь как отобразить. Вообщем сам себе задачу ставлю. Чтоб без дела не сидеть.

Кстати в нашем городе такой карты еще нет. Да и делать ее вроде некому. Так что вот думаю может сгодится кому нить.
...
Рейтинг: 0 / 0
02.02.2009, 19:27:53
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35800189
ResearchStudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ResearchStudio
Участник
1. Не знаю или поможет, но запомнился простой как топор метод Монтекарло.

Правда он используется для высчитывания обьема сложных фигур заданных какойто сложной формулой.

Допустим нужно посчитать обьем шестеренки с выпукло, впуклыми, волнистыми гранями по левую сторону барикад с крапинками и зубчиками.

1. Берем простую формулу большого куба который достаточных размеров чтобы вместить эту шестеренку.

2. Рандомам генерим в этот куб допустим 100 млн точек, и считаем сколько попало этих точек внутрь шестеренки.

3. Обьем у нас будет в пропорциях, допустим если 50 млн точек попало в шестеренку, то обьем шестеренки 1/2 обьема куба, если 70 млн точек то 7/10 обьема куба и тд.
...
Рейтинг: 0 / 0
05.02.2009, 19:01:19
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35800900
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вряд-ли автору это поможет.
...
Рейтинг: 0 / 0
06.02.2009, 09:39:46
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35801469
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
maytonВряд-ли автору это поможет.
Не то чтобы поможет, просто кажется это не то что мне надо
...
Рейтинг: 0 / 0
06.02.2009, 12:31:43
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803185
Random_Goodman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Random_Goodman
Участник
Если это псевдо-3д, то задача № 2 элементарно раскладывается в несколько задач №1.

Задача № 1 для лубого многоугольника решается Проведем через точку z горизонталь l (рис. 5).]алгоритмом из нескольких 10 строчек. Поиск по гуглу занял меньше минуты.
...
Рейтинг: 0 / 0
07.02.2009, 06:41:20
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803186
Random_Goodman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Random_Goodman
Участник
http://graphics.cs.msu.su/courses/cg_el99/notes/lect09.doc
...
Рейтинг: 0 / 0
07.02.2009, 06:41:46
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803439
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
Ну... по-моему разницы в 2д и 3д почти нету )) 2д отличается от 3д только тем, что двухмерные фигуры ограничиваются некими линиями (отрезками), а трёхмерные - плоскостями... Соответственно пускаем тот-же самый луч в любую сторону (но лучше по-моему это делать в сторону оси у, хотя особой разницы нету ) и считаем количество пересечённых ним плоскостей фигуры ))) По сути алгоритм почти идентичен, немного сложнее только его реализация :)
...
Рейтинг: 0 / 0
07.02.2009, 14:37:30
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803549
Random_Goodman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Random_Goodman
Участник
Не, слишком сложно будет

Я имел ввиду что у него это псевдо-3д, т. е. изображение трехмерной фигуры на двухмерной плоскости. Если же подлинно трехмерная, то задача сводится к проекции точки и фигуры на каждую из 3-х осей с дальнейшим решением первой задачи (только не надо в этом случае забывать о выраженности)
...
Рейтинг: 0 / 0
07.02.2009, 16:23:35
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803552
Random_Goodman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Random_Goodman
Участник
т. е. когда фигура пересекает какую-либо из осей или точка находится в минусовых координатах
...
Рейтинг: 0 / 0
07.02.2009, 16:25:40
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803558
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Random_GoodmanНе, слишком сложно будет

Я имел ввиду что у него это псевдо-3д, т. е. изображение трехмерной фигуры на двухмерной плоскости. Если же подлинно трехмерная, то задача сводится к проекции точки и фигуры на каждую из 3-х осей с дальнейшим решением первой задачи (только не надо в этом случае забывать о выраженности)
Ты прав. Третья ось не учитывается
...
Рейтинг: 0 / 0
07.02.2009, 16:27:50
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803560
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Random_GoodmanЕсли же подлинно трехмерная, то задача сводится к проекции точки и фигуры на каждую из 3-х осей с дальнейшим решением первой задачи (только не надо в этом случае забывать о выраженности)Нет, с проекциями будет неверно.
Контрпример: Шар и точка снаружи на расстоянии 1/100 радиуса шара от его поверхости в направлении от центра шара, сопадающим с направлением вектора (1,1,1). На всех трех проекциях точка будет внутри, но на самом деле она снаружи.
...
Рейтинг: 0 / 0
07.02.2009, 16:29:22
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803561
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
miksoftRandom_GoodmanЕсли же подлинно трехмерная, то задача сводится к проекции точки и фигуры на каждую из 3-х осей с дальнейшим решением первой задачи (только не надо в этом случае забывать о выраженности)Нет, с проекциями будет неверно.
Контрпример: Шар и точка снаружи на расстоянии 1/100 радиуса шара от его поверхости в направлении от центра шара, сопадающим с направлением вектора (1,1,1). На всех трех проекциях точка будет внутри, но на самом деле она снаружи.
Да ты тоже прав.
...
Рейтинг: 0 / 0
07.02.2009, 16:30:21
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803578
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
КартежникRandom_GoodmanНе, слишком сложно будет

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

Что-то я не совсем понял задачу ))) что значит третья ось не учитывается? Значит ли это, что наши точки всё же имеют только две координаты х и у, при том, что они описывают 3д фигуру? Если да, то тогда никакой алгоритм не поможет определить принадлежит ли точка фигуре или нет (это типа как решить систему уравнений с тремя неизвестными при наличии только двух уравнений) :) Этого даже человек не сможет сделать ))
...
Рейтинг: 0 / 0
07.02.2009, 16:45:21
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803582
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
ПрограмёрКартежникRandom_GoodmanНе, слишком сложно будет

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

Что-то я не совсем понял задачу ))) что значит третья ось не учитывается? Значит ли это, что наши точки всё же имеют только две координаты х и у, при том, что они описывают 3д фигуру? Если да, то тогда никакой алгоритм не поможет определить принадлежит ли точка фигуре или нет (это типа как решить систему уравнений с тремя неизвестными при наличии только двух уравнений) :) Этого даже человек не сможет сделать ))

Вот тут могу объяснить. Если поймешь. Третья ось - это та которая идет в глубину экрана. Ты же не можешь двигать мышь внутрь экрана или наружу. Вот она не учитывается. Главное чтоб курсор был надо объектом. А объект будет нарисован как я показывал на рисунке ранее
...
Рейтинг: 0 / 0
07.02.2009, 16:48:14
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803593
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
Картежник
Вот тут могу объяснить. Если поймешь. Третья ось - это та которая идет в глубину экрана. Ты же не можешь двигать мышь внутрь экрана или наружу. Вот она не учитывается. Главное чтоб курсор был надо объектом. А объект будет нарисован как я показывал на рисунке ранее

Тогда всё намного легче ))) Если есть две координаты, то просто высчитываем внешний контур фигуры и удаляем/игнорируем внутренний, после чего ранее обговариваемый алгоритм. Если же координаты три, то проецируем все линии на плоскость (2д) ну и читаем данное сообщение сначала :)

З.Ы. Насчёт движения курсора вглубь экрана могу тебя обрадовать ))) В мышке есть ролик, который можно в своей проге использовать для движения курсора вглубь экрана/карты (насколько я понял всё ради этого) и назад (хотя это немного бессмысленно, так как юзер будет замечать только уменьшение указателя курсора и небольшое смещение всторону, в случае если начало координат не является центром экрана :) )
...
Рейтинг: 0 / 0
07.02.2009, 17:07:08
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803601
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Програмёр
З.Ы. Насчёт движения курсора вглубь экрана могу тебя обрадовать ))) В мышке есть ролик, который можно в своей проге использовать для движения курсора вглубь экрана/карты (насколько я понял всё ради этого) и назад (хотя это немного бессмысленно, так как юзер будет замечать только уменьшение указателя курсора и небольшое смещение всторону, в случае если начало координат не является центром экрана :) )
Порадовал. Но тут,ИМХО, ты предлагаешь мне засунуть курсор внутрь Объекта. Ты прав это бессмысленно.
...
Рейтинг: 0 / 0
07.02.2009, 17:10:53
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803604
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
КартежникПрограмёр
З.Ы. Насчёт движения курсора вглубь экрана могу тебя обрадовать ))) В мышке есть ролик, который можно в своей проге использовать для движения курсора вглубь экрана/карты (насколько я понял всё ради этого) и назад (хотя это немного бессмысленно, так как юзер будет замечать только уменьшение указателя курсора и небольшое смещение всторону, в случае если начало координат не является центром экрана :) )
Порадовал. Но тут,ИМХО, ты предлагаешь мне засунуть курсор внутрь Объекта. Ты прав это бессмысленно.

это была шутка ))) Серьёзная была только первая часть сообщения ;)
...
Рейтинг: 0 / 0
07.02.2009, 17:16:38
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803606
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
ДА я понял. Я так и делаю.
...
Рейтинг: 0 / 0
07.02.2009, 17:17:29
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803631
Random_Goodman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Random_Goodman
Участник
Да, я был неправ с проекциями, как-то анал. геометрия подзабылась уже...

Так у вас все-таки прикладная задача? Уууу, как неинтересно. Если это серьезно - берите XNA или OpenGL и вперед. Там это все давно за вас решено.
...
Рейтинг: 0 / 0
07.02.2009, 17:52:19
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35803636
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
Random_GoodmanДа, я был неправ с проекциями, как-то анал. геометрия подзабылась уже...

Так у вас все-таки прикладная задача? Уууу, как неинтересно. Если это серьезно - берите XNA или OpenGL и вперед. Там это все давно за вас решено.
Честно говоря мне это тоже не особо интересно(пока что оставил все как есть, другими функциями занимаюсь). Просто необходимо сделать чтоб работало как можно быстрее.
...
Рейтинг: 0 / 0
07.02.2009, 17:57:38
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35804415
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Работать с иммитацией 3-д - это хорошая оптимизация задачи. Большинство стратегических игр (StarCraft, AOE) в своих алгоритмах оперируют с двумерным представлением локаций. А на экран игроку "подаётся" изометрия. Вроде-бы и 3-д, но в то-же время степеней свободы меньше.
...
Рейтинг: 0 / 0
08.02.2009, 18:03:29
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35806380
ResearchStudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ResearchStudio
Участник
К Сабжу,

Пускай многоугольник задан несколькими точками.
Провести от нашей точки к каждой точке многоугольника отрезок.
Получим Н-ое количество секторов. Если хотябы в одном секторе угол >180 градусов, точка не принадлежит многоугольнику
...
Рейтинг: 0 / 0
09.02.2009, 17:20:39
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35806745
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirovindos
Участник
Логично, но обратное неверно.
...
Рейтинг: 0 / 0
09.02.2009, 19:39:22
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35806753
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
В таком и подобных методах трудно определить угол. Как мне кажется в Дельфи триг.функции работают неправильно(или это касается чисел с плавающей точкой).
...
Рейтинг: 0 / 0
09.02.2009, 19:43:02
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35806861
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Используйте свойство знака векторного произведения и от углов можно будет избавится. По крайней мере мне это почти всегда удавалось.
...
Рейтинг: 0 / 0
09.02.2009, 20:50:39
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35806862
Фотография Картежник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Картежник
Участник
mayton,

Спасибо за полезный совет
...
Рейтинг: 0 / 0
09.02.2009, 20:52:09
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35807755
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirovindos
Участник
maytonИспользуйте свойство знака векторного произведения и от углов можно будет избавится. По крайней мере мне это почти всегда удавалось.
Так не отличить углы х и 180-х.
...
Рейтинг: 0 / 0
10.02.2009, 12:16:58
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35809346
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
ResearchStudioК Сабжу,

Пускай многоугольник задан несколькими точками.
Провести от нашей точки к каждой точке многоугольника отрезок.
Получим Н-ое количество секторов. Если хотябы в одном секторе угол >180 градусов, точка не принадлежит многоугольнику

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

Вот по-моему так ))) Потому могу предположить, что этот алгоритм является не самым лучшим для решения задачи (разве только если я что-то упустил, хотя это вряд ли).
...
Рейтинг: 0 / 0
10.02.2009, 22:12:04
| Ответить | Цитировать | Написать  
Как определить принадлежит ли точка прямоугольнику
    #35809378
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
pirovindosmaytonИспользуйте свойство знака векторного произведения и от углов можно будет избавится. По крайней мере мне это почти всегда удавалось.
Так не отличить углы х и 180-х.
Нарисуйте конкретный пример на экране. Может быть мы подразумеваем разные вещи.
...
Рейтинг: 0 / 0
10.02.2009, 22:32:15
| Ответить | Цитировать | Написать  
108 сообщений из 108, показаны все 5 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как определить принадлежит ли точка прямоугольнику
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=16&tid=1344672]:
 0ms
get settings:
 7ms
get forum list:
 12ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 1714ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 96ms
get tp. blocked users:
 1ms
others: 225ms
total:  2073ms
созд. / загр.: 2073ms
x
x
Закрыть


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