Получение списка местоположений в треугольнике в виде позиций x, y

Question

Допустим, у меня есть треугольник, заданный тремя целочисленными вершинами (x1, y1), (x2, y2) и (x3, y3).Какой тип алгоритма я могу использовать, чтобы получить полный список ВСЕХ (x, y) целочисленных пар, которые лежат внутри треугольника.

Answer 1

Правильное название этой проблемы - треугольник растеризация .

Это хорошо изученная проблема, и есть множество способов сделать это. Два популярных метода:

1. Сканирование строки по строке сканирования

   Для каждой строки сканирования вам требуется некоторая базовая геометрия для пересчета начало и конец строки. См. Алгоритм рисования линий Брезенхэма .

2. Проверьте каждый пиксель в ограничительной рамке, чтобы увидеть, находится ли он в треугольник.

   Обычно это делается с помощью барицентрических координат.

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

Оригинальная статья для точного описания того, как использовать метод 2), написана Хуаном Пинедой в 1988 году и называется «Параллельный алгоритм растеризации полигонов».

Для треугольников это концептуально очень просто (если вы изучаете барицентрические координаты). Если вы преобразуете каждый пиксель в треугольные барицентрические координаты, альфа, бета и гамма - тогда простой тест состоит в том, что альфа, бета и гамма должны быть между 0 и 1.

Answer 2

Должен подойти следующий алгоритм:

1. Сортировать вершины треугольника по координате x в порядке возрастания.Теперь у нас есть два сегмента (1-2 и 2-3) с одной стороны (сверху или снизу) и один сегмент с другой (1-3).

2. ВычислитьКоэффициенты уравнений прямых (которые содержат отрезки):

   A * x + B * y + C = 0
   A = y2 - y1
   B = x1 - x2
   C = x2 * y1 - x1 * y2
   

   Там (x1, y1) и (x2, y2) две точки линии.

3. Для каждого из диапазонов [x1, x2), (x2, x3] и x2 (особый случай) переберите целые точки в диапазонах и выполните следующие действия для каждого x:

   1. Найти верхнюю границуas y_top = (- A1 * x - C1) div B1.
   2. Найти нижнюю границу как y_bottom = (- A2 * y - C2 - 1) div B2 + 1.
   3. Добавить все точкимежду (x, y_bottom) и (x, y_top) к результату.

Этот алгоритм предназначен для не строго внутренних вершин. Для строго внутренних вершин элементы 3.1 и 3.2 немного отличаются.

Answer 3

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

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

Затем для каждой пары кандидатов (x, y) решите в a, b, c систему

a + b + c = 1
a x1 + b x2 + c x3 = x
a y2 + b y2 + c y3 = y

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

Answer 4

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