Сколько целых точек в трех точках, образующих треугольник?

Question

На самом деле это классическая проблема, как выразился пользователь SO Victor (в другом вопросе SO о том, какие задачи задавать во время интервью).

Я не мог сделать это за час (вздох), так каков алгоритм, который вычисляет количество целых точек в треугольнике?

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

Answer 1

Я бы пошел так:

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

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

Остановитесь, когда ваши убывающие координаты Y достигнут второй по высоте точки треугольника.

Теперь вы посчитали все точки «выше второй по величине точки», и теперь у вас осталась проблема «подсчета всех точек в каком-то (гораздо меньшем !!!) треугольнике, из которого вы знаете, что его верхний боковые параллели оси X.

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

После этого у вас остается проблема подсчета всех целых точек в треугольнике, еще раз значительно меньшем, из которого вы знаете, что его верхняя сторона параллельна оси X, а его левая сторона параллельна Y- ось.

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

(Я уже сделал для тебя домашнее задание?)

Answer 2

У меня есть идея -

Пусть A (x1, y1), B (x2, y2) и C (x3, y3) - вершины треугольника. Пусть 'count' будет числом целых точек, образующих треугольник.

Если нам нужны точки на краях треугольника, то по формуле евклидова расстояния http://en.wikipedia.org/wiki/Euclidean_distance, можно определить длину всех трех сторон. Сумма длины всех трех сторон - 3, даст этот счет.

Чтобы найти количество точек внутри треугольника, нам нужно использовать алгоритм заполнения треугольника и вместо фактического рендеринга, т. Е. Выполнения drawpixel (x, y), просто пройти через циклы и обновлять счет, пока мы выполняем цикл , Алгоритм заполнения треугольника от

Основы компьютерной графики Питер Ширли, Михаил Ашихмин

должно помочь. Это указано здесь http://www.gidforums.com/t-20838.html

ура

Answer 3

Быстрый и грязный псевдокод:

-- Declare triangle
p1 2DPoint = (x1, y1);
p2 2DPoint = (x2, y2);
p3 2DPoint = (x3, y3);
triangle [2DPoint] := [p1, p2, p3];

-- Bounding box
xmin float = min(triangle[][0]);
xmax float = max(triangle[][0]);
ymin float = min(triangle[][1]);
ymax float = max(triangle[][1]);

result [[float]];

-- Points in bounding box might be inside the triangle
for x in xmin .. xmax {
  for y in ymin .. ymax {
    if a line starting in (x, y) and going in any direction crosses one, and only one, of the lines between the points in the triangle, or hits exactly one of the corners of the triangle {
      result[result.count] = (x, y);
    }
  }
}