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

My knee-jerk reaction would be to brute-force it:

• Find the maximum and minimum extent of the triangle in the x and y directions.
• Loop over all combinations of integer points within those extents.
• For each set of points, use one of the standard tests (Same side or Barycentric techniques, for example) to see if the point lies within the triangle. Since this sort of computation is a component of algorithms for detecting intersections between rays/line segments and triangles, you can also check this link for more info.

Хорошо, я предложу один алгоритм, он не будет блестящим, но он будет работать.

Во-первых, нам понадобится точка в тесте треугольника. Я предлагаю использовать «Барицентрическую технику», как объясняется в этом замечательном посте:

http://www.blackpawn.com/texts/pointinpoly/default.html

Теперь к алгоритму:

1. let (x1 , y1) (x2, y2) (x3, y3) - вершины треугольника

2. пусть ymin = floor (min (y1, y2, y3)) ymax = потолок (max (y1, y2, y3)) xmin = floor (min (x1, x2, x3)) ymax = потолок (max (x1, x2,3))

3. итерация от xmin до xmax и от ymin до ymax, вы можете перечислить все целые точки в прямоугольной области, содержащей треугольник

4. Используя тест точки в треугольнике, вы можете проверить каждую точку в перечислении, чтобы увидеть, находится ли она в треугольнике.

Это просто,

This is called the "Point in the Triangle" test.

Here is an article with several solutions to this problem: Point in the Triangle Test.

A common way to check if a point is in a triangle is to find the vectors connecting the point to each of the triangle's three vertices and sum the angles between those vectors. If the sum of the angles is 2*pi (360-degrees) then the point is inside the triangle, otherwise it is not.

Быстрый n'dirty псевдокод:

-- 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);
    }
  }
}

I only have half an answer for a non-brute-force method. If the vertices were integer, you could reduce it to figuring out how to find how many integer points the edges intersect. With that number and the area of the triangle (Heron's formula), you can use Pick's theorem to find the number of interior integer points.

Edit: for the other half, finding the integer points that intersect the edge, I suspect that it's the greatest common denominator between the x and y difference between the points minus one, or if the distance minus one if one of the x or y differences is zero.

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

Пусть 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

ура

Я бы сказал так:

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

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

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

Теперь вы подсчитали все точки «выше второй по высоте точки». ,

(wierd) псевдокод для алгоритма «бит лучше, чем грубая сила» (он должен иметь O (n))
Надеюсь, вы понимаете, что я имею в виду

n=0
p1,p2,p3 = order points by xcoordinate(p1,p2,p3)
for int i between p1.x and p2.x do
  a = (intersection point of the line p1-p2 and the line with x==i).y 
  b = (intersection point of the line p1-p3 and the line with x==i).y
  n += number of integers between floats (a, b)
end
for i between p2.x+1 and p3.x do
  a = (intersection point of the line p2-p3 and the line with x==i).y 
  b = (intersection point of the line p1-p3 and the line with x==i).y
  n += number of integers between floats (a, b)
end

, этот алгоритм довольно легко расширить для вершин типа float (требуется только некоторый раунд в части "для i ..", при этом особый случай, когда p2.x является целым числом (там, округлено вниз = округлено в большую сторону))
и есть некоторые возможности для оптимизации в реальной реализации

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

Сначала назовите точку с самой низкой координатой X "L", точку с самой высокой Координата X «R», а оставшаяся точка «M» (левая, правая и средняя).

Затем настройте два экземпляра линейного алгоритма Брезенхема. Параметризуйте один экземпляр для рисования от L до R, а второй - для рисования от L до M. Запустите алгоритмы одновременно для X = X [L] до X [M]. Но вместо того, чтобы рисовать какие-либо линии или включать какие-либо пиксели, подсчитайте пиксели между линиями.

После перехода от X [L] к X [M] измените параметры второго Брезенхэма, чтобы рисовать с M на R, затем продолжать запускать алгоритмы одновременно для X = X [M] - X [R].

Это очень похоже на решение, предложенное Эрвином Смаутом 7 часов назад, но используя Брезенхэм вместо формулы линейного наклона.

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