Здравствуйте. Нужно сделать следующее. Есть 4 точки (x и y-координаты) которые формируют четырехугольник. Так же есть точка с координатами. Нужно определить является ли точка внутри четырех угольника. Сейчас делаю так. Разбиваю четырехугольник на два треугольника. Если точка в одном их треугольников, то она и в 4-угольнике в целом. Далее как я определяю внутри мы треугольника или нет. Я имея три координаты могу посчитать площадь треугольника. Точка внутри треугольника делит его три три треугольника. Так вот если сумма трех треугольников равна площади большого треугольника то точка лежит внутри. Вот.
Но на AVR этот алгоритм работает очень долго, много времени тратится. Подскажите как сделать оптимальнее? Если поделитесь кусками кода вообще будет супер. Заранее спасибо.
|