Программе необходимо прочитать значения трех координат.
- P1 (x1, y1)
- P2 (x2, y2)
- P3 (x3, y3)
А также другую координату P (x, y) и определите, находится ли эта точка внутри треугольника, образованного из трех точек выше.
KevinKZ 9 Ноя 2012 в 05:38
Это простая математика, и, вероятно, она относится к программистам или информатике. также дубликат stackoverflow .com/questions/2049582/…
9 Ноя 2012 в 05:40
Похоже, у вас репутация человека, который просто просит решения домашних заданий. Прочтите этот сайт whathaveyoutried.com и выполните поиск в Google по запросу «узнайте, находится ли точка внутри треугольника».
Fantastic Mr Fox
9 Ноя 2012 в 05:43
Я голосую за закрытие этого вопроса, потому что он лучше подходит для math.stackexchange.com.
8 Сен 2021 в 18:25
Отвечает ли это на ваш вопрос?
Как определить, находится ли точка в 2D треугольник?
9 Сен 2021 в 02:39
3 ответа
Лучший ответ
Правильный способ сделать это — вычислить барицентрические координаты четвертой точки с учетом три точки вашего треугольника. Формула для их вычисления приведена в конце раздела «Преобразование в барицентрические координаты», но я надеюсь дать здесь менее сложное математическое объяснение.
Математика без Ху%!ни. Уравнение плоскости.
Для простоты предположим, что у вас есть структура point , которая имеет значения x и y . Вы определили свои баллы как:
point p1(x1, y1); point p2(x2, y2); point p3(x3, y3); point p(x,y); //
Теперь барицентрические координаты, обычно называемые alpha , beta и gamma , вычисляются следующим образом:
float alpha = ((p2.y — p3.y)*(p.x — p3.x) + (p3.x — p2.x)*(p.y — p3.y)) / ((p2.y — p3.y)*(p1.x — p3.x) + (p3.x — p2.x)*(p1.y — p3.y)); float beta = ((p3.y — p1.y)*(p.x — p3.x) + (p1.x — p3.x)*(p.y — p3.y)) / ((p2.y — p3.y)*(p1.x — p3.x) + (p3.x — p2.x)*(p1.y — p3.y)); float gamma = 1.0f — alpha — beta;
Если все alpha , beta и gamma больше, чем 0 , то точка p лежит внутри треугольника, состоящего из точек p1 , p2 и p3 .
Это объясняется тем, что точку внутри треугольника можно описать с помощью точек треугольника и трех коэффициентов (по одному для каждой точки в диапазоне [0,1]):
p = (alpha)*p1 + (beta)*p2 + (gamma)*p3
Перестановка этой функции дает вам формулу для вычисления барицентрических координат, но я чувствую, что шаги для этого могут выходить за рамки вопроса. Они представлены на странице Википедии, которую я связал вверху.
Отсюда следует, что каждый коэффициент должен быть больше 0, чтобы точка p находилась в пределах области, описываемой тремя точками.
kevintodisco 9 Ноя 2012 в 06:18
Имейте в виду, что я все еще учусь в старшей школе, и многие вещи о барицентрических координатах мне совершенно неизвестны. В любом случае, спасибо 🙂
Источник: question-it.com
Требовалось написать программу которая определяет лежит ли точка а внутри
Задача. Даны координаты трех точек (A),(B),(C). Точки расположены так, что образуют треугольник. Дана еще одна точка (D). Необходимо проверить лежит ли эта точка внутри треугольника (triangle ABC).
Программирование на С++. Урок 10. Попадает ли точка в заштрихованную область
Написать код программы на #С++.
Решение. Сразу заметим, что здесь будет предложено решение, которое нельзя назвать наилучшим. Это — быстрое решение, но имеет целый ряд недостатков. Классическая идея для решения состоит в том, что если точка (D) лежит внутри треугольника (triangle ABC), то получаются три треугольника, содержащихся внутри данного и сумма их площадей должна равняться площади данного треугольника.
Т.е. должно выполняться равенство: [S_=S_+S_+S_] А теперь поясним проблему. Вам придется сравнивать значения двух действительных чисел — площадь данного треугольника и сумму площадей трех внутренних треугольников. А, как известно, это можно сделать только с определенной точностью. На практике рассматривают разность этих площадей по модулю и сравнивают с маленьким числом, задающим точность сравнения. А это плохо.
Для решения задачи воспользуемся другой идеей:
Все точки треугольника (и любого выпуклого многоугольника) должны лежать по одну сторону от прямой, проходящей через каждую его сторону.
Запишем уравнение прямой, проходящей, например, через точки A и B. Получим: [left( x — x_A right) left( y_B — y_A right) — left( y — y_A right) left( x_B — x_A right) = 0]. Уравнение записано в такой форме, чтобы не приходилось выполнять деление и переживать о нуле в знаменателе.
Теперь для любой точки (left( x;y right)) мы можем вычислить левую часть приведенного равенства. Для точек, лежащих на прямой мы должны получать ноль. В тоже время прямая разобьёт плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения. А точки из другой полуплоскости — отрицательные.
Как определить, лежат ли точки на одной прямой?
Задаем координаты 4 точек с клавиатуры (x и y). Как написать условие, которое определяет лежат ли хотя бы три из этих точек на одной прямой?
Отслеживать
8,647 17 17 золотых знаков 73 73 серебряных знака 180 180 бронзовых знаков
задан 21 ноя 2011 в 15:55
danny_rules danny_rules
126 2 2 золотых знака 2 2 серебряных знака 11 11 бронзовых знаков
Первая часть понятно, а там где «правда» и «ложь» не совсем, две точки всегда могут лежать на одной прямой
21 ноя 2011 в 15:59
4 ответа 4
Сортировка: Сброс на вариант по умолчанию
Можете воспользоваться уравнением прямой, проходящей через две точки:
(x — x_1) / (x_2 — x1) = (y — y_1) / (y_2 — y_1)
Если уравнение будет выполнятся для какой-либо другой точки — она находится на этой прямой
UPD: Собственно для трех точек условие будет выглядеть вот так:
if ((x_3 — x_1) / (x_2 — x_1) == (y_3 — y_1) / (y_2 — y_1)) /*Точки 1, 2, 3 — лежат на одной прямой */
Отслеживать
ответ дан 21 ноя 2011 в 16:05
Sergii Kozlov Sergii Kozlov
2,468 15 15 серебряных знаков 13 13 бронзовых знаков
21 ноя 2011 в 16:17
Спасибо, поправил
21 ноя 2011 в 16:19
Ага, пожалуйста.
И еще: лучше пользоваться произведениями разностей, чем их отношением. Тогда можно координаты объявлять int и не иметь мороки со сравнением double (float).
21 ноя 2011 в 16:42
спасибо, BuilderC
21 ноя 2011 в 16:47
Все правильно кроме знака «= расстояние от точки до прямой». Алгоритм легко гуглится. Если это расстояние меньше Tol, значит точка лежит на прямой. Однако для большинства задач это — излишнее усложнение.
Отслеживать
ответ дан 27 окт 2016 в 11:36
161 1 1 серебряный знак 2 2 бронзовых знака
Для целочисленных координат можно использовать формулу:
bool function IsPointsOnLine(int x1, int y1, int x2, int y2, int x3, int y3)
или тоже самое, но с кешированием:
void PreIsPointsOnLine(int x1, int y1, int x2, int y2, int dy, int dx = x2 — x1; dy = y2 — y1; ds = x1 * y2 — x2 * y1; >bool IsPointsOnLine(int dx, int dy, int ds, int x3, int y3)
Для четырёх точек можно перебрать четыре условия, поочерёдно исключая одну из точек:
bool function IsPointsOnLine(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) < if (IsPointsOnLine(x2, y2, x3, y3, x4, y4) || IsPointsOnLine(x1, y1, x3, y3, x4, y4) || IsPointsOnLine(x1, y1, x2, y2, x4, y4) || IsPointsOnLine(x1, y1, x2, y2, x3, y3) ||) < return true; >return false; >
Для того, чтобы не было переполнения, числа не должны быть близки к границам целочисленного типа переменной.
Источник: ru.stackoverflow.com