Изменения

Перейти к: навигация, поиск

Straight skeleton

2 байта добавлено, 18:28, 5 декабря 2014
м
Множественные события в одной точке
===== Множественные события в одной точке =====
Первая проблема, возникающая в этом случае {{---}} точное определение того, что несколько событий произошли в одной точке. Для определения совпадения нескольких событий в одной точке можно поступать приближённо: вводить с каждой точкой <tex>\varepsilon</tex>-окрестность и смотреть, не попали ли другие точки в эту окрестность, или использовать более точную арифметику<ref>[http://www.mpfr.org/ The GNU MPFR Library]</ref>. В данном случае недостаточно использовать [[Интервальная арифметика | интервальную арифметику]] или даже рациональную арифметику. Потому что даже если координаты точек задаются абсолютно точно, то для посчёта подсчёта радиуса вписанной окружности необходимо уметь извлекать корни (напомним, что радиус вписанной окружности равен площади, поделённой на полупериметр, а длины сторон треугольников {{---}} корни из [[Гильбертовы пространства | скалярного произведения]] векторов разницы точек на самих себя).
Чтобы научиться разбираться с такими случаями в алгоритме, когда мы уже поняли, что в одной точке будет несколько событий, введём понятие '''обобщённого события пересечения''' (англ. ''GIE'', ''generalized intersection event'').

Навигация