[Линетт]

Ох, это будет просто чудом, если кто-то откликнется.

Может, кто-то решал задачу об оптимальной триангуляции многоугольника (динамическое программирование)?
Остался ли у вас код? А может, вы ещё и очень добрые и покажете мне этот код? ) Или, если жалко и не хочется, подскажете как можно более подробный алгоритм с учётом визуализации?

P.s. Если что - я не фанат выдавания чужой работы за свою.

@темы: Вопрос, Delphi, Алгоритм

Comments

[Ri]

Многоугольник выпуклый или произвольный?
Что вы имеете в виду под "с учетом визуализации"?

[Линетт]

Ri, вообще, есть три варианта для моей работы.)
Первый - многоугольник выпуклый, без всяких точек внутри. То есть просто голый многоугольник. Эту триангуляцию я написала.
Второй - многоугольник произвольный, но тоже без внутренних точек (тут сложности, так как в первом случае у меня так построено, что можно натыкать тучу точек, потом программа сама отберет самые крайние точки и построит по ним выпуклый многоугольник, здесь же, скорее всего, нужно будет тыкать точки последовательно и сразу строить многоугольник - это не проблема, проблема с самой триангуляцией ._. )
Но мне нужен и третий вариант - просто дано очень много точек, выпуклый многоугольник с внутренними точками, которые тоже нужно все между собой соединить. Я начала делать методом "Разделяй и властвуй", осилила только самую начальную часть алгоритма - для 3-4 точек разбиение, проблемы с разбиением первоначальных точек на подзадачи, то есть разбиение вертикальными и горизонтальными прямыми на участки по 3-4 точки и соединение потом этих подмногоугольников в один общий. Если теоретическую часть ещё можно понять, если посидеть и повтыкать, то с визуализацией этого у меня проблемы -.- Я пару часов убила на то, чтобы написать процедуру, проверящую, не пересекает ли рисуемая прямая какую-то из уже имеющихся прямых ._.