|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Chelmodeev 2:5062/17.5 03 Nov 2001 16:28:41
To : Yurij Zabelyshynskij
Subject : Maximal area rect
--------------------------------------------------------------------------------
02 Hоя 2001 Пт в 23:10 : Yurij Zabelyshynskij --> Андрей:
YZ> Я и говорю: идеальный случай, если строго, но мне достаточно близкого
YZ> к идеальному.
YZ> То же самое нужно мне: чтобы верилось в то, что не слишком маленький
YZ> прямоугольник не слишком вылазит. :) Возможно, есть какой-нибудь
YZ> алгоритм, основанный на вероятностях.
Hе знаю, как это проще реализовать, но вот такой "визуальный" алгоритм
придумался.
Многоугольник покрывается сеткой-растром (размер квадратной ячейки сетки
можно подобрать). Каждой клетке можно присвоить код в зависимости от заполнения
её точками многоугольника (0-пуста, 1-меньше половины, 2-больше половины,
4-полностью пересек.). Строится массив кодов клеток (здесь сразу выделен
прямоугольник, содержащий хотя бы одну "4" в каждой строке и столбце):
0 0 0 0 0 1 0 0
0 0 1 2 2 4 2 0
1 1 2 4 4 4 2 0
0 0 1 2 2 4 4 2
0 0 0 1 1 2 2 0
0 0 0 0 0 1 0 0
Дальше наверно понятно - есть несколько вариантов...
... http://ichip.chat.ru ... mailto:ichip(a)chat.ru
--- GoldED+/386 1.1.5-20010807 rev.0813 (MS-DOS 7.10 pc) * Chip&Deal *
* Origin: Мнoгие чинoвники cтaльнoму пеpу пoдoбны. (2:5062/17.5)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
