Рассчитать все дискретные точки плоскости

Question

I w sh, чтобы заполнить все точки на плоскости, определяемой тремя точками, таким образом:

• Координаты всех точек являются целыми числами, т. Е. Нет точек с десятичными координатами.
• Все точки на такой плоскости не находятся за пределами границ, образованных тремя точками, которые определяют указанную плоскость

Например, если задана плоскость P, определенная точками A (3, 0, 0) , B (0, 3, 0) и C (0, 0, 3) :

• точка D (1, 1, 1) удовлетворяет этому условию
• Точка E (6, 3, -6) не удовлетворяет этому условию, поскольку она включена плоскость, но за пределами границ
• Точка F (4, 1, 3) не удовлетворяет этому условию, поскольку она не находится на плоскости

I Я пытался применить алгоритм трехмерных линий Брезенхема и расширить его до рисования на плоскости, но я не могу понять это.

Answer 1

Сканировать заполняющий раствор:

Проецировать треугольник на XY и отсканировать заполнить его (рассмотрите все целочисленные ординаты Y между Ymin и Ymax и для каждого Y найдите Xmin и Xmax путем пересечения со сторонами, возьмите все промежуточные X).

Затем проверьте, является ли соответствующий Z целым числом (уравнение плоскости равно a.X + b.Y + c.Z + d = 0).

Объем работы пропорционален проецируемой области треугольника.

Вы можете немного ускорить процесс, заметив, что для постоянной Y вы используйте только решения диофантова уравнения a.X + c.Z = - d - b.Y. Это уравнение имеет решения, только если gcd(a, c) делит d + b.Y, и это ограничивает возможное Y.

---

В вашем случае плоскость равна X + Y + Z = 3, а спроецированный треугольник (0, 0), (3, 0), (0, 3).

Заполнение дает десять точек сетки, из которых три угла, шесть точек по краям и еще одна внутри. Для всех этих точек Z является целым числом. (Методы ускорения здесь не применяются.)

(0, 0, 3), (1, 0, 2), (2, 0, 1), (3, 0, 0), 
(0, 1, 2), (1, 1, 1), (2, 1, 0),
(0, 2, 1), (1, 2, 0), 
(0, 3, 0).

Answer 2

Сначала давайте найдем минимальные ZMin и максимальные ZMax значения z-координаты трех вершин, определяющих ваш трехмерный треугольник. Теперь представьте несколько плоскостей, параллельных плоскости xy и имеющих целое число z-координату в диапазоне ( ZMin , ZMax ). Каждая из этих плоскостей пересекается с вашим треугольником, давая отрезок прямой - найдите все конечные точки этих отрезков. Если предположить, что все координаты вершин треугольника являются целыми числами (согласно вашему примеру), то все эти отрезки будут иметь конечные точки с рациональными координатами.

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