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

Ответ 1

Предполагая, что вершины находятся в целочисленных координатах, вы можете получить ответ, построив прямоугольник вокруг треугольника, как объяснено в Kyle Schultz Исследование теоремы выбора.

Для j x k прямоугольника количество внутренних точек

I = (j – 1)(k – 1).

Для прямоугольника 5 x 3 ниже есть 8 внутренних точек.

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image008.jpg

Для треугольников с вертикальной ножкой (j) и горизонтальной ногой (k) количество внутренних точек определяется выражением

I = ((j – 1)(k – 1) - h) / 2

где h - количество точек внутри прямоугольника, совпадающих с гипотенузой треугольников (а не длины).

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image012.jpg

Для треугольников с вертикальной стороной или горизонтальной стороной число внутренних точек (I) определяется выражением

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Formula5.jpg

где j, k, h1, h2 и b отмечены на следующей диаграмме

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Triangle3.jpg

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

Число внутренних точек (I) в первом подзаборе дается выражением

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Formula7.jpg

где все переменные отмечены на следующей диаграмме

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/triangle5.jpg

Число внутренних точек (I) во втором подзаборе дается выражением

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image042.png

где все переменные отмечены на следующей диаграмме

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image038.png

Ответ 2

Теорема о выпуске (http://en.wikipedia.org/wiki/Pick%27s_theorem) гласит, что поверхность простого многоугольника, помещенного в целые точки, определяется следующим образом:

A = i + b/2 - 1

Здесь A - поверхность треугольника, я - количество внутренних точек, а b - количество граничных точек. Число граничных точек b можно легко вычислить, суммируя наибольший общий делитель наклонов каждой линии:

b =   gcd(abs(p0x - p1x), abs(p0y - p1y)) 
    + gcd(abs(p1x - p2x), abs(p1y - p2y)) 
    + gcd(abs(p2x - p0x), abs(p2y - p0y))

Поверхность также может быть рассчитана. Для формулы, которая вычисляет поверхность, см. fooobar.com/questions/32708/.... Объединение этих известных значений я можно вычислить по формуле:

i = A + 1 - b/2

Ответ 3

Моя реакция на коленный рефлекс была бы грубой силой:

• Найти максимальную и минимальную степень треугольника в направлениях x и y.
• Перебирать все комбинации целых точек в пределах этих экстентов.
• Для каждого набора точек используйте один из стандартных тестов (Same side или Barycentric methods, например), чтобы увидеть, лежит внутри треугольника. Поскольку этот вид вычислений является компонентом алгоритмов для обнаружения пересечений между лучами/отрезками и треугольниками, вы можете также проверить эту ссылку для получения дополнительной информации.

Ответ 4

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

Сначала нам понадобится точка в треугольном тесте. Я предлагаю использовать "Barycentric Technique", как объясняется в этом превосходном посте:

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

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

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

• Пусть ymin = пол (min (y1, y2, y3)) ymax = потолок (max (y1, y2, y3)) xmin = пол (min (x1, x2, x3)) ymax = макс (x1, x2,3))

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

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

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

Ответ 5

Это называется тестом "Точка в треугольнике".

Вот статья с несколькими решениями этой проблемы: Точка в тестовом треугольнике.

Общим способом проверить, находится ли точка в треугольнике, является найти векторы, соединяющие точку с каждой из трех треугольников треугольника и суммировать углы между этими векторы. Если сумма углов 2 * pi (360 градусов), то точка внутри треугольника, в противном случае это не так.

Ответ 6

У меня есть только половина ответа для метода без грубой силы. Если вершины были целыми, вы могли бы уменьшить его, чтобы выяснить, как найти, сколько целых точек пересекают ребра. С этим числом и площадью треугольника (формулой Херона) вы можете использовать теорему Пика, чтобы найти количество внутренних целых точек.

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

Ответ 7

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

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

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

После перехода из X [L] в X [M], измените параметры второго Bresenham на рисование из M в R, затем продолжайте выполнение алгоритмов одновременно для X = X [M] до X [R].

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

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

Ответ 8

Быстрый 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);
    }
  }
}

Ответ 9

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

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

веселит

Ответ 10

Я бы сказал:

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

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

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

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

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

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

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

(Я сделал домашнее задание для вас?)

Ответ 11

(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 является целым числом (там округлено вниз = округлено вверх))
и есть некоторые возможности для оптимизации в реальной реализации

Ответ 12

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

http://mathforum.org/library/drmath/view/55169.html

public int points(int[][] vertices){
      int interiorPoints = 0;
      double triangleArea = 0;
      int x1 = vertices[0][0], x2 = vertices[1][0], x3 = vertices[2][0];
      int y1 = vertices[0][1], y2 = vertices[1][1], y3 = vertices[2][1];

      triangleArea = Math.abs(((x1-x2)*(y1+y2))                             
                + ((x2-x3)*(y2+y3))
                + ((x3-x1)*(y3+y1)));

      triangleArea /=2;
      triangleArea++;

      interiorPoints = Math.abs(gcd(x1-x2,y1-y2))
                + Math.abs(gcd(x2-x3, y2-y3))
                + Math.abs(gcd(x3-x1, y3-y1));

      interiorPoints /=2;

      return  (int)(triangleArea - interiorPoints);
 }

Ответ 13

Вот реализация Python решения @Prabhala:

from collections import namedtuple
from fractions import gcd


def get_points(vertices):
    Point = namedtuple('Point', 'x,y')
    vertices = [Point(x, y) for x, y in vertices]

    a, b, c = vertices

    triangle_area = abs((a.x - b.x) * (a.y + b.y) + (b.x - c.x) * (b.y + c.y) + (c.x - a.x) * (c.y + a.y))
    triangle_area /= 2
    triangle_area += 1

    interior = abs(gcd(a.x - b.x, a.y - b.y)) + abs(gcd(b.x - c.x, b.y - c.y)) + abs(gcd(c.x - a.x, c.y - a.y))
    interior /= 2

    return triangle_area - interior

Использование:

print(get_points([(-1, -1), (1, 0), (0, 1)]))  # 1
print(get_points([[2, 3], [6, 9], [10, 160]]))  # 289