| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Алгоритм] построение многоугольников в пространстве |
| Автор: maximusrus 2.12.2008, 20:41 |
| Здравствуйте участники форума! Обращаюсь к вам с огромной просьбой, потому что больше не к кому. Короче требуется ваша помощь! Задача: Даны m точек в пространстве, определить, можно-ли выбрать такие n-точек, которые являются вершинами правильного многоугольника. Если Да, то выбрать многоугольник максимальной площади. Точки задаются произвольно. Времени в обрез. Вопрос жизни и смерти. Прошу помощи. Всем заранее спасибо. |
| Автор: maxdiver 2.12.2008, 21:25 |
| Ну перебором это легко замутить. Переберём, какие n точек среди этих m выбираем, и проверяем, что они лежат в одной плоскости. Для этого достаточно проверить, что для любой четвёрки точек среди выбранных n выполняется, что объём тетраэдра, построенного на них, равен нулю - это делается подсчётом определителя, составленного из координат этих четырёх точек. Далее, вроде как, можно сделать так. Найдём центр этого многоугольника как среднее арифметическое координат его вершин. Тогда, утверждается, что многоугольник будет правильным тогда и только тогда, когда все вершины равноудалены от центра, а все расстояния между соседними вершинами равны между собой (для каждой вершины найдём две ближайшие к ней - это и есть её соседи, если мы надеемся, что многоугольник выпуклый правильный). Вроде так. |
| Автор: maximusrus 2.12.2008, 21:47 |
| я в математике не очень силён, но помоему многоугольник в пространстве это многогранник? поправте меня если это не так. |
| Автор: HumanAPI 3.12.2008, 00:11 |
| Ну если m >= 3 то правильный многоугольник построить можно в любом случаи. Что бы построить многоугольник максимальной площади нужно знать в каком пространстве мы работаем в 2D или 3D. |
| Автор: maximusrus 3.12.2008, 00:26 |
| в 3D пространстве. Насчёт алгоритма ни у кого ничё нету, нужен какой нибудь примерчик для толчка и точки опоры. Плиз! |
| Автор: HumanAPI 3.12.2008, 18:55 |
| Ну если под понятием правильный многоугольник подразумевается выпуклый многоугольник то это не сложно, а если подразумевается с равными углами и сторонами то я не представляю как это сделать. (с интересом бы взглянул на такой алгоритм) |
| Автор: maximusrus 3.12.2008, 19:53 |
| я сам с удовольствием посмотрел бы... |