Форум программистов, компьютерный форум CyberForum.ru

Точка в треугольнике - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 90, средняя оценка - 4.93
Непрограммистка
0 / 0 / 0
Регистрация: 15.09.2010
Сообщений: 45
29.12.2010, 18:24     Точка в треугольнике #1
Помогите!
даны три вершины треугольника с координатами(коорд вводятся с клавиатуры) А(х1,y1) B(х2,y2) и С(х3,y3). И вводятся координаты другой точки Д(х4,y4)-и нужно определить принадлежит эта точка треугольнику или нет!А перед этим еще проверить возможен ли треугольник с такими точками.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.12.2010, 18:24     Точка в треугольнике
Посмотрите здесь:

C++ Лежит ли точка в круге и треугольнике
C++ нахождение всех углов в треугольнике
Треугольник в треугольнике C++
Дана точка М(x, y). Присвоить z = 1, если точка принадлежит окружности с радиусом R и центром в точке (a, b) и z = 0 в противном случае. C++
C++ Даны отрезки [a, b] и [c, d] и точка A с координатой х. Определить, принадлежит ли данная точка одному из этих отрезков, обоим или лежит вне их
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
29.12.2010, 19:39     Точка в треугольнике #2
Цитата Сообщение от Непрограммистка Посмотреть сообщение
даны три вершины треугольника с координатами(коорд вводятся с клавиатуры) А(х1,y1) B(х2,y2) и С(х3,y3). И вводятся координаты другой точки Д(х4,y4)-и нужно определить принадлежит эта точка треугольнику или нет!А перед этим еще проверить возможен ли треугольник с такими точками.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
 
struct point
{
    double x;
    double y;
};
 
bool foo(point p[])
{
    int a = (p[1].x - p[0].x) * (p[2].y - p[1].y) * (p[1].y - p[0].y),
    b = (p[2].x - p[0].x) * (p[3].y - p[2].y) * (p[2].y - p[0].y),
    c = (p[3].x - p[0].x) * (p[1].y - p[2].y) * (p[3].y - p[0].y);
 
    return (a >= 0 && b >= 0 && c >= 0) ||
                (a <= 0 && b <= 0 && c <= 0)? 1 : 0;
}
 
bool prov(point p[])
{
    return p[1].x == p[2].x && p[2].x == p[3].x? 0 :
                p[1].y == p[2].y && p[2].y == p[3].y? 0 : 1;
}
 
int main()
{
    const size_t n = 4;
    point p[n];
 
    std::cout << "\n\nEnter coord point: ";
    for(size_t i = 0; i < n; ++i)
    {
        if(i > 0)
            std::cout << "\n\nEnter tringale coord " << i << ": ";
 
        std::cout << "\n\nx" << i << " -> ";
        std::cin >> p[i].x;
        std::cout << "\n\ny" << i << " -> ";
        std::cin >> p[i].y;
    }
 
    if(prov(p))
    {
        if(foo(p))
           std::cout << "\n\tYes" << std::endl;
 
        else
           std::cout << "\n\tNo" << std::endl;
    }
 
    else
        std::cout << "\n\tTringale not found" << std::endl;
 
    return 0;
}
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
29.12.2010, 20:41     Точка в треугольнике #3
asics, как у вас работает проверка на возможность существования треугольника с задаными координатами?
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
29.12.2010, 20:46     Точка в треугольнике #4
Mayonez, Если точки находятся на одной линии, то соответственно нельзя построить данный треугольник, а что что-то не так ?
Алексaндр
 Аватар для Алексaндр
131 / 108 / 5
Регистрация: 04.12.2010
Сообщений: 313
29.12.2010, 20:47     Точка в треугольнике #5
А как он может не существовать? 3 точки всегда преобразуют одну плоскость. Следовательно, и треугольник. Единственный вариант - координаты точек совпадут...
Да, или на одной прямой. Это можно по одной формуле (расположение то4ки относительно прямой) вычеслить...
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
29.12.2010, 20:55     Точка в треугольнике #6
Цитата Сообщение от Алексaндр Посмотреть сообщение
3 точки всегда преобразуют одну плоскость.
Ошыбаетесь, три точки которые не лежат на одной прямой всегда преобразуют одну и только одну плосткость.Это вытекает из аксиомы стереометрии, точно уже не помню какой именно.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
29.12.2010, 21:01     Точка в треугольнике #7
Цитата Сообщение от asics Посмотреть сообщение
а что что-то не так ?
ну, например, для координат треугольника 0 0, 2 2, 3 3
проверка дает +

Добавлено через 2 минуты
а как проверяется приналежность точки треугольнику? Через площадь???
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
29.12.2010, 21:07     Точка в треугольнике #8
Mayonez, По этому алгоритму.

Добавлено через 3 минуты
Цитата Сообщение от Mayonez Посмотреть сообщение
ну, например, для координат треугольника 0 0, 2 2, 3 3
проверка дает +
Ов, пардон, не доглидел.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
29.12.2010, 21:16     Точка в треугольнике #9
Ввод:
0.346
0.236

-0.474
-0.568

0.567
2.346

2.437
-0.2

