ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alex Cvetkov                         2:5030/1334    30 May 2001  12:40:56
 To : Anatoly Saveliev
 Subject : Определение площади фигуры
 -------------------------------------------------------------------------------- 
 

 
 29 May 01 17:13, Anatoly Saveliev писал(ла) All:
 
  AS> 1. Берем для каждого круга охватывающий прямоугольник (точнее квадрат)
  AS> 2. Сортируем квадраты лексикографически по лувому нижнему углу (если
  AS> круги разбросаны равномерно, при 5000 объектов достаточно сортировки
  AS> по X) 3. Для каждого круга находим сначала потенциальных
  AS> "пересеченцев" (по квадратам, сначала дихотомический поиск первого,
  AS> потом просмотр списка, пока не вылезем за границу своего квадрата),
  AS> затем реальных. Сохраняем факт пересечения и его площадь в списке. 4.
  AS> Рассматривая список как ребра графа, определяем его компоненты
  AS> связности (алгоритм есть в Кнуте и Ахо, Ульмане). 5. Идем по
  AS> компоненте связности, складывая площади кругов и вычитая пересечения.
 
 А как этот алгоритм учитывает тройное пересечение (когда пересекаються сразу три
 круга)?
 
                                            Alex Cvetkov
 
 ---
  * Origin: Life suxx (2:5030/1334)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Определение площади фигуры   Anatoly Saveliev   29 May 2001 17:13:38   Определение площади фигуры   Alex Cvetkov   30 May 2001 12:40:56   Определение площади фигуры   Alexei Frounze   31 May 2001 09:23:23   Определение площади фигуры   Fyodor Korzhov   01 Jun 2001 00:36:05   Определение площади фигуры   Dan Raskovalov   31 May 2001 13:58:13   Определение площади фигуры   Alex Cvetkov   03 Jun 2001 01:09:32   Определение площади фигуры   Dan Raskovalov   04 Jun 2001 04:11:14