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

28

На самом деле это классическая проблема для пользователя SOВиктор положить его (в другой ТАКвопрос относительно того, какие задачи задавать во время собеседования).

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

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

Можете ли вы дать ссылку на другой вопрос, пожалуйста teabot
@Chet: предположительно включительно. Ваш вопрос имеет смысл, только если вокруг треугольника имеется граница определенной ширины. В этом случае это строка без ширины, поэтому она всегда будет включающей. Теперь, если на нем есть граница с любой шириной, тогда этот вопрос остается в силе. Eric
Я не понимаю вопроса, можете ли вы предоставить немного больше деталей? samoz
@samoz: например, учитывая треугольник с вершинами (0,0), (0,3), (3,0), найдите целочисленные координаты в пределах - (т.е. 1,1) является одним из них jimyi
Как насчет точек на одном из краев? Являются ли края эксклюзивными или инклюзивными? Chet

Ваш Ответ

13   ответов
11

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.
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
0

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

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

alt text

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

Error: User Rate Limit Exceeded
0

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

n=0
p1,p2,p3 = order points by xcoordinate(p1,p2,p3)
for int i between p1..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, являющимся целым числом (там, округлено вниз = округлено вверх))
и есть некоторые возможности для оптимизации в реальной реализации

0

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

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

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

Fundamentals of Computer Graphics by Peter Shirley,Michael Ashikhmin

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

ура

1

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

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

13

Теорема Пика (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
0

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

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

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

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

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

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

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

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

(Я уже сделал твою домашнюю работу для тебя?)

Error: User Rate Limit Exceeded tzup
36

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

Для J X Krectangle, количество внутренних точек

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

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

альтернативный текст http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image008.jpg

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

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

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

альтернативный текст http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image012.jpg

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

альтернативный текст http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Formula5.jpg

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

альтернативный текст http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Triangle3.jpg

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

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

альтернативный текст http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Formula7.jpg

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

альтернативный текст http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/triangle5.jpg

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

альтернативный текст http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image042.png

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

альтернативный текст http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image038.png

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededour trianglesError: User Rate Limit ExceededShoelace FormulaError: User Rate Limit ExceededI= A - B/2 +1
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
1

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

Сначала назовите точку с наименьшей координатой 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. Но к тому времени, когда это произойдет, ваш интервьюер будет в восторге, и вы сможете перейти к следующему вопросу.

0

Решение Прабхалы:

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
5

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

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

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

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

let (x1,y1) (x2,y2) (x3,y3) be the triangle vertices

let ymin = floor(min(y1,y2,y3)) ymax = ceiling(max(y1,y2,y3)) xmin = floor(min(x1,x2,x3)) ymax = ceiling(max(x1,x2,3))

iterating from xmin to xmax and ymin to ymax you can enumerate all the integer points in the rectangular region that contains the triangle

using the point in triangle test you can test for each point in the enumeration to see if it's on the triangle.

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

Похожие вопросы