Компьютерный форум OSzone.net  

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)
-   Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)
-   -   Pascal (http://forum.oszone.net/showthread.php?t=29352)

Guest 22-10-2004 23:37 203480

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

Oaxa 23-10-2004 01:02 203481

Алгоритм общий для любой замкнутой фигуры (а не только для треугольника)
Строишь из этой точки луч произвольного направления и счиатешь количество пересечений со сторонами фигуры. Если пересечений четное количество (0, 2, 4...), то точка лежит вне фигуры. Если нечетное, то внутри. Для треугольника слово нечетное подразумквает только единицу. Если не понятно, могу и в формулах объяснить.

Guest 24-10-2004 22:05 203482

было бы понятнее в формулах

hasherfrog 25-10-2004 10:24 203483

Чуть-чуть оптимизации, для метода, предложенного Oaxa. Луч строите вертикальный, и "вверх". Тогда (перебором сторон треугольника) нужно будет посчитать количество сторон, которые имеют точку, лежащую между концами отрезка и имеющую x==x(точки), и у>=y(точки).
Вроде не напутал :cranky:

mavludov 25-10-2004 17:31 203484

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

Oaxa 25-10-2004 19:08 203485

Пишешь цикл от 1 до трех, решаешь три системы уравнений, в каждой из которой находишь точку пересечения луча со стороной треугольника. проверяешь, лежит ли точка пересечения между концами отрезка (в смысле, между концами стороны треугольника), если лежит, то увеличиваешь счетчик пересечений на 1. Вот, собственно, и всё. Если честно, то вопрос этот очень далеко выходит за рамки программирования на паскале. Он много ближе к курсу геометрии класс этак за 8-9-й. Тем не менее, да простят меня за оффтопик, попробую вспомнить.
уравнение прямой такое: y=ax+b.
что бы найти a и b (только что на трубе они и не сидели) для сторон отрезка делаешь так:
a = (yк-ун)/(xк-xн)
b = ук-axк = yн-axн
(н - начало отрезка, к - конец)
уравнение луча ты задавал сам, так что a и b тебе известны.
Как очень тонко подметил hasherfrog, для удобства лучше выбирать вертикальный луч. Тогда уравнение прямой, описывающей луч будет выглядеть так (блин, хочется всё бросить и послать тебя к учебнику геометрии... или алгебры, я уж даже и не помню), для вертикальной прямой: a=0, и соответственно, уравнение принимает вид y = b
Далее решаешь систему:
1: у = a(отрезка)*x + b(отезка)
2: y = b(луча)
полученные x и y - и есть точка пересечения.
Вы уж меня извините, многоуважаемый mavludov, но объяснять, как проверить, лежит ли точка пересечения между концами отрезка (а так же лежит ли она выше точки, из которой мы отправляли вышеуказанный луч) я не стану. Эдак мы и до букваря доберёмся.
Всего наилучшего!


[s]Исправлено: Oaxa, 19:09 25-10-2004[/s]

mavludov 26-10-2004 17:56 203486

спасибо всем...


Время: 11:00.

Время: 11:00.
© OSzone.net 2001-