Пренадлежит ли точка треугольнику

@Programer101 · Регистрация: 04.12.2012

Author24 — интернет-сервис помощи студентам

Треугольник задан координатами вершин. Определить, принадлежит ли точка M(x,y) треугольнику.

Ilot · 25.12.2013, 13:03

Ну уж если вам действительно нечем заняться давайте пободоемся.

Кликните здесь для просмотра всего текста

C++

int Point::classify(Point &p0, Point &pl)
{
  Point p2 = *this;
  Point a = p1 - pO;//+1
  Point b = p2 - pO;//+1
  double sa = a. x * b.y - b.x * a.y;//+3
  if (sa > 0.0)
    return LEFT;//здесь большой шанс выйти из функции.
  if (sa < 0.0)
    return RIGHT;//здесь большой шанс выйти из функции.
  if ((a.x * b.x < 0.0) || (a.y * b.y < 0.0))
    return BEHIND;
  if (a.length() < b.length())
    return BEYOND;
  if (pO == p2)
    return ORIGIN;
  if (p1 == p2)
    return DESTINATION;
  return BETWEEN;
}

И таких вызовов три.
Повторюсь еще раз мне не хочется вам, что либо доказывать...
Вам метод не универсален, так как не дает правильного ответа если точки лежат на одной прямой. Придется лепить костыли. Это раз. Все вычисления в ваше алгоритме придется выполнять полностью в отличае от второго метода.

@SatanaXIII · 25.12.2013, 13:09

Не по теме:

Сообщение от valeriikozlov

Если точки образующие треугольник лежат на одной прямой то это не треугольник

Кстати по моему называется вырожденный треугольник.

valeriikozlov · 25.12.2013, 13:44

Сообщение от SatanaXIII

Кстати по моему называется вырожденный треугольник.

Сообщение от Ilot

Point a = p1 - pO;//+1

тут неправильно. смотрим здесь:

C++

Point Point::operator- (Point &p)
{
  return Point (x - р.х, у - p. у);
}

так что не +1, а +2
Но давайте попорядку. Начнем с этого:

Сообщение от Ilot

Вам метод не универсален, так как не дает правильного ответа если точки лежат на одной прямой.

(кстати это не мой метод)
Здесь два случая: точка M не лежит на этой прямой - в этом случае будет правильный ответ. В случае если точка М лежит на этой прямой, то будет ответ неправильный. Но это не недостаток. В первом алгоритме отдельно расчитывается для трех отрезков: принадлежит ли точка М этим отрезкам или нет. Во втором варианте можно даже проще сделать эту проверку: например так - если площадь треугольника равна 0, и сумма площадей трех треугольников равна 0, то берем самый длинный отрезок и проверяем принадлежность точки М только ему, а не всем трем.

Сообщение от Ilot

Придется лепить костыли.

придется лепить один костыль, в отличие от трех таких же в первом методе.

Сообщение от Ilot

Все вычисления в ваше алгоритме придется выполнять полностью в отличае от второго метода.

это не показатель. Я могу например сделать так: расчитываю площадь основного треугольника S (7 операций), расчитываю площадь первого треугольника s1 (еще 7 операций). Сравниваю их сразу и если s1 уже больше S сразу выдаю ответ - не принадлежит. И могу утверждать что второй способ лучше первого , т.к. у него в лучшем случае всего 14 операций и одно сравнение.

Добавлено через 8 минут
кстати про этот случай:

Сообщение от Ilot

если точки лежат на одной прямой.

именно в этом случае в "суперском" первом методе происходит проверка на равенство вещественных чисел. А это значит что именно первый метод:

Сообщение от Ilot

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

Ilot · 25.12.2013, 14:04

Сообщение от valeriikozlov

Здесь два случая: точка M не лежит на этой прямой - в этом случае будет правильный ответ. В случае если точка М лежит на этой прямой, то будет ответ неправильный. Но это не недостаток. В первом алгоритме отдельно расчитывается для трех отрезков: принадлежит ли точка М этим отрезкам или нет. Во втором варианте можно даже проще сделать эту проверку: например так - если площадь треугольника равна 0, и сумма площадей трех треугольников равна 0, то берем самый длинный отрезок и проверяем принадлежность точки М только ему, а не всем трем.

