Официальный сайт студ.городка НГТУ
Программирование и БД » Алгоритм/треугольник 

#1  21.12.07 15:12

Алгоритм/треугольник

Чтот не могу придумать как определить
покрывает ли точку треугольник..

Подскажите идею.

точка и треугольник произвольные..

---
Была идейка вычислить все уравнения сторон треугольника
у=кх+б.. но эт ни к чему, кроме путаницы не привело(((

Offline

#2  21.12.07 15:48

Re: Алгоритм/треугольник

посчитай площади 4-ех треугольников (т.е. 1 - исходный треугольник и еще 3 - это по две вершины и точка)
если площать исходного будет совпадать с суммой трех, то точка в треугольнике

Offline

#3  21.12.07 15:53

Re: Алгоритм/треугольник

Jaguar, блин, точно))))
спасиб! ))

Offline

#4  21.12.07 16:09

Re: Алгоритм/треугольник

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

Offline

#5  21.12.07 16:17

Re: Алгоритм/треугольник

еще один метод...
составляешь канонические ур-ия трех прямых через вершины треугольника и делаешь три проверки:
точка всегда должна лежать по одну сторону от прямой с третей вершиной

этот метод надежнее, т.к. при вычислении площадей погрешности могут быть больше

Offline

#6  22.12.07 12:39

Re: Алгоритм/треугольник

Jaguar, дополнение - нужно обходить стороны треугольника по часовой или против часовой стрелки, а не как попало.

Offline

#7  22.12.07 16:06

rzk
Профиль

Re: Алгоритм/треугольник

Forsage, какая разница? Где подвох? Проясни ситуацию.

Offline

#8  22.12.07 21:48

Re: Алгоритм/треугольник

Forsage написал(а):

Jaguar, дополнение - нужно обходить стороны треугольника по часовой или против часовой стрелки, а не как попало.

А можно пройти их как попало? Там либо по часовой, либо против.

Offline

#9  22.12.07 22:16

Re: Алгоритм/треугольник

2 All, через площади все нормально решилось. Точность выбрал 0.01

Offline

#10  23.12.07 00:39

Re: Алгоритм/треугольник

Forsage написал(а):

дополнение - нужно обходить стороны треугольника

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

Offline

#11  24.12.07 12:25

Я
Профиль

Re: Алгоритм/треугольник

А для не выпуклого многоугольника помнится лучик из точки пускали.

Offline

#12  24.12.07 16:39

Re: Алгоритм/треугольник

Я, а! ну, да... про это я забыл... ессно, только для выпуклых много угольников...

Offline

#13  25.12.07 10:41

Я
Профиль

Re: Алгоритм/треугольник

Jaguar, в том то и дело, что для любых.

Offline

Программирование и БД » Алгоритм/треугольник 

ФутЕр:)

© Hostel Web Group, 2002-2025.   Сообщить об ошибке

Сгенерировано за 0.024 сек.
Выполнено 11 запросов.