Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [С++]площадь пересечения многоугольников

Автор: Artemon 19.3.2008, 16:07

Как найти площадь пересечения 2-х многоугольников?

Площадь одного многоугольника нашел следущим способом:

Код


  double x[] = { 4, 4, 7, 7};
  double y[] = { 4, 6, 6, 4};
  const int count = sizeof( x ) / sizeof( x[0] );

   //int imin = min_element( &x[0], &x[count - 1] ) - &x[0], i = imin;
   int imin = 0, i = 0;

   double S = 0;

   do
   {
       int j = ( i + 1 ) % count;
       S += ( y[j] + y[i] ) * ( x[j] - x[i] ) / 2;
       i = j;
   } while ( i != imin );

Автор: ksili 21.3.2008, 10:07

По-моему надо искать точки пересечения многоугольников, потом по ним и вершинам разбивать площадь пересечения на треугольники и находить площадь пересечения как сумму площадей этих треугольников. Если многоугольники могут быть невыпуклыми, то алгоритм усложнится
Программу, разумеется, я сейчас писать не буду ))

Автор: ama_kid 21.3.2008, 11:06

Цитата(Artemon @ 19.3.2008, 16:07

)

Как найти площадь пересечения 2-х многоугольников?

Я думаю, сначала надо найти пересечение многоугольников, а затем найти площадь этого пересечения. Алгоритм первой задачи http://algolist.manual.ru/maths/geom/intersect/convex_intersect.php, а второй - http://algolist.manual.ru/maths/geom/polygon/area.php... В случае выпуклых исходных полигонов область пересечения - это один полигон. Для невыпуклых исходных полигонов пересечение может состоять из нескольких многоугольников. Тогда необходимо искать площадь каждого из них, а затем суммировать.
Ну и вот http://homepages.compuserve.de/chasluebeck/practic_info55.htm приведено какое-то решение на паскале, комментировать его качество не буду, нашёл банальным поиском...