 |
|
Модераторы: Poseidon |
 
|
|
[Геометрия] Находится ли точка , в данном четырёхугольнике? 
| gepard |
|
|||
 Эксперт  Профиль Группа: Участник Сообщений: 2477 Регистрация: 29.2.2004 Репутация: 2 Всего: 40 |
В пространстве есть точка, лежащая в плоскости четырёхугольника. Четырёхугольник задан 4 вершинами, координаты точки и вершин известны. Как мне узнать: лежит ли эта точка в данном четырёхугольнике?
-------------------- Когда начинаются цифровые войны, а траффик разносит моё сознание по бесконечным просторам инета, подобно ветру, разносящему листву по полям, тогда и только тогда я чувствую себя свободным! © Я, Берсерк, что значит - Неистовый. |
|||
|
||||
Дата 27.1.2005, 05:32 (
Загрузка ...
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 17 Всего: 454 |
Делим четырехугольник на 2 треугольника (2 варианта, пробуем оба - на всякий случай). Проверка того что точка лежит внутри треугольника - тривиальна.
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| Alx |
|
|||
|
Ajaxy Профиль Группа: Комодератор Сообщений: 2903 Регистрация: 26.11.2003 Где: Cutopia Репутация: нет Всего: 78 |
gepard
Модератор: Ну язык-то можно указать?   |
|||
|
||||
| GoodBoy |
|
|||
 Главный джедай Профиль Группа: Модератор Сообщений: 3886 Регистрация: 8.1.2003 Где: КМВ Репутация: нет Всего: 83 |
Alx
А какая разница!!!! Тут алгоритм только и нужен! :-)))) -------------------- Чем дальше в лес, тем толще партизаны...
|
|||
|
||||
| Alx |
|
|||
|
Ajaxy Профиль Группа: Комодератор Сообщений: 2903 Регистрация: 26.11.2003 Где: Cutopia Репутация: нет Всего: 78 |
GoodBoy
т.е. мне на JS ответить, да? |
|||
|
||||
| GoodBoy |
|
|||
|
Главный джедай Профиль Группа: Модератор Сообщений: 3886 Регистрация: 8.1.2003 Где: КМВ Репутация: нет Всего: 83 |
Alx
Да запросто! :-))))) В С - то же самое практически получится... В Паскале - чуть переделать!!! А можно вообще просто алгоритм описать... :-))))) -------------------- Чем дальше в лес, тем толще партизаны...
|
|||
|
||||
| maxim1000 |
|
|||
 Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
-------------------- qqq |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 17 Всего: 454 |
maxim1000
Неправильно там. Представь четырехугольник с вершинами (0,0) (0,5) (5,-5) (-5,-5) и точку (1,1) - она лежит справа от одних сторон и слева от других... надо сперва бить на треугольники. Кстати, этот же четырехугольник объясняет почему надо пробовать оба разбиения (для четырехугольника это быстрее чем проверять вложенность). А вот тут правильно - Проверка принадлежности точки многоугольнику - особенно см. примечание trurl. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| maxim1000 |
|
||||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
это означает, что она находится снаружи многоугольника 
кстати. не стоит забывать о направлении ребер (от этого зависит справа будет точка или слева) направление ребра должно совпадать с направлением обхода... -------------------- qqq |
||||
|
|||||
| gepard |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 2477 Регистрация: 29.2.2004 Репутация: 2 Всего: 40 |
Мне нужен алгоритм, а не исходник. И почему тему перенесли в Работа, хобби и учёба -> Vingrad - Колледж -> Центр помощи Что за бред-то? Я вроде алгоритм прошу. У винграда столько ответвлений стало, что скоро заблудиться можно будет  maxim1000 Благодарю... -------------------- Когда начинаются цифровые войны, а траффик разносит моё сознание по бесконечным просторам инета, подобно ветру, разносящему листву по полям, тогда и только тогда я чувствую себя свободным! © Я, Берсерк, что значит - Неистовый. |
|||
|
||||
| Akina |
|
||||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 17 Всего: 454 |
Ты карандашик-то в руки возьми... 
Вот отсюда-то и жопа... -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
||||
|
|||||
| maxim1000 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
каюсь... был неправ... у этого алгоритма есть одно ограничение: только выпуклые многоугольники а вообще есть другой: проводим из точки луч (в любую сторну) и считаем, сколько раз он пересек границу многоугольника для простоты можно проводить луч по оси координат... -------------------- qqq |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 17 Всего: 454 |
угу. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| maxim1000 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
почитал внимательно ссылку, которую ты привел, обнаружил, что этот метод там описан...
вывод: надо мне внимательнее читать чужие сообщения а что касается комментария trurl, то сильно сомневаюсь, что оно будет вычислительно эффективным: 1. для каждого треугольника нужно будет проводить вычисление трех определителей третьего порядка - это куча вычислений 2. в случае трассировки луча - большая часть ребер вообще не будут пересекать ось, так что для них все обойдется двумя операциями сравнения, а для той небольшой части, которые будут - всего две операции умножения+несколько операций +,-,<> -------------------- qqq |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 17 Всего: 454 |
maxim1000
коммент будет вычислительно эффективен, если речь идет о проверке вхождения в полигон, не помещающийся категорически в экран, при отображении точки - т.е. когда имеют место неявные отсечения. На бесконечной плоскости - конечно эффективнее луч. Только все проще - в лоб считается точка пересечения 2 прямых (на которой луч и на которой отрезок) и делается контроль вхождения по одной из координат (если прямая не параллельна оси - пофиг по какой, а если параллельна - именно по этой). Проверка на необходимость до расчета точки пересечения имхо обойдется дороже... -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
|
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.0888 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |