алгоритм бы - Форум на исходниках

WWW.ИСХОДНИКИ.РУ cpp.sources.ru

java.sources.ru web.sources.ru soft.sources.ru

jdbc.sources.ru asp.sources.ru api.sources.ru

  Форум на исходниках
  C / C++ / Visual C++
  алгоритм бы
СПРОСИТЬ  ОТВЕТИТЬ
профайл | регистрация | faq

Автор Тема:   алгоритм бы

gecky опубликован 15-12-2001 18:02 MSK
Нужно решить задачу
Разбить многоугольник на треугольники.
У кого какие идеи? Поделитесь пожалуйста.
hacklite опубликован 15-12-2001 18:46 MSK
А он выпуклый?
hacklite опубликован 15-12-2001 19:39 MSK
Для выпуклого слишком очевидно. Для произвольного несамопересекающегося могу предложить:
Найти какую-нибудь диагональ, лежащую полностью внутри многоугольника. Это можно проверить, убедившись, что ее центр лежит внутри многоугольника и что она не пересекается ни с одной из его сторон.
Эта диагональ разобьет многоугольник на 2. К каждому из них применяем этот же алгоритм рекурсивно.
kuss опубликован 15-12-2001 21:35 MSK
найди точку внутри (пересечение двух диагоналей), а затем по циклу (колич точек) из центральной пускай лучи.
формулы надо, или сам посчитаешь?
x опубликован 16-12-2001 07:12 MSK
смотри триангуляция Делоне в любом поисковике
gecky опубликован 16-12-2001 18:35 MSK
уф. Порой задачки лёгкие на первый взгляд оказываются куда сложнее чем кажется. Неверите? - попробуйте!
Мног-к любой.
2hacklite -> не люблю рекурсию, отлаживать сложно.
Существует препод, который заставляет писать подобные програмки на маткаде. Предмет - компьютерная графика. Спрашивается кому это надо!?
kuss опубликован 17-12-2001 06:49 MSK
еще придумал!!!
берешь первую точку, и чертишь линии по циклу
for(int i=2;i<n-1;i++)
{
}
hacklite опубликован 17-12-2001 10:29 MSK
Если не любишь рекурсию, тогда в цикле. Диагональ проводи через вершины n и n+2 ("через одну"), тогда она отсечет треугольник. Треугольник сохраняешь в список треугольников, а вершину исключаешь. И так, пока многоугольник не кончится :)
Только надо диагональ не абы какую, а такую, чтобы отсеченный треугольник полностью лежал в многоугольнике <=> диагональ полностью лежит в многоугольнике. Интуитивно ясно, что всегда хоть одна такая найдется, хотя строго доказать не могу.
Sourcer опубликован 17-12-2001 10:54 MSK
Хороший вопрос!
Ну доустим с триугольникоми понятно.
А как узнать самую ближайшую точку к центру от которой вести линии?
Sourcer опубликован 17-12-2001 11:29 MSK
Добовление:
Если нужно вести паутину от центра.
mishootka опубликован 17-12-2001 11:47 MSK
Что есть центр? Для выпуклого многоугольника можешь взять геометрический центр всех вершин (центр тяжести). В случае произвольного сначала определись с понятием центра. Возможно, что достаточно будет вписать максимальный выпуклый многоугольник и взять его центр. А может быть хватит обрамляющего выпуклого и взятия его центра.
И совет: лезь на поисковики и ищи по ключам "разбиение многоугольника", "триангуляция" и т.п.
Sourcer опубликован 17-12-2001 00:58 MSK
Уже нашел :)
gecky опубликован 18-12-2001 19:03 MSK
hacklite, твой алгоритм работать не будет. Ещё надо проверить чтобы в отсекаемый треугольник не попала ни одна из других вершин (кроме трёх рассматриваемых в данный момент).
зы: kuss, твой тем более не будет работать. Нарисуй какой-нить мног-к посложнее (не выпуклый) и посмотри.
всем спасибо.
xKernel опубликован 19-12-2001 06:54 MSK
Соединять две вершины лежащие через одну если отрезок соединяющии их лежит внутри многоугольника (для выпуклых всегда лежит), если не лежит -- берёшь другую пару. Причем после каждого соединения ты будешь получать многоугольник с кол-вом вершин N-1.
x опубликован 19-12-2001 06:58 MSK
маньяки
алгоритмов триангуляции разработано много
и делали их люди явно круче вас
че вы колесо изобретаете?
michl_m опубликован 20-12-2001 11:49 MSK
Вопрос классический. Есть классический ответ.
Строится сетка с заданным шагом. Получаются
прямоугольники.
Последовательно проходим все прямоугольники,
для каждой из вершин определяем, находится
она внутри многоугольника или вне. Если
одна вершина стороны прямоугольника внутри, а другая снаружи, нужно найти точку пересечения данной стороны прямоугольника(т.е. отрезка) с многоугольником.
Затем триангулируем каждый прямоугольник.
Данный алгоритм для 3D называется "алгоритм плавающего кубика" (marching cubes algorithm). Посмотри на www.enlight.ru/faq3d/
Там есть 3D алгоритм, его легко применить к
2D.
hacklite опубликован 21-12-2001 10:35 MSK
gecky: "hacklite, твой алгоритм работать не будет. Ещё надо проверить чтобы в отсекаемый треугольник не попала ни одна из других вершин (кроме трёх рассматриваемых в данный момент)."
И что, можешь привести контрпример, в котором
1. В отсекаемый треугольник попала какая-то из вершин
2. Диагональ, которой отсекли многоугольник, полностью лежит в многоугольнике (или это условие ты пропустил мимо ушей? :)
?
aaa_ulstu опубликован 25-12-2001 10:28 MSK
Привет.
Задачка с виду не очень сложная...
Но на самом деле в ней масса подводных камней...
Приходилось сталкиваться с рядом алгоритмов, придуманных умными людьми (слова x), но при их реализации всплывает .... Но всё-таки получилось...
Можно посмотреть готовые программы для построения сеток. Есть даже куча нормальных и бесплатных(условно). Есть хорошие сайты по сеткопостроителям. Могу переслать страничку со ссылками, если нужно... тогды пиши на мыло!
СПРОСИТЬ  ОТВЕТИТЬ
Перейти:

