|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 01 Mar 2002 06:17:54
To : Uriy Iovkov
Subject : Re: ПЛОЩАДЬ ПЕРЕСЕЧЕHИЯ.
--------------------------------------------------------------------------------
До меня дошли слухи, что *28.02.02* *4:48:50* пролетало сообщение
от Uriy к *All* про *"ПЛОЩАДЬ ПЕРЕСЕЧЕHИЯ."*. И я решил вмешаться.
UI> ВОт в чем вопрос. Если узнать пересекаются ли два многоугольника еще могу
UI> решить проанализировав все ребра на пересечение(мож как побыстрее можно?)
UI> То вот как посчитать площать пересечения -ума не приложу. Точней оно
UI> конечно понятно: посчитать площадь обоих, потом посчитать пложадь
UI> получившейся в результате пересечения фигуры и разница будет площадью
UI> пересечения. Hо вот КАК ПОСЧИТАТЬ ПЛОЩАДЬ ПОЛУЧИВШЕЙСЯ ФИГУРЫ? Как вообще
UI> найти этот новый многоугольник?
Я могу присалать алгоритм находящий многоугольник явлюящийся пресечением
двух данных за O(mn), где m и n - количество вершин в этих многоугольниках.
Hо я сегодня узнал один новый метод, который может поможет решить эту задачу
за O(m+n), только вот я его (решение) еще пока не до конца придумал.
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Металл сила - всем рэперам могила. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
