2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Проверка условия с "погрешностью"
Сообщение16.03.2018, 16:23 
Написал программу вычисляющую площадь четырёхугольника, в том числе вычисляющую площадь "вогнутого" четырёхугольника, где одна из вершин находится внутри треугольника образованного тремя другими вершинами. Например если есть четырёхугольник ABCD и точка A лежит внутри треугольника BCD, то это можно установить проверив условие:
$BCD=ABC+ABD+ACD$
BCD-площадь треугольника BCD и т.д.

Но при вводе координат (таких что одна из точек в "недрах" треугольника) с точностью более 4-5 значащих цифр программа находит, что условие не выполняется, большой треугольник чуть-чуть не равен трём маленьких из которых он состоит и из-за этого отличия включается алгоритм вычисления площади выпуклого четырёхугольника и ошибка может быть очень значительной. Программа написана на C++, тип используемых переменных long double. Как избежать этого "чуть-чуть"?

Собственная попытка решения проблемы: усложнить проверку условия так, чтобы проверялась относительная погрешность, если $\frac{BCD-ABC-ABD-ACD}{BCD}$ меньше скажем 0,000001 то считать четырёхугольник "вогнутым", но тогда программа может принять выпуклый четырёхугольник очень близкий по внешнему виду к треугольнику за "вогнутый" и посчитать площадь немного не правильно

 
 
 
 Re: Проверка условия с "погрешностью"
Сообщение16.03.2018, 16:40 
Аватара пользователя
Проверку на выпуклость надо делать не через равенство, а через неравенство. $C$ и $D$ находятся по разные стороны от $AB$, если скалярные произведения $(AB, AC)$ и $(AB, AD)$ имеют разные знаки.

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

 
 
 
 Re: Проверка условия с "погрешностью"
Сообщение17.03.2018, 06:11 
Сравнение вещественных чисел на равенство/неравенство является ошибкой почти всегда. Есть какие-то редкие случаи, когда это можно делать, и вы каждый раз должны понимать, почему это можно в данном случае.

Если вы используете алгоритм "тупо считаем сумму площадей" для определения выпуклости/вогнутости, то у вас нет выхода, кроме как проверять на "почти равенство" и смириться с тем, что иногда будут ошибки для почти выпуклых/почти вогнутых 4-угольников. Кстати, а как вы считаете площадь?

 
 
 
 Re: Проверка условия с "погрешностью"
Сообщение18.03.2018, 15:30 
urod
Изображение
Формула 17

Ошибка каждый раз получалась очень маленькой, -19 степени, -20 степени, так что я задал условие что относительная погрешность должна быть меньше одной квадрилионной. Думаю теперь если программа и ошибётся то не ранее чем знака с 15-го

 
 
 
 Re: Проверка условия с "погрешностью"
Сообщение18.03.2018, 16:38 
SpiderHulk в сообщении #1298100 писал(а):
так что я задал условие что относительная погрешность должна быть меньше одной квадрилионной
То есть вы попросили совета, получили его и проигнорировали. Интересный подход.

 
 
 
 Re: Проверка условия с "погрешностью"
Сообщение18.03.2018, 17:17 
warlock66613 в сообщении #1298119 писал(а):
То есть вы попросили совета, получили его и проигнорировали. Интересный подход.

Не осилил

 
 
 
 Re: Проверка условия с "погрешностью"
Сообщение18.03.2018, 21:01 
Вот у вас там формула площади как раз даст упомянутую Xaositect ориентированную, если модули снять. Сравните выражение $\mathbf u_x\mathbf v_y - \mathbf v_x\mathbf u_y$ ориентированной площади параллелограмма, натянутого на векторы $\mathbf u,\mathbf v$ с векторным произведением из трёхмерного пространства — это его полный аналог.

 
 
 
 Re: Проверка условия с "погрешностью"
Сообщение20.03.2018, 12:31 
Я написал короткую программу вычисляющую сумму ориентированных площадей двух треугольников, но эта программа неустойчива к вводу координат точек в другом порядке. То есть например если A(0, 0), B(0, 10), C(10, 10), D(10, 0) (вершины обходятся по часовой стрелке) то площадь будет найдена верно, а если A(10, 0), B(10, 10), C(0, 10), D(0, 0) (вершины обходятся против часовой) то площадь будет уже со знаком минус, если А(0, 0), B(0, 10), D(10, 0), C(10, 10) (самопересечение) то и вовсе равной нулю

 
 
 
 Re: Проверка условия с "погрешностью"
Сообщение20.03.2018, 20:09 
SpiderHulk в сообщении #1298504 писал(а):
если А(0, 0), B(0, 10), D(10, 0), C(10, 10) (самопересечение) то и вовсе равной нулю
Так это совершенно нормально. Вы ведь должны не какие попало пары вершин брать, а только инцидентные (соединённые ребром). Тогда для несамопересекающегося четырёхугольника всё будет как надо. А минус в самом конце можно убрать модулем (хотя если сделить за порядком обхода, можно организовать всё так, что он никогда не появится).

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group