#include <stdio.h>;
#include <math.h>;
#include <conio.h>
float x1,x2,x3,y1,y2,y3,s,s1,s2,s3,s4,p,p1,p2,p3,k1,k2,k3,k4,k5,k6;
void main()
{
clrscr();
puts("Vvedite x1,y1");
scanf("%f%f",&x1,&y1);
puts("Vvedite x2,y2");
scanf("%f%f",&x2,&y2);
puts("Vvedite x3,y3");
scanf("%f%f",&x3,&y3);
k1=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
k2=sqrt((0-x2)*(0-x2)+(0-y2)*(0-y2));
k3=sqrt((0-x1)*(0-x1)+(0-y1)*(0-y1));
k4=sqrt((0-x3)*(0-x3)+(0-y3)*(0-y3));
k5=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2));
k6=sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1));
p1=(k1+k2+k3)/2;
p2=(k2+k5+k4)/2;
p3=(k3+k4+k6)/2;
p=(k1+k5+k6)/2;
s1=sqrt(p1*(p1-k1)*(p1-k2)*(p1-k3));
s2=sqrt(p2*(p2-k4)*(p2-k2)*(p2-k5));
s3=sqrt(p3*(p3-k6)*(p3-k4)*(p3-k3));
s4=s1+s2+s3;
s=sqrt(p*(p-k1)*(p-k5)*(p-k6));
if (s4==s)
printf("da");
else
printf("net");
getch();
}
Задача: Принадлежит ли начало координат треугольнику (Си)
Задача: Даны действительные числа x1, x2, x3, y1, y2, y3. Принадлежит ли начало координат треугольнику с вершинами (x1, y1), (x2, y2), (x3, y3)?
Вот моё решение:
Посмотрите пожалуйста, что не правильно в моем решении. К примеру: когда я ввожу следующие значения:
х1=1,
у1=2,
х2=-3,
у2=1,
х3=2,
у3=-5, то программа пишет что нет не принадлежит, хотя если я не ошибаюсь, то начало координат принадлежит треугольнику построеному на этих вершинах.
Вот моё решение:
Код:
Посмотрите пожалуйста, что не правильно в моем решении. К примеру: когда я ввожу следующие значения:
х1=1,
у1=2,
х2=-3,
у2=1,
х3=2,
у3=-5, то программа пишет что нет не принадлежит, хотя если я не ошибаюсь, то начало координат принадлежит треугольнику построеному на этих вершинах.
А ты проверял: правильно ли считываются у тебя вводимые числа?
так как ты их сканируешь они должны идти парами, причем я не понимаю как у тебя в паре числа отделяются.
scanf("%f%f",&x1,&y1); - это типа они без разделителей должны идти вот так?:
123.234.3
Вот и скажи мне толи это 123.2 и 34.3 или 123.23 и 4.3 ?
Я извиняюсь, в принципе можно их и через пробел ввести,
а не получается потому, что надо сравнивать с некоторой точностью, т.е. приблизительно.
В целом алгоритм вроде верен.
Проблема в том что:
double a = 4;
float b = 4;
но a!=b -> опять же изза машинной погрешности :)
У самого была куча лагов с геометрией и вещественными числами.
Есть 2-а выхода:
1. Как я уже говорил: ограничиться заданием какой-то точности сравнения.
2. Вычислять все в обыкновенных дробях :) (с целыми числами таких лагов не должно быть)
так как ты их сканируешь они должны идти парами, причем я не понимаю как у тебя в паре числа отделяются.
scanf("%f%f",&x1,&y1); - это типа они без разделителей должны идти вот так?:
123.234.3
Вот и скажи мне толи это 123.2 и 34.3 или 123.23 и 4.3 ?
Я извиняюсь, в принципе можно их и через пробел ввести,
а не получается потому, что надо сравнивать с некоторой точностью, т.е. приблизительно.
В целом алгоритм вроде верен.
Проблема в том что:
double a = 4;
float b = 4;
но a!=b -> опять же изза машинной погрешности :)
У самого была куча лагов с геометрией и вещественными числами.
Есть 2-а выхода:
1. Как я уже говорил: ограничиться заданием какой-то точности сравнения.
2. Вычислять все в обыкновенных дробях :) (с целыми числами таких лагов не должно быть)
этот код для Dev-Cpp, так что возможно надо будет подключить math.h:
Код:
#include <stdio.h>
#include <stdlib.h>
typedef struct Point
{
float x;
float y;
}Point;
float Square(Point p1, Point p2, Point p3)
{
return 0.5*(p1.x*p2.y + p1.y*p3.x + p3.y*p2.x - p3.x*p2.y - p3.y*p1.x - p2.x*p1.y);
}
int main(int argc, char *argv[])
{
Point p, p1, p2, p3;
printf("test point:\n");
scanf("%f%f",&p.x,&p.y);
printf("others points:\n");
scanf("%f%f",&p1.x,&p1.y);
scanf("%f%f",&p2.x,&p2.y);
scanf("%f%f",&p3.x,&p3.y);
if (Square(p1,p2,p3)==(fabs(Square(p,p1,p2))+fabs(Square(p,p1,p3))+fabs(Square(p,p2,p3))))
{
printf("in\n");
}
else
printf("out\n");
system("PAUSE");
return 0;
}
#include <stdlib.h>
typedef struct Point
{
float x;
float y;
}Point;
float Square(Point p1, Point p2, Point p3)
{
return 0.5*(p1.x*p2.y + p1.y*p3.x + p3.y*p2.x - p3.x*p2.y - p3.y*p1.x - p2.x*p1.y);
}
int main(int argc, char *argv[])
{
Point p, p1, p2, p3;
printf("test point:\n");
scanf("%f%f",&p.x,&p.y);
printf("others points:\n");
scanf("%f%f",&p1.x,&p1.y);
scanf("%f%f",&p2.x,&p2.y);
scanf("%f%f",&p3.x,&p3.y);
if (Square(p1,p2,p3)==(fabs(Square(p,p1,p2))+fabs(Square(p,p1,p3))+fabs(Square(p,p2,p3))))
{
printf("in\n");
}
else
printf("out\n");
system("PAUSE");
return 0;
}
__AleXX__ ясно, а не подскажешь как можно ограничиться заданием какой-то точности сравнения?
kosfiz спасибо, но это немного сложновато пока, я в структурах ещё плохо разбираюсь.
kosfiz спасибо, но это немного сложновато пока, я в структурах ещё плохо разбираюсь.
Цитата: Draconit
__AleXX__ ясно, а не подскажешь как можно ограничиться заданием какой-то точности сравнения?
Дави на разность между сравниваемыми величинами если она достаточно мала (задай порог), то выдаешь "да". Да и забудь про float - это не тип :), используй double (в сканфе %lf). Да и поменьше вычисляй корень, в последние четыре вычисления вообще не нужны, а предыдущие сомнительны...
Цитата: Draconit
kosfiz спасибо, но это немного сложновато пока, я в структурах ещё плохо разбираюсь.
Даа а я уж подумал предложить алгоритм с типичной областью допустимых решений. Составляешь систему неравенств описывающих область треугольника и просто подставляешь координаты любой точки в эту систему, если условие выполняется, то точка внутри области. Алгоритм самый универсальный, но требует некоторой элементарной матподготовки. Для нахождения системы неравенств, надо найти:
1. найти уравнение каждой прямой проходящей через ребро треугольника;
2. найти градиент и определить какая полуплоскость соответствует третьей вершине для каждого отрезка.(те определиться со знаками <= и >=)
3. получим систему вида:
a1*x1+b1*x2+c1>=0;
a2*x1+b2*x2+c2>=0;
a3*x1+b3*x2+c3>=0;
подставляя в каждое неравенство координаты искомой точки (x;y) можно определить удовлетворяют ли они все трем неравенствам и получить ответ на вопрос: "лежит ли точка (x,y) в заданной области?"
А матподготовка пригодится для пункта 2
ЗЫ: Конечно если тебя интересует результат, тогда это тебе никчему:D
Цитата: WidowMaker
Да и забудь про float - это не тип :), используй double
:)
Всем спасибо за помощь, прогу сделал и главное сам разобрался:)
Цитата: WidowMaker
Составляешь систему неравенств описывающих область треугольника и просто подставляешь координаты любой точки в эту систему, если условие выполняется, то точка внутри области. Алгоритм самый универсальный, но требует некоторой элементарной матподготовки. Для нахождения системы неравенств, надо найти:
1. найти уравнение каждой прямой проходящей через ребро треугольника;
2. найти градиент и определить какая полуплоскость соответствует третьей вершине для каждого отрезка.(те определиться со знаками <= и >=)
3. получим систему вида:
a1*x1+b1*x2+c1>=0;
a2*x1+b2*x2+c2>=0;
a3*x1+b3*x2+c3>=0;
подставляя в каждое неравенство координаты искомой точки (x;y) можно определить удовлетворяют ли они все трем неравенствам и получить ответ на вопрос: "лежит ли точка (x,y) в заданной области?"
1. найти уравнение каждой прямой проходящей через ребро треугольника;
2. найти градиент и определить какая полуплоскость соответствует третьей вершине для каждого отрезка.(те определиться со знаками <= и >=)
3. получим систему вида:
a1*x1+b1*x2+c1>=0;
a2*x1+b2*x2+c2>=0;
a3*x1+b3*x2+c3>=0;
подставляя в каждое неравенство координаты искомой точки (x;y) можно определить удовлетворяют ли они все трем неравенствам и получить ответ на вопрос: "лежит ли точка (x,y) в заданной области?"
Вот это дело!
Пункт 2, на самом деле, очень прост.
Имеется уравнение прямой a*x + b*y + с = 0. Рассмотрим собственно функцию a*x + b*y + с. Для всех точек, лежащих на прямой, функция будет равной нулю, для всех точек с одной стороны от прямой - меньше нуля, с другой стороны - больше нуля. Собственно значение функции нас не интересует, только знак.
Таким образом, нужно лишь проверить, что для искомой точки знак функции будет таким же, что знак функции для третьей вершины треугольника. Допустимо также (хотя это зависит от исходной задачи), что искомая точка лежит на ребре треугольника, тогда функция для этой точки будет равной нулю.
Не вникая далеко в математику, сразу приведу вид функции для прямой, проходящей через (x1, y1) и (x2, y2):
f(x,y) = (y - y2) * (x1 - x2) - (x - x2) * (y1 - y2).
Собственно, вот код:
Код:
#include <iostream>
using namespace std;
inline double sgn (double x)
{
return x == 0 ? 0 : (x > 0 ? 1 : -1);
};
inline double function (double x1, double y1, double x2, double y2, double x, double y)
{
return (y - y2) * (x1 - x2) - (x - x2) * (y1 - y2);
}
bool check_point (double x1, double y1, double x2, double y2, double x3, double y3, double x, double y)
{
const double value = function (x1, y1, x2, y2, x, y);
return (value == 0 || sgn (value) == sgn (function (x1, y1, x2, y2, x3, y3)));
};
void main (void)
{
double x1, y1, x2, y2, x3, y3, x, y;
char c;
cout << "Enter triangle coordinates: ";
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
cout << "Enter point coordinates: ";
cin >> x >> y;
if (check_point (x1, y1, x2, y2, x3, y3, x, y)
&& check_point (x1, y1, x3, y3, x2, y2, x, y)
&& check_point (x3, y3, x2, y2, x1, y1, x, y))
cout << "Point is inside triangle";
else
cout << "Point is outside of triangle";
cin >> c;
};
using namespace std;
inline double sgn (double x)
{
return x == 0 ? 0 : (x > 0 ? 1 : -1);
};
inline double function (double x1, double y1, double x2, double y2, double x, double y)
{
return (y - y2) * (x1 - x2) - (x - x2) * (y1 - y2);
}
bool check_point (double x1, double y1, double x2, double y2, double x3, double y3, double x, double y)
{
const double value = function (x1, y1, x2, y2, x, y);
return (value == 0 || sgn (value) == sgn (function (x1, y1, x2, y2, x3, y3)));
};
void main (void)
{
double x1, y1, x2, y2, x3, y3, x, y;
char c;
cout << "Enter triangle coordinates: ";
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
cout << "Enter point coordinates: ";
cin >> x >> y;
if (check_point (x1, y1, x2, y2, x3, y3, x, y)
&& check_point (x1, y1, x3, y3, x2, y2, x, y)
&& check_point (x3, y3, x2, y2, x1, y1, x, y))
cout << "Point is inside triangle";
else
cout << "Point is outside of triangle";
cin >> c;
};
Код вроде рабочий, проверил на примере, приведенном Draconit.
Самое интересное - при работе с графикой можно заменить double на int и алгоритм останется работоспособным и целочисленным, безо всяких квадратных корней.
Есть еще один интересный алгоритм, применяемый в графике.
Создаем массив bool, в нем "рисуем" попиксельно заданный треугольник (т. е. для каждой точки (x,y) треугольника помещаем в array[x][y] = true), после чего для любой точки принадлежность треугольнику можно легко проверить с помощью массива. Причем алгоритм работает для произвольных фигур, не только для треугольников.