• Sandrick
  • Восстановленный участник
  • На форуме с 13 января 2006г.
  • Сообщений: 96
  • Спасибо: 0

Тема: Алгоритм обхода двумерного массива

Прошу прощения за оффтопик.
Задача такая: есть некий двумерный массив, размерностью (x,y).
Элемент массива - структура, содержащая координаты, прочие данные и флаг "присутствия". Подскажите пожалуйста каким образом мне оконтурить этот массив по внешним границам, т.е. граница - имеется ввиду "присутствующие" ячейки массива.
Заранее благодарен.

  • Откуда: Украина / Киев
  • На форуме с 15 апреля 2005г.
  • Сообщений: 8,666
  • Спасибо: 158

Re: Алгоритм обхода двумерного массива

> Sandrick
Не понял постановку задачи. Нужно найти выпуклый контур который проходит через внешние точки и содержит все остальные внутри? Тогда где-то так: http://algolist.manual.ru/maths/geom/misc/linkpoly.php

  • Откуда: Украина / Киев
  • На форуме с 15 апреля 2005г.
  • Сообщений: 8,666
  • Спасибо: 158

Re: Алгоритм обхода двумерного массива

Или: http://algolist.manual.ru/maths/geom/co … online.php

  • archimag
  • Восстановленный участник
  • На форуме с 24 ноября 2004г.
  • Сообщений: 156
  • Спасибо: 0

Re: Алгоритм обхода двумерного массива

> Sandrick
Если имеется в виду Convex hulls, то готовая реализация есть в cgal (http://www.cgal.org): http://www.cgal.org/Manual/3.2/doc_html … _main.html

  • Sandrick
  • Восстановленный участник
  • На форуме с 13 января 2006г.
  • Сообщений: 96
  • Спасибо: 0

Re: Алгоритм обхода двумерного массива

Большое спасибо!
Но тут не совсем Convex hulls...
Каждая ячейка массива состоит из 4-х координат, описывающих "ящик" и флага "присутствия". Многоугольник, который нужно в результате получить может быть выпуклым а может и нет.
Проще - в чертеже AutoCAD я генерю контейнерную (порт) площадку, а затем удаляю контейнеры под осветительные вышки и прочую лабуду, естественно, что вышки и пр не входят в общую площадь покрытия под контейнерной площадкой.

  • Откуда: Украина / Киев
  • На форуме с 15 апреля 2005г.
  • Сообщений: 8,666
  • Спасибо: 158

Re: Алгоритм обхода двумерного массива

> Sandrick
Так тебе контур нужен или площадь подсчитать? Если площадь, то контур не нужен вообще - просто суммируй площади "присутствующих" элементов. А если контур, то все намного сложнее. Хотя бы потому, что контуров может получится не один, если "отсутствующие" ячейки "рассекают" контур на части.

  • Sandrick
  • Восстановленный участник
  • На форуме с 13 января 2006г.
  • Сообщений: 96
  • Спасибо: 0

Re: Алгоритм обхода двумерного массива

> Александр Ривилис
Мне нужен контур - его необходимо графически отобразить. А исходя уже из построенного контура, берется площадь.