реклама на сайте
подробности
 
 Wiki Wiki  Photo Photo  Forum Forum  Reviews Reviews  Help (!) Help (!)
 
> Обьект внутри четырех угольника
gsm_starter
сообщение Jun 30 2010, 15:35
Сообщение #1


Участник
*

Группа: Участник
Сообщений: 21
Регистрация: 14-01-10
Пользователь №: 54 809
Здравствуйте. Нужно сделать следующее. Есть 4 точки (x и y-координаты) которые формируют четырехугольник. Так же есть точка с координатами. Нужно определить является ли точка внутри четырех угольника.
Сейчас делаю так. Разбиваю четырехугольник на два треугольника. Если точка в одном их треугольников, то она и в 4-угольнике в целом.
Далее как я определяю внутри мы треугольника или нет. Я имея три координаты могу посчитать площадь треугольника. Точка внутри треугольника делит его три три треугольника. Так вот если сумма трех треугольников равна площади большого треугольника то точка лежит внутри. Вот.

Но на AVR этот алгоритм работает очень долго, много времени тратится. Подскажите как сделать оптимальнее? Если поделитесь кусками кода вообще будет супер.
Заранее спасибо.
Go to the top of the page
 
+Quote Post
 
 Start new topic
Ответов
gsm_starter
сообщение Jul 13 2010, 07:27
Сообщение #2


Участник
*

Группа: Участник
Сообщений: 21
Регистрация: 14-01-10
Пользователь №: 54 809
Нет, впуклые исключены.
Go to the top of the page
 
+Quote Post
Oldring
сообщение Jul 13 2010, 07:38
Сообщение #3


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874
Цитата(gsm_starter @ Jul 13 2010, 11:27) *
Нет, впуклые исключены.


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


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post

Сообщений в этой теме
- gsm_starter   Обьект внутри четырех угольника   Jun 30 2010, 15:35
- - aaarrr   Ужас какой! Четырехугольник можно рассматриват...   Jun 30 2010, 16:18
- - mluk   Если деление на треугольники прошло успешно (с нев...   Jun 30 2010, 16:32
|- - aaarrr   Цитата(mluk @ Jun 30 2010, 20:32) как же ...   Jun 30 2010, 16:50
|- - mluk   Цитата(aaarrr @ Jun 30 2010, 20:50) Опред...   Jul 1 2010, 05:15
|- - mluk   Здесь надо знак выбирать такой же как при подстано...   Jul 1 2010, 05:28
|- - MrYuran   Цитата(mluk @ Jul 1 2010, 09:28) И это ра...   Jul 1 2010, 06:28
|- - ig_z   Пару месяцев назад на собеседовании в одну модную ...   Jul 1 2010, 08:15
|- - fontp   QUOTE (ig_z @ Jul 1 2010, 12:15) Я когда ...   Jul 1 2010, 08:44
|- - Tanya   Цитата(fontp @ Jul 1 2010, 12:44) Именно ...   Jul 1 2010, 08:57
|- - fontp   QUOTE (Tanya @ Jul 1 2010, 12:57) Все это...   Jul 1 2010, 09:04
|- - Tanya   Цитата(fontp @ Jul 1 2010, 13:04) Не совс...   Jul 1 2010, 09:21
- - MrYuran   У вас что там, графический ускоритель на АВР? М...   Jul 1 2010, 05:24
- - aaarrr   Цитата(mluk @ Jul 1 2010, 09:15) Ясно, чт...   Jul 1 2010, 05:43
|- - gsm_starter   Цитата(aaarrr @ Jul 1 2010, 08:43) Всего-...   Jul 12 2010, 18:07
|- - scifi   Цитата(gsm_starter @ Jul 12 2010, 22:07) ...   Jul 12 2010, 19:44
- - Oldring   Цитата(gsm_starter @ Jun 30 2010, 19:35) ...   Jul 1 2010, 09:31
|- - mluk   Проще сравнивать знак варажеия проверяемой точки с...   Jul 13 2010, 03:02
- - scifi   Цитата(gsm_starter @ Jul 13 2010, 11:27) ...   Jul 13 2010, 05:19
|- - mluk   Цитата(scifi @ Jul 13 2010, 09:19) Тогда ...   Jul 13 2010, 05:34
- - Muscat   А можно я влезу тут и спрошу? Почему нельзя опреде...   Jul 13 2010, 05:44
- - mluk   Цитата(Muscat @ Jul 13 2010, 09:44) А мож...   Jul 13 2010, 05:54

 

Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

RSS Текстовая версия Сейчас: 18th July 2025 - 21:31
Рейтинг@Mail.ru


Страница сгенерированна за 0.01381 секунд с 7
ELECTRONIX ©2004-2016