выдает NO
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
29.12.2010, 21:29     Точка в треугольнике #10
Mayonez, А если так ?
C++
1
2
3
4
5
6
7
8
9
bool foo(point p[])
{
    int a = (p[1].x - p[0].x) * (p[2].y - p[1].y) - (p[2].x - p[1].x) * (p[1].y - p[0].y),
    b = (p[2].x - p[0].x) * (p[3].y - p[2].y) - (p[3].x - p[2].x) * (p[2].y - p[0].y),
    c = (p[3].x - p[0].x) * (p[1].y - p[3].y) - (p[1].x - p[3].x) * (p[3].y - p[0].y);
 
    return (a >= 0 && b >= 0 && c >= 0) ||
                (a <= 0 && b <= 0 && c <= 0)? 1 : 0;
}
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
29.12.2010, 21:45     Точка в треугольнике #11
Проще через площади посчитать ИМХО...
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
29.12.2010, 21:46     Точка в треугольнике #12
Чтобы проверить, можно ли образовать с заданых точек треугольник, нужно найти длину всех сторон и воспользоватся тем, что сумма двух любых сторон не должна превышать третью
Igor
 Аватар для Igor
4582 / 3341 / 287
Регистрация: 11.11.2010
Сообщений: 6,118
Записей в блоге: 2
29.12.2010, 21:50     Точка в треугольнике #13
Допустим имеется треугольник ABC, находим его площадь по трем вершинам, далее, чтобы определить попадает ли точка в заданную область находим площади треугольников: DAB, DBC, DAC; если Sabc=Sdab+Sdbc+Sdac тогда точка принадлежит.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
29.12.2010, 21:53     Точка в треугольнике #14
Цитата Сообщение от silent_1991 Посмотреть сообщение
Проще через площади посчитать ИМХО...
Можно и через площади, но тогда нужно, чтобы координаты были целыми числами, тогда площадь - полуцелое число. Тогда можна сравнить удвоенные величины площадей (найденых через псевдоскалярное произведение)
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
29.12.2010, 21:57     Точка в треугольнике #15
Если координаты - целые числа:
Точка в треугольнике
Находим площадь ABC. Если она равна площади ABD+BCD+ADC значит точка лежит внутри треугольника.
В противном случае площадь ABC будет меньше второй суммы
найти площадь таким образом:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cmath>
using namespace std;
 
struct point
{
   int x;
   int y;
};
 
int area(point a, point b, point c)
{
   return abs((a.x - c.x)*(b.y - c.y) + (b.x-c.x)*(c.y-a.y));
}
 
int main()
{
   /////////////////////////////////////////////////////////////////////////////
   point a, b, c, d;
   cin >> a.x >> a.y;
   cin >> b.x >> b.y;
   cin >> c.x >> c.y;
   cin >> d.x >> d.y;
   /////////////////////////////////////////////////////////////////////////////
   if (area(a, b, c) == area(a, b, d) + area(a, d, c) + area(b, d, c))
      cout << "In\n";
   else 
      cout << "Out\n";
   /////////////////////////////////////////////////////////////////////////////
   return 0;
}
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
29.12.2010, 21:57     Точка в треугольнике #16
Mayonez, а что, нынче с дробными числами работать не удаётся? Аппаратные трудности? Или над их полем умножение не определили?
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
29.12.2010, 22:01     Точка в треугольнике #17
Цитата Сообщение от silent_1991 Посмотреть сообщение
Аппаратные трудности?
скорее програмные
допустим, площадь треугольника 15 ед^2
елси точка внутри имеет НЕ целые координаты:
10.783245324623 + 2.125346347 + 2.103246326236 не равно 15.0!
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
29.12.2010, 22:05     Точка в треугольнике #18
Mayonez, если уж на то пошло, то 15 не равно 15 (в том виде, в котором это 15 хранится в типе double). Поэтому сравнивают переменные типа double не так. Обычно это делают так:
C++
1
2
3
4
if (fabs(a - b) < 1E-8)
    std::cout << "Равны";
else
    std::cout << "Не равны";
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
29.12.2010, 22:17     Точка в треугольнике #19
Цитата Сообщение от silent_1991 Посмотреть сообщение
Mayonez, если уж на то пошло, то 15 не равно 15 (в том виде, в котором это 15 хранится в типе double). Поэтому сравнивают переменные типа double не так. Обычно это делают так:
а если эта погрешность окажется и точка будет лежать за треугольником - программа выдаст - ДА
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2010, 22:33     Точка в треугольнике
Еще ссылки по теме:

C++ Определить, находится ли точка в треугольнике
Найти углы в треугольнике C++
C++ Определить и напечатать, находится ли точка в треугольнике

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
29.12.2010, 22:33     Точка в треугольнике #20
Mayonez, к сожалению, когда рассчитывают траектории космических кораблей, пользуются именно тем способом сравнения, который я указал...

Добавлено через 3 минуты
А вообще я не понял, о чём мы спорим? Те же погрешности появляются и в псевдоскалярном произведении... Что вы хотели, компьютер - вещь дискретная, и при расчётах всегда найдется интервал меньше, чем минимально возможный, представимый в памяти...
Yandex
Объявления
29.12.2010, 22:33     Точка в треугольнике
Ответ Создать тему
Опции темы

Текущее время: 14:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru