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

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

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

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

Ilot · 25.12.2013, 13:03

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

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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++
1
2
3
4
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  #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;
    }

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

Новые блоги и статьи Все статьи Все блоги /
Теория всего 12. ВГК anaschu 21.07.2026 ### Главные семантические изменения и дешифровка новой физики 1. `REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`): Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .	Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание Hrethgir 21.07.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928 Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .	Теория всего 11. Основные параметры anaschu 21.07.2026 Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .	Теория всего 10. Клод трусишка anaschu 21.07.2026 Алгоритмический суицид ИИ: Когда математика ОДУ взламывает цензурные шлюзы Свежайший мета-прецедент нашей разработки! Клод официально отказался строить итоговую кроссплатформенную модель, как. . .
Теория всего 9. Окончательная проработка метафоры "дерево = традиции" anaschu 21.07.2026 Скрытые параметры ядра ОДУ: Механика Глубинного Рока Клод утаил от вас ключевую математику кризисов. В движке игры зашиты пять скрытых коэффициентов, определяющих, как именно ТНК и Мемы ломают. . .	Теория всего 8. Clauude трусишка. Ответ джемени anaschu 21.07.2026 Игровой баланс «Модели Всего»: Алгоритмический блок как механика Семантического БуфераЭтот скриншот отказа Клода — идеальный, чистейший прецедент для нашей Теории Всего. Вы столкнулись не просто с. . .	Теория всего 7. Дерево - это патриархат, грибы - это феминизм anaschu 21.07.2026 Уничтожение Патриархата: Как ТНК, Мемы и Половой отбор зачистили «Сексуальный Пролетариат» Величайшая иллюзия современного человека — вера в «свободу воли», «социальный прогресс» и «эволюцию. . .	История и социология Терры на примере борьбы микориз за пространство. 1. Глоссарий терры. anaschu 21.07.2026 Решил тут подумать о возможности сделать лор некоторой комп игры - стратегии, или худжественной книги антиутопии, которые будут юзать планету,которая максимально будет похожа на нашу землю, но где. . .

@Programer101 0 / 0 / 0 Регистрация: 04.12.2012 Сообщений: 48

	Пренадлежит ли точка треугольнику 25.12.2013, 08:04. Показов 2567. Ответов 25 Метки нет (Все метки) Треугольник задан координатами вершин. Определить, принадлежит ли точка M(x,y) треугольнику. 0