E-mail | WWW.ИСХОДНИКИ.RU

Powered by: Ultimate Bulletin Board, Freeware Version 5.10a
Purchase our Licensed Version- which adds many more features!
© Infopop Corporation (formerly Madrona Park, Inc.), 1998 - 2000.

Автор	Тема: алгоритм бы
gecky	опубликован 15-12-2001 18:02 MSK Нужно решить задачу Разбить многоугольник на треугольники. У кого какие идеи? Поделитесь пожалуйста.
hacklite	опубликован 15-12-2001 18:46 MSK А он выпуклый?
hacklite	опубликован 15-12-2001 19:39 MSK Для выпуклого слишком очевидно. Для произвольного несамопересекающегося могу предложить: Найти какую-нибудь диагональ, лежащую полностью внутри многоугольника. Это можно проверить, убедившись, что ее центр лежит внутри многоугольника и что она не пересекается ни с одной из его сторон. Эта диагональ разобьет многоугольник на 2. К каждому из них применяем этот же алгоритм рекурсивно.
kuss	опубликован 15-12-2001 21:35 MSK найди точку внутри (пересечение двух диагоналей), а затем по циклу (колич точек) из центральной пускай лучи. формулы надо, или сам посчитаешь?
x	опубликован 16-12-2001 07:12 MSK смотри триангуляция Делоне в любом поисковике
gecky	опубликован 16-12-2001 18:35 MSK уф. Порой задачки лёгкие на первый взгляд оказываются куда сложнее чем кажется. Неверите? - попробуйте! Мног-к любой. 2hacklite -> не люблю рекурсию, отлаживать сложно. Существует препод, который заставляет писать подобные програмки на маткаде. Предмет - компьютерная графика. Спрашивается кому это надо!?
kuss	опубликован 17-12-2001 06:49 MSK еще придумал!!! берешь первую точку, и чертишь линии по циклу for(int i=2;i<n-1;i++) { }
hacklite	опубликован 17-12-2001 10:29 MSK Если не любишь рекурсию, тогда в цикле. Диагональ проводи через вершины n и n+2 ("через одну"), тогда она отсечет треугольник. Треугольник сохраняешь в список треугольников, а вершину исключаешь. И так, пока многоугольник не кончится :) Только надо диагональ не абы какую, а такую, чтобы отсеченный треугольник полностью лежал в многоугольнике <=> диагональ полностью лежит в многоугольнике. Интуитивно ясно, что всегда хоть одна такая найдется, хотя строго доказать не могу.
Sourcer	опубликован 17-12-2001 10:54 MSK Хороший вопрос! Ну доустим с триугольникоми понятно. А как узнать самую ближайшую точку к центру от которой вести линии?
Sourcer	опубликован 17-12-2001 11:29 MSK Добовление: Если нужно вести паутину от центра.
mishootka	опубликован 17-12-2001 11:47 MSK Что есть центр? Для выпуклого многоугольника можешь взять геометрический центр всех вершин (центр тяжести). В случае произвольного сначала определись с понятием центра. Возможно, что достаточно будет вписать максимальный выпуклый многоугольник и взять его центр. А может быть хватит обрамляющего выпуклого и взятия его центра. И совет: лезь на поисковики и ищи по ключам "разбиение многоугольника", "триангуляция" и т.п.
Sourcer	опубликован 17-12-2001 00:58 MSK Уже нашел :)
gecky	опубликован 18-12-2001 19:03 MSK hacklite, твой алгоритм работать не будет. Ещё надо проверить чтобы в отсекаемый треугольник не попала ни одна из других вершин (кроме трёх рассматриваемых в данный момент). зы: kuss, твой тем более не будет работать. Нарисуй какой-нить мног-к посложнее (не выпуклый) и посмотри. всем спасибо.
xKernel	опубликован 19-12-2001 06:54 MSK Соединять две вершины лежащие через одну если отрезок соединяющии их лежит внутри многоугольника (для выпуклых всегда лежит), если не лежит -- берёшь другую пару. Причем после каждого соединения ты будешь получать многоугольник с кол-вом вершин N-1.
x	опубликован 19-12-2001 06:58 MSK маньяки алгоритмов триангуляции разработано много и делали их люди явно круче вас че вы колесо изобретаете?
michl_m	опубликован 20-12-2001 11:49 MSK Вопрос классический. Есть классический ответ. Строится сетка с заданным шагом. Получаются прямоугольники. Последовательно проходим все прямоугольники, для каждой из вершин определяем, находится она внутри многоугольника или вне. Если одна вершина стороны прямоугольника внутри, а другая снаружи, нужно найти точку пересечения данной стороны прямоугольника(т.е. отрезка) с многоугольником. Затем триангулируем каждый прямоугольник. Данный алгоритм для 3D называется "алгоритм плавающего кубика" (marching cubes algorithm). Посмотри на www.enlight.ru/faq3d/ Там есть 3D алгоритм, его легко применить к 2D.
hacklite	опубликован 21-12-2001 10:35 MSK gecky: "hacklite, твой алгоритм работать не будет. Ещё надо проверить чтобы в отсекаемый треугольник не попала ни одна из других вершин (кроме трёх рассматриваемых в данный момент)." И что, можешь привести контрпример, в котором 1. В отсекаемый треугольник попала какая-то из вершин 2. Диагональ, которой отсекли многоугольник, полностью лежит в многоугольнике (или это условие ты пропустил мимо ушей? :) ?
aaa_ulstu	опубликован 25-12-2001 10:28 MSK Привет. Задачка с виду не очень сложная... Но на самом деле в ней масса подводных камней... Приходилось сталкиваться с рядом алгоритмов, придуманных умными людьми (слова x), но при их реализации всплывает .... Но всё-таки получилось... Можно посмотреть готовые программы для построения сеток. Есть даже куча нормальных и бесплатных(условно). Есть хорошие сайты по сеткопостроителям. Могу переслать страничку со ссылками, если нужно... тогды пиши на мыло!