Polygon math

Question

Учитывая список точек, которые образуют простой 2d-многоугольник, ориентированный в 3d-пространстве, и нормальный для этого полигона, что является хорошим способом определить, какие точки являются конкретными «угловыми» точками?

Например, какой пункт находится в левом нижнем углу, или в правом нижнем углу, или в верхней точке? Многоугольник может быть ориентирован в любой 3d ориентации, поэтому я уверен, что мне нужно что-то сделать с нормальным, но у меня проблемы с правильной математикой.

Спасибо!

Answer 1

Вы ищете ограничительную коробку?

Я не уверен, что нормальное имеет какое-либо отношение к тому, что вы просите.

Чтобы получить ограничивающего параллелепипеда, держать 4 переменные: Minx, Maxx, MinY, MAXY

Затем цикл через все ваши очки, проверяя значения X против MaxX и шалунья, и ваши Y значений против MAXY и MinY , обновляя их по мере необходимости.

Когда цикл завершится, ваша коробка определяется как Minx, MinY в верхнем левом углу, шалунья, MAXY в верхнем правом углу, и так далее ...

Ответ на ваш комментарий:

Если вы хотите свою коробку после проекции, вам нужно получить «преобразованные» точки. Затем примените цикл ограничивающей рамки, как указано выше.

Преобразование обычно подразумевает координаты 2D-экрана после проекции (рендеринг сцены), но это также может означать двумерные точки на любой плоскости, на которую вы проецировали.

Answer 2

Проецируйте его на самолет и получите ограничительную коробку.

Answer 3

Возможный алгоритм будет

1. Найти нормальное, которые вы можете сделать, используя декартово произведение векторов, соединяющих две пары различных углов

2. Создать матрицу преобразования, чтобы повернуть полигон так что это строгальный станок в пространстве XY (т.е. нормальный, закрепленный вдоль оси Z)

3. Вычисление координат ограничительной рамки или любого другого определения углов, которые вы используете (поскольку многоугольник теперь выровнены в 2D-пространстве, это значительно более простая проблема).

4. Примените инверсию матрицы преобразования, используемой на шаге 2, чтобы преобразовать эти координаты обратно в 3D-пространство.

Answer 4

Для этого вам потребуется дополнительная информация. Множество (копланарных) точек и нормального недостаточно, чтобы дать вам понятие «нижний левый» или «верхний правый» или любая такая относительная идентификация.

Просмотр многоугольника в направлении нормального (так, что он выглядит как простая двумерная форма) является хорошим началом, но эта форма может быть повернута на любой произвольный угол.

1. Есть ли какая-либо другая информация в 3D-мире, которую вы можете использовать для получения ссылки на координатную систему?

2. Что вы пытаетесь достичь, зная крайние углы формы?

Answer 5

Я считаю, что ваш вопрос требует некоторой дополнительной информации, а именно системы координат, относительно которой любая точка может считаться «самой верхней» или «самой левой».

Не забывайте, что, пока нормальный говорит вам, в каком направлении находится многоугольник, он сам по себе не говорит вам, какой путь «вверх». Можно поворачивать (или «рулон») вокруг нормальный вектор и по-прежнему смотреть в том же направлении.

Именно поэтому в большинстве систем 3D-рендеринга есть камера, которая содержит не только вектор «вид», но и «вверх» и «правый» векторы. Изменения в последних двух достигают эффекта «качения» камеры вокруг вектора вида.

Answer 6

У меня есть глупая идея, но на риске получения отрицательной точки, я дам ему попробовать:

1. Получить минимальное/максимальное значение из каждой трехмерной оси каждого точка на вашем 2-м полигоне. Достаточно одного прохода с петлей/итератором над списком значений для каждой точки, просто заменяя минимальное и максимальное значения при прохождении. Конечным результатом является список, который имеет «самые низкие» координаты X, Y, Z и «самые высокие» координаты X, Y, Z.
2. Инициируйте этот список значений min/max значений для создания каждой точки («угол») «ограничивающей рамки» вокруг объекта. Результат должен быть полем, который всегда содержит объект независимо от оси проверенный или ориентированный (нет точки на , когда полигон будет когда-либо превышать максимальные или минимальные суммы ).
3. Затем получить расстояние каждого «2d многоугольник» указать на каждый угол местоположение на «ограничительной коробке»; меньше расстояния между точками, «ближе» к этому «углу».

Далеко не оптимальный, конечно, мутный, но, безусловно, быстрый. Вероятно, вы могли бы зафиксировать это во время вращения объекта, просто просмотрев min/max каждого повернутого значения x/y/z и сохраняя список этих значений загодя.

Answer 7

Если вы можете предположить, что есть некоторые ограничения в отношении фигур, то вы можете уйти с пониманием меньшей информации. Например, если ваша фигура была составом небольшого квадрата с длинным тонким треугольником с одной стороны (т. Е. Простой симметричной геометрией), то вы могли бы сравнить расстояние от каждой точки списка до «центра масс». Наибольшее расстояние определяло бы кончик конуса, второй по величине был бы двумя точками, наиболее удаленными от кончика конуса и т. Д. Если бы в списке был какой-то порядок, то, как и точки, введены против часовой стрелки (около нормальный), вы можете определить все точки. Это звучит немного вычислительно, поэтому было бы разумно попытаться включить дополнительную информацию с вашими фигурами, например, «центр масс» и контрольную точку, расположенную «вверх» над COM (но не по нормальному).Это даст вам «вверх» вектор, который вы можете пересечь с нормалью, чтобы определить некоторые координаты тела, например. Кроме того, нормаль может быть определена путем упорядочения списка точек. Если вы не можете принять что-либо о фигурах (или даже если фигуры были симметричными, например), тогда вам понадобится больше данных. Это зависит от ваших ограничений.

Answer 8

Если вы знаете, что многоугольник в 3D «плоский», вы можете использовать нормаль, чтобы преобразовать все 3D-точки вершин в 2D-представление (точек относительно плана, в котором расположен многоугольник) - но это все еще оставляет вам определение происхождения этой системы координат (но это не имеет особого значения для вашей проблемы) и с ориентацией хотя бы одной из осей (если вы хотите ортогональные оси, вы можете повернуть их вокруг вашего выбранного происхождения) - и здесь начинается проблема. Я бы рекомендовал использовать ось Y вашей 3D-системы координат, проецировать ее на ваш самолет и использовать результирующее направление как «вверх», но тогда у вас проблемы, если ваш план ортогонален оси Y (теперь вы можете использовать проецируемую Z-ось как «вверх»).

Математика довольно проста (вы можете использовать внутренний продукт (скалярное произведение) для проецирования на ваш самолет и некоторые элементы матрицы для преобразования в 2D-систему координат - вы можете получить все это путем поиска по алгоритмам raytracer для полигонов