Помощь - Поиск - Пользователи - Календарь
Полная версия: turbo pascal > Информатика / Программирование
Образовательный студенческий форум > Другие дисциплины > Информатика / Программирование
dimka37
Здравствуйте!
суть задачи состоит в следующем: даны координаты(х,у) трех вершин треугольника, и дана четвертая координата точки. требуется определить принадлежит ли точка треугольнику или нет.
у меня в принципе задача решена , но только для всех треугольиков кроме прямоугольных. Т.к. я действовал по следующему алгоритму решения данной задачи: я находил уравнения трех прямых которые образуют треугольник, т.е. находил угол наклона(к) к=(у1-у2)/(х1-х2) и так далее... вот здесь то и скрывается подвох... если задать координаты прямоугольного треугольника, то получается деление на ноль... вот я и не могу от этого избавиться. подскажите, как действовать?
Harch
Подробнее напишите почему деление на ноль.
dimka37
в прямоугольном треугольнике один из катетов параллелен оси У, то есть координата Х одинакова. и при нахождении угла наклона прямой к=у1-у2/х1-х2 знаменатель обращается в ноль. и это будет с любым треугольником у которого одна из сторон будет параллельна оси ординат.
Harch
ищите тогда по-другому, а именно так: если идет деление на ноль, то говорите что угол pi/2 и все smile.gif то есть просто сделайте проверку.
dimka37
спасибо, вроде бы представляю как условия будут выглядеть...
а вот еще вопросик: у меня программа работает если только точки вводить по возрастанию аргумента. а как заставить программу чтоб можно было координаты вводить в произвольном порядке?
Harch
Вводите в произвольном порядке а потом упорядочивайте по возрастанию smile.gif
dimka37
об этом я думал, но как потом нужному аргументу подставить нужное значение ординаты? в этом вопрос. есть вариант ставить условия на Х, чтоб он был между двумя другими. допустим: х2 находится между х1 и х3 тогда находим все что нам нужно. и так с каждым аргументом.
граф Монте-Кристо
А зачем у Вас вообще в алгоритме нужно вводить координаты упорядочено? Есть стандартные алгоритмы на определение принадлежности точки многоугольнику - хотя бы даже на Википедии.
Harch
Цитата
А зачем у Вас вообще в алгоритме нужно вводить координаты упорядочено? Есть стандартные алгоритмы на определение принадлежности точки многоугольнику - хотя бы даже на Википедии.


Согласен с этим. Просто я отвечал на конкретные вопросы автора темы.
Botan
Например так.
Соеденим нашу точку со всеми вершинами теугольника, и посчитаем сумму площадей получившихся маленьких треугольников (например по формуле герона). Дальше сравниваем её с площадью исходного треугольника. Если они совпадают, то точка внутри ли на границе треугольника. если больше, то точка снаружи. Если площади совпадают, то хорошо бы проверить, а не лежит ли наша точка в какой-нибудь из вершин или на границе. Реальзовать это просот: три ифа - проверка на совпадение данной точки с вершинами, и ещё три ифа : проверка того, что все площади мелких треугольников не нулевые. (Если какая-то из них нулевая, то точка на соответствующей границе). Вот и всё.
dimka37
если точка находится в какой либо вершине то это сразу видно при вводе начальных данныхsmile.gif (я над этим задумывался) а так же даже если у нас точка находится на какой либо границе треугольника то это существенно не влияет на ход программы. т.к. мы просто заранее ставим лишние условие чтобы программа не выполняла лишнего действия...
а вот интерес состоит в том что если мы ставим конечно условие на равенство площади треугольника и суммы трех других площадей то при равных площадях нам программа выдаст отказ на принадлежность точки треугольникуsmile.gif
Botan
Цитата(dimka37 @ 26.12.2010, 16:04) *

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


Насколько я понял, вы прописали нечто вроде
If(s1+s2+s3 = s) Then
WriteLn('In triangle');

Это неправильно.
Ибо дробные числа хранятся не точные. и сравнивать надо так:
Заводим некоторый епсилон

eps := 0.000000000001;

а собственно сравнение:
If (abs(s1+s2+s3-s)<eps) Then
Write('In triangle');

Функцию abs, считающую модуль числа, я думаю вы сможете написать сами ;-)

Есть другой метод.
Берём ещё одну точку, такую, что она гарантированно вне треугольника, и отреок, соединяющий нашу точку с новой точкой не проходит ни через одну вершину, и при этом не собержит ни одну сторону треугольника (например с большой вероятностью точка с координатами x+1, y+1000000, где х - абсцисса заданной точки, а у - её ордината, подойдёт). А дальше просто посчитаем число пересечений этого отрезка со сторонами треугольника. Если 0 или 2, то точка вне треугольника, если 1, то внутри. Основная загвоздка этого метода - написать функцию, определяющую, пересекаются ли отрезки.
dimka37
а для того что бы написать функцию пересечения отрезков надо составить уравнения этих прямых. . . и это опять же сводится к угловым коэффициентам прямыхsmile.gif и к возможному делению на ноль если мы k находим по формуле у1-у2/х1-х2
есть вариант представлению уравнения прямой вида ах+bу+с=0 тогда в этом случае деление на ноль отсутствуетsmile.gif
Botan
Цитата(dimka37 @ 26.12.2010, 16:56) *

а для того что бы написать функцию пересечения отрезков надо составить уравнения этих прямых. . . и это опять же сводится к угловым коэффициентам прямыхsmile.gif и к возможному делению на ноль если мы k находим по формуле у1-у2/х1-х2
есть вариант представлению уравнения прямой вида ах+bу+с=0 тогда в этом случае деление на ноль отсутствуетsmile.gif


Да. Если вы решили использовать второй метод, то прямые стоит хранить как три коэффицента в уравнении ax+by+c=0.
Однако в большинстве случаев это будет написано (извинияюсь за выражение) быдлокодом, в котором легко ошибится, да так, что легче будет написать новую программу, чем искать ошибку в этой. Поэтому рекомендую добить первый метод.

З.Ы. мне не сложно. могу привести работоспособный код. правда на С++... паскаль малость подзабыл... но перевести с С++ на паскаль обычно легко получается....
dimka37
спасибо, конечно, за активную помощь, но эта программа написана мною уже недели полторы назад примерноsmile.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.
Русская версия Invision Power Board © 2001-2024 Invision Power Services, Inc.