Посещение точек в треугольнике в случайном порядке

Question

Для прямоугольного треугольника, заданного уравнением aX + bY <= c на целых числах </p>

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

Я знаю, как это сделать с отрезком от 0 до x

выберите случайную точку 'o' вдоль линии,
выберите 'p', который относительно прост к x
повторить до x раз: O _{следующий} = (O _cur + P) MOD x

Чтобы сделать это для треугольника, я бы
1. Нужно посчитать количество пикселей в списках без треугольника
2. Отобразите целое число 0..пунктов в пару x, y, которая является допустимым пикселем внутри треугольника

Я надеюсь, что любое решение может быть обобщено на пирамиды и формы более высоких размеров.

(*) Я использую термин пиксель CG для пары целых точек X, Y, так что уравнение удовлетворяется.

Answer 1

Поскольку вы хотите гарантировать посещение каждого пикселя один раз и только один раз, вероятно, лучше думать с точки зрения пикселей, а не реальных треугольников. Вы можете разрезать треугольники по горизонтали и получить группу горизонтальных линий сканирования . Соедините линии сканирования, и вы превратили свой «треугольник» в длинную линию. Примените свой алгоритм посещения точек к длинной цепочке линий сканирования.

Кстати, это отображение должно происходить только на бумаге, все, что вам нужно, - это функция, которая может возвращать (x, y) заданный (t) вдоль линии виртуального сканирования.

Edit: Чтобы преобразовать две точки в отрезок, вы можете найти преобразование сканирования Брезенхэма . Как только вы преобразуете 3 линейных сегмента в серию точек, вы можете поместить все точки в корзину и сгруппировать все точки по y. В пределах того же значения y сортируйте точки по x. Наименьшее значение x в значении y является начальной точкой строки сканирования, а наибольшее значение x в значении y является конечной точкой строки сканирования. Это называется "сканирующий конвертирующий треугольник". Вы можете найти больше информации, если вы Google.

Answer 2

Вот решение для Выбор треугольника .

Что вам нужно сделать, это выбрать два вектора (стороны) вашего треугольника, умножить каждый случайное число в [0,1] и сложить их. Это обеспечит равномерное распределение в четырехугольнике, определяемом векторами. Вам нужно проверить, лежит ли результат внутри исходного треугольника; если он не преобразует его обратно или просто отбрасывает и пытается снова.

Answer 3

Я бы рассмотрел линии треугольника как одну линию, которая разрезана на сегменты. Сегменты будут храниться в массиве, где также хранится длина сегмента и смещение в общей длине линий. Затем, в зависимости от значения O, вы можете выбрать, какой элемент массива содержит пиксель, который вы хотите нарисовать в данный момент, на основе этой информации и раскрасить пиксель на основе значений в элементе.

Answer 4

Вот метод, который тратит некоторое время процессора, но, вероятно, не тратит так много, как более сложный метод.

Вычислить прямоугольник, который описывает треугольник. Будет легко «линеаризовать» этот прямоугольник, за каждой строкой сканирования следует следующая. Используйте алгоритм, который вы уже знаете, чтобы пройти пиксели прямоугольника. Когда вы нажимаете каждый пиксель, проверьте, находится ли пиксель в треугольнике, а если нет, пропустите его.

Answer 5

Один из методов состоит в том, чтобы поместить все пиксели в массив и затем перетасовать массив (это O (n)), а затем посетить пиксели в порядке в перетасованном массиве. Для этого может потребоваться довольно много памяти.