Костыль.

именно в этом случае в "суперском" первом методе происходит проверка на равенство вещественных чисел. А это значит что именно первый метод:

Ошибаетесь. Так как сравниваются два исходных числа, а не результат их преобразования. Как говорил Кузьма Прутков: смотри в корень!

это не показатель. Я могу например сделать так: расчитываю площадь основного треугольника S (7 операций), расчитываю площадь первого треугольника s1 (еще 7 операций). Сравниваю их сразу и если s1 уже больше S сразу выдаю ответ - не принадлежит. И могу утверждать что второй способ лучше первого , т.к. у него в лучшем случае всего 14 операций и одно сравнение.

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

valeriikozlov · 25.12.2013, 14:20

Сообщение от Ilot

Костыль.

а в первом варианте этих же костылей уже три )

Не по теме:

ладно пора заканчивать - доказать мне что первый вариант реально лучше второго вы не сумели и чуствую не сумеете. просто слова что он лучше, я не принимаю в расчет )

@sergei60 · 26.12.2013, 18:57

Я находил попадает ли точка с одной стороны или с другой от отрезка так:

C++

  #include <iostream>
    #include <cmath>
  using namespace std;
     
    int main () {
    double x1,x2,y1,y2,;
    cout<<"введем координаты отрезка ";
    cin>>x1>>x2>>y1>>y2;
cout<<"введем координаты проверяемой точки";
     cin>>x>>y;
  if(y>2*(y1-y2)*(x-x1)/(x2-x1)+y2)
   cout<<"c одной стороны";
   else
   cout <<"c другой стороны";
return 0;
    }

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

@Programer101 0 / 0 / 0 Регистрация: 04.12.2012 Сообщений: 48
		1
	Пренадлежит ли точка треугольнику 25.12.2013, 08:04. Показов 2019. Ответов 25 Метки нет (Все метки) Треугольник задан координатами вершин. Определить, принадлежит ли точка M(x,y) треугольнику. 0

@SatanaXIII
	25.12.2013, 13:09 #22
	Не по теме: Сообщение от valeriikozlov Если точки образующие треугольник лежат на одной прямой то это не треугольник Кстати по моему называется вырожденный треугольник. 0

Ilot $Эксперт по математике/физике$ 2048 / 1366 / 395 Регистрация: 16.05.2013 Сообщений: 3,505 Записей в блоге: 6
	25.12.2013, 14:04	24
	Сообщение от valeriikozlov Здесь два случая: точка M не лежит на этой прямой - в этом случае будет правильный ответ. В случае если точка М лежит на этой прямой, то будет ответ неправильный. Но это не недостаток. В первом алгоритме отдельно расчитывается для трех отрезков: принадлежит ли точка М этим отрезкам или нет. Во втором варианте можно даже проще сделать эту проверку: например так - если площадь треугольника равна 0, и сумма площадей трех треугольников равна 0, то берем самый длинный отрезок и проверяем принадлежность точки М только ему, а не всем трем. Костыль. именно в этом случае в "суперском" первом методе происходит проверка на равенство вещественных чисел. А это значит что именно первый метод: Ошибаетесь. Так как сравниваются два исходных числа, а не результат их преобразования. Как говорил Кузьма Прутков: смотри в корень! это не показатель. Я могу например сделать так: расчитываю площадь основного треугольника S (7 операций), расчитываю площадь первого треугольника s1 (еще 7 операций). Сравниваю их сразу и если s1 уже больше S сразу выдаю ответ - не принадлежит. И могу утверждать что второй способ лучше первого , т.к. у него в лучшем случае всего 14 операций и одно сравнение. Я же написал арматизационное число. Вероятность того, что точка попадет на прямые задающие треугольник крайне мала. В отличает от вероятности, что новый треугольник, образованный исследуемой точкой, будет больше исходного. 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	25.12.2013, 14:20	25
	Сообщение от Ilot Костыль. а в первом варианте этих же костылей уже три ) Не по теме: ладно пора заканчивать - доказать мне что первый вариант реально лучше второго вы не сумели и чуствую не сумеете. просто слова что он лучше, я не принимаю в расчет ) 0

	26.12.2013, 18:57