Обьект внутри четырех угольника Опции

[gsm_starter]

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

Но на AVR этот алгоритм работает очень долго, много времени тратится. Подскажите как сделать оптимальнее? Если поделитесь кусками кода вообще будет супер.
Заранее спасибо.

[Oldring]

Но на AVR этот алгоритм работает очень долго, много времени тратится. Подскажите как сделать оптимальнее? Если поделитесь кусками кода вообще будет супер.
Заранее спасибо.

Ускорить на AVR можно так.

1. Отказываетесь от плавающей арифметики. Оптимизируете целочисленные проверки на ассемблере, чтобы не вычислять лишних промежуточных результатов.

2. Считаете количество сторон четырехугольника, пересекающих вертикальную координату точки слева от неё. При этом сразу быстро простыми сравнениями вертикальных координат отсекаются стороны, лежащие целиком выше или ниже горизорнтали точки. Также быстро учитываются отрезки, целиком лежащие (стоящие) слева или справа от точки. Остается проверить только отрезки, обе координаты концов которых лежат по разные стороны от точки. Проверяете, вычисляя знак векторного произведения и учитывая направление отрезка. Тут придется умножать. Впрочем, если отрезок короткий - можете пройтись по его точкам Брезенхамом.

3. Если подсчитанное количество таких отрезков нечетное - точка внутри четырехугольника.

4. И не забудьте, что точка может лежать точно на отрезке. Что в этом случае делать - вам виднее.