Изменения

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

Straight skeleton

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

Навигация