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

Question

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

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

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

Answer 1

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

Кайла Шульца.

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

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

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

_{(источник: uga.edu )}

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

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

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

_{(источник: uga.edu )}

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

_{(источник: uga.edu )}

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

_{(источник: uga.edu )}

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

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

_{(источник: uga.edu )}

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

_{(источник: uga.edu )}

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

_{(источник: uga.edu )}

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

_{(источник: uga.edu )}

Answer 2

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

A = i + b/2 - 1

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

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

Поверхность также может быть рассчитана. Для формулы, которая вычисляет поверхность см. https://stackoverflow.com/a/14382692/2491535. Объединяя эти известные значения, я могу вычислить:

i = A + 1 - b/2

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

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

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

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

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

2. let ymin = floor (min (y1, y2, y3)) ymax = потолок (max (y1, y2, y3)) xmin = этаж (min (x1, x2, x3)) ymax = потолок ( макс (x1, x2,3))

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

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

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

Answer 6

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

Сначала назовите точку с наименьшей координатой 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 часов назад, но с использованием Брезенхэма вместо формулы наклона линии.

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

Answer 7

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

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

Answer 8

Вот реализация Python решения @ Прабхалы :

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

Answer 9

Я нашел довольно полезную ссылку, которая четко объясняет решение этой проблемы. Я слаб в координатной геометрии, поэтому я использовал это решение и закодировал его в 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);
 }

Answer 10

(странный) псевдокод для немного лучше, чем грубая сила (он должен иметь 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 (требуется только некоторое округление в части "for i ..", с особым случаем для p2.x, являющимся целым числом (там, округлено вниз = округлено вверх))
и есть некоторые возможности для оптимизации в реальной реализации