Настройте точки внутри треугольника быстро

Ответ 1

В соответствии с вычислительной геометрией weenies самым быстрым способом сделать это является преобразование барицентрических координат. В случае, когда у вас есть фиксированный треугольник и множество контрольных точек, этот подход будет особенно быстрым, потому что, как только вы вычислили барицентрические координаты трех точек треугольника, вы выполнили большую часть работы. Вот полный алгоритм, где ABC - это треугольник, а P - тестируемая точка:

// Compute vectors        
v0 = C - A
v1 = B - A
v2 = P - A

// Compute dot products
dot00 = dot(v0, v0)
dot01 = dot(v0, v1)
dot02 = dot(v0, v2)
dot11 = dot(v1, v1)
dot12 = dot(v1, v2)

// Compute barycentric coordinates
invDenom = 1 / (dot00 * dot11 - dot01 * dot01)
u = (dot11 * dot02 - dot01 * dot12) * invDenom
v = (dot00 * dot12 - dot01 * dot02) * invDenom

// Check if point is in triangle
return (u >= 0) && (v >= 0) && (u + v < 1)

Здесь барицентрические координаты вычисляются относительно A, но B или C также работали бы.

Для проверки дополнительных точек вам нужно только пересчитать v2, dot02, dot12, u и v. Количества, такие как invDenom, остаются неизменными.

Ответ 2

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

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

Пример кода в C:

#include <stdio.h>

#define SCREEN_HEIGHT 22
#define SCREEN_WIDTH  78

// Simulated frame buffer
char Screen[SCREEN_HEIGHT][SCREEN_WIDTH];

void SetPixel(int x, int y, char color)
{
  if ((x < 0) || (x >= SCREEN_WIDTH) ||
      (y < 0) || (y >= SCREEN_HEIGHT))
    return;

  Screen[y][x] = color;
}

void Visualize(void)
{
  int x, y;

  for (y = 0; y < SCREEN_HEIGHT; y++)
  {
    for (x = 0; x < SCREEN_WIDTH; x++)
      printf("%c", Screen[y][x]);

    printf("\n");
  }
}

typedef struct
{
  int x, y;
} Point2D;

int main(void)
{
  // triangle vertices
  Point2D vx0 = { SCREEN_WIDTH / 2, SCREEN_HEIGHT / 7 };
  Point2D vx1 = { SCREEN_WIDTH * 6 / 7, SCREEN_HEIGHT * 2 / 3 };
  Point2D vx2 = { SCREEN_WIDTH / 7, SCREEN_HEIGHT * 6 / 7 };
  // vectors lying on triangle sides
  Point2D v0, v1, v2;
  // current point coordinates
  int x, y;

  // calculate side vectors

  v0.x = vx1.x - vx0.x;
  v0.y = vx1.y - vx0.y;

  v1.x = vx2.x - vx1.x;
  v1.y = vx2.y - vx1.y;

  v2.x = vx0.x - vx2.x;
  v2.y = vx0.y - vx2.y;

  // process all points

  for (y = 0; y < SCREEN_HEIGHT; y++)
    for (x = 0; x < SCREEN_WIDTH; x++)
    {
      int z1 = (x - vx0.x) * v0.y - (y - vx0.y) * v0.x;
      int z2 = (x - vx1.x) * v1.y - (y - vx1.y) * v1.x;
      int z3 = (x - vx2.x) * v2.y - (y - vx2.y) * v2.x;

      if ((z1 * z2 > 0) && (z1 * z3 > 0))
        SetPixel(x, y, '+'); // point is to the right (left) of all vectors
      else
        SetPixel(x, y, '-');
    }

  // draw triangle vertices

  SetPixel(vx0.x, vx0.y, '0');
  SetPixel(vx1.x, vx1.y, '1');
  SetPixel(vx2.x, vx2.y, '2');

  // visualize the result

  Visualize();

  return 0;
}

Выход (ideone):

------------------------------------------------------------------------------
------------------------------------------------------------------------------
------------------------------------------------------------------------------
---------------------------------------0--------------------------------------
--------------------------------------++++------------------------------------
------------------------------------++++++++----------------------------------
----------------------------------+++++++++++++-------------------------------
--------------------------------+++++++++++++++++-----------------------------
------------------------------++++++++++++++++++++++--------------------------
----------------------------++++++++++++++++++++++++++------------------------
--------------------------+++++++++++++++++++++++++++++++---------------------
-------------------------++++++++++++++++++++++++++++++++++-------------------
-----------------------+++++++++++++++++++++++++++++++++++++++----------------
---------------------+++++++++++++++++++++++++++++++++++++++++++--------------
-------------------+++++++++++++++++++++++++++++++++++++++++++++++1-----------
-----------------++++++++++++++++++++++++++++++++++++-------------------------
---------------++++++++++++++++++++++++---------------------------------------
-------------++++++++++++-----------------------------------------------------
-----------2------------------------------------------------------------------
------------------------------------------------------------------------------
------------------------------------------------------------------------------
------------------------------------------------------------------------------

Ответ 3

Простой предварительный фильтр - это устранение любых точек, координаты которых, очевидно, лежат вне границ треугольников. например.

  a
+
|\
| \ b
|c \
+---+  d

A и D, очевидно, снаружи. Координата Y намного выше максимума треугольника Y, а D, очевидно, находится за пределами максимума треугольника X.

Это оставляет B и C для тестирования.

Ответ 4

Вы также можете использовать quadtree, чтобы ускорить вычисление.

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

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

Ответ 5

Прежде всего сортируйте свои точки, указанные в списке по координатам y и по координатам y координат x. Теперь начните снизу с вашей младшей координаты y (подумайте о параллельной линии по оси x) и переместите ее на 1 единицу, вы также получите уравнение отрезков линий, образованных конечными точками вашего треугольника. Теперь устраните некоторые очевидные моменты, предложенные Марком Б. И для остальных точек, имеющих ту же самую координату y, что и ваша воображаемая параллельная линия оси x, движущаяся вверх на единичный шаг, каждый раз проверяйте, находятся ли они внутри или вне треугольника, в уравнениях линии, соединяющей конечные точки треугольника. Вы можете легко получить такие точки с одинаковыми координатами y, выполнив двоичный поиск в списке координат, который вы отсортировали ранее в соответствии с координатами y. Таким образом, ваш алгоритм принимает O (Yrangeoftriangle * nlogn) для каждого запроса. ТАКЖЕ Вопрос довольно хорошо задан в кодеке долго.