?

Log in

алгоритмическая ссылка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

алгоритмическая ссылка [мар. 8, 2008|11:03 am]
Anatoly Vorobey


Мне очень понравилась статья об алгоритме Форчуна (англ.) для вычислений диаграммы Вороного (если вы не знаете, что это такое, то по ссылке подробно объясняется). Написано ясным языком, и содержит несколько полезных демонстраций.
СсылкаОтветить

Comments:
[User Picture]From: katyat
2008-03-08 09:19 am
Spasibo, ne znala.
(Ответить) (Thread)
(Удалённый комментарий)
From: (Anonymous)
2008-03-08 11:13 am
Триангуляции названы именем Делоне.

"содержит несколько полезных демонстраций" - по-русски так не говорят.
(Ответить) (Parent) (Thread)
From: 9000
2008-03-08 03:35 pm
уже говорят %)
(Ответить) (Parent) (Thread)
From: (Anonymous)
2008-03-08 04:08 pm
не может быть. разве что это очень узкий жаргонизм.
априори неясно, что имеется в виду, сначала я подумал, что в тексте по ссылке будет мультик, иллюстрирующий работу алгоритма или чего-то еще
еще была версия, что это калька с французского, и имеется в виду "доказательство"
апостериори тоже не вполне ясно, видимо имелся в виду "пример"
(Ответить) (Parent) (Thread)
From: ro-che.info
2008-03-09 11:23 am
Все верно, имелись в виду Java-апплеты, которые демонстрируют работу алгоритма. Управляемый мультик.
(Ответить) (Parent) (Thread)
[User Picture]From: bakhtin
2008-03-08 04:22 pm
Мне больше нравится такой алгоритм, годящийся в евклидовом ространстве любой размерности (здесь описываю для плоскости):

Дан набор точек на плоскости {(x,y)}.
1) Помещаем плоскость в 3-мерное пространство, добавляя ещё одну координату z.
2) На нашу плоскость {(x,y,z): z=0} ставим параболоид вращения {(x,y,z): z=x^2+y^2} и для каждой точки из набора проецируем её на параболоид (x и y даны, по ним вычисляем z).
3) В пространстве находим выпуклую оболочку получившегося набора на параболоиде. Её граница в случае общего положения состоит из треугольников с вершинами из получившегося набора (для многомерной ситуации будут симплексы). Проецируя те из этих треугольников, внешняя нормаль к которым направлена вниз, обратно на плоскость, получим триангуляцию Делоне, двойственную структуре Вороного.

Конечно, остаются вопросы: как искать выпуклые оболочки, что делать в случаях необщего положения.

См. http://www.qhull.org/
(Ответить) (Thread)
[User Picture]From: spamsink
2008-03-08 05:56 pm
http://www.mailcom.com/ioccc/boutines/boutines.c видел уже, наверное?
(Ответить) (Thread)
From: ro-che.info
2008-03-09 11:28 am
Спасибо за наводку, действительно красиво и интересно.
Я даже подумываю о том, чтобы прочесть лекцию по мотивам этой статьи в своем лицее. Можно будет приурочить к 140-летию Вороного.
(Ответить) (Thread)
From: opegs
2008-03-16 10:56 pm
Nice. Thanx!
(Ответить) (Thread)
From: (Anonymous)
2008-03-20 07:31 am

Ahhh! Voronoi!

I was trying to take a break, but here it is again! (спасибо).
(Ответить) (Thread)
[User Picture]From: keturah
2008-03-20 07:31 am

Ahhh! Voronoi!

I was trying to take a break, but here it is again! (спасибо).
(Ответить) (Thread)