Найти точку, где барицентрические веса имеют определенное значение

Ответ 1

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

Голубые линии показывают, как расширяются края треугольника, зеленые Xs являются точками на минимальных или максимальных строках. Только с двумя этими точками мы знаем наклон, если линия. Желтые линии показывают подключение выравнивания Xs к светло-серому.

Математика работает так: сначала получите значение расстояния между vb и vc: valueDistBtoC = vc - vb

Затем получим декартовое расстояние от b до c: cartesianDistBtoC = b.distance(c)

Затем получите значение расстояния от b до max: valueDistBtoMax = max - vb

Теперь мы можем пересечь размножение, чтобы получить декартовое расстояние от b до max: cartesianDistBtoMax = (valueDistBtoMax * cartesianDistBtoC)/valueDistBtoC

Сделайте то же самое для min, а также для a, b и c, a. 6 баллов достаточно, чтобы ограничить положение p.

Ответ 2

Считайте ваш треугольник фактически трехмерным треугольником с точками (ax,ay,va), (bx,by,vb) и (cx,cy,vc). Эти три точки определяют плоскость, содержащую все возможные триплеты p,vp, которые можно получить через барицентрическую интерполяцию.

Теперь подумайте о своих ограничениях как о двух других плоскостях, в z>=max и z<=min. Каждая из этих плоскостей пересекает вашу плоскость треугольника вдоль бесконечной линии; бесконечный луч между ними, проецируемый назад на плоскость ху, представляет собой область точек, которые удовлетворяют ограничениям. После того, как у вас есть линии (проецируемые вниз), вы можете просто найти, какая (если) нарушена определенной точкой, и переместить ее на это ограничение (вдоль вектора, перпендикулярного ограничению).

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

Ответ 3

Математически проблема - это просто изменение координат. Более сложная часть заключается в нахождении хорошей записи для соответствующих величин.

У вас есть две системы координат: (x, y) - декартовы координаты вашего дисплея и (v, w) - барицентрические координаты относительно векторов (ca), (ba), которые определяют другую (неортогональную).

Вам нужно найти уравнение двух линий в системе (x, y), тогда будет легко проецировать точку p на эти строки.

Для этого вы можете явно найти матрицу для перехода от координат (x, y) к координатам (v, w) и обратно. Функция, которую вы используете toBaryCoords, позволяет вычислить координаты (v, w) из (x, y), и мы можем повторно использовать эту функцию. Мы хотим найти коэффициенты преобразования из мировых координат (x, y) в барицентрические координаты (v, w). Он должен быть в форме

v = O_v + x_v * x + y_v * y

w = O_w + x_w * x + y_w * y

то есть.

(v, w) = (O_v, O_w) + (x_v, y_y) * (x, y)

и вы можете определить (O_v, O_w) путем вычисления toBaryCoord (0,0), затем найти (x_v, x_w), вычислив координаты (1,0) и найти (y_v, y_w) = toBaryCoord (1, 0) - (O_v, O_w), а затем найдите (y_v, y_w), вычислив (y_v, y_w) = toBaryCoord (0,1) - (O_v, O_w).

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

Значение вашей функции vp можно вычислить следующим образом. Я буду использовать f вместо v, потому что мы используем v для координаты барицентра. Следовательно, в следующем я имею в виду f (x, y) = vp, fa = va, fb = vb, fc = vc.

У вас есть:

f (v, w) = fa + (fb-fa) * v + (fc-fa) * w

то есть.

f (x, y) = fa + (fb-fa) (O_v + x_v * x + y_v * y) + (fc-fa) (O_w + x_w * x + y_w * y)

где (x, y) - координаты вашей точки p. Вы можете проверить справедливость этого уравнения, вставив координаты трех вершин a, b, c и убедитесь, что вы получили три значения fa, fb и fc. Помните, что координаты барицентра a равны (0,0), следовательно, O_v + x_v * a_x + y_v * a_y = 0 и т.д.... (a_x и a_y - координаты x, y точки a).

Если вы дадите

q = fa + (fb_fa) * O_v + (fc-fa) * O_w

fx = (fb-fa) * x_v + (fc-fa) * x_w

fy = (fb-fa) * y_v + (fc-fa) * y_w

вы получаете

f (x, y) = q + fx * x + fy * y

Обратите внимание, что q, fx и fy могут быть вычислены один раз из a, b, c, fa, fb, fc, и вы можете повторно использовать их, если вы меняете только координаты (x, y) точки p.

Теперь, если f (x, y) > max, вы можете легко проецировать (x, y) на линию, где max достигается. Координаты проекции:

(x ', y') = (x, y) - [(x, y) * (fx, fy) - max + q]/[(fx, fy) * (fx, fy)] (fx, fy)

Теперь. Вы хотите, чтобы имел код. Ну вот какой-то псевдокод:

toBarycoord(Vector2(0,0),a,b,c,O);
toBarycoord(Vector2(1,0),a,b,c,X);
toBarycoord(Vector2(0,1),a,b,c,Y);
X.sub(O); // X = X - O
Y.sub(O); // Y = Y - O

V = Vector2(fb-fa,fc-fa);

q =  fa + V.dot(O); // q = fa + V*O
N = Vector2(V.dot(X),V.dot(Y)); // N = (V*X,V*Y)

// p is the point to be considered

f = q + N.dot(p); // f = q + N*p

if (f > max) {
  Vector2 tmp;
  tmp.set(N);
  tmp.multiply((N.dot(p) - max + q)/(N.dot(N))); // scalar multiplication
  p.sub(tmp);
}

if (f < min) {
  Vector2 tmp;
  tmp.set(N);
  tmp.multiply((N.dot(p) - min + q)/(N.dot(N))); // scalar multiplication
  p.sum(tmp);
}

Ответ 4

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

Тогда вопрос заключается в том, чтобы найти градиент плоскости, который определяется тремя точками. Линии, где плоскость пересекается с плоскостями z = min и z = max, - это линии, на которые вы хотите ограничить свои точки.

Если вы нашли точку p, где v (p) > max или v (p) мин, нам нужно идти в направлении самого крутого наклона (градиент) до v(p + k * g) = max или мин соответственно. g - это направление градиента, а k - фактор, который нам нужно найти. Координаты, которые вы ищете (в декартовых координатах), являются соответствующими компонентами p + k * g.

Чтобы определить g, мы вычисляем ортонормированный вектор, перпендикулярный плоскости, который определяется тремя точками с использованием поперечного произведения:

// input:  px, py, pz, 
// output: p2x, p2y

// local variables
var v1x, v1y, v1z, v2x, v2y, v2z, nx, ny, nz, tp, k,

// two vectors pointing from b to a and c respectively
v1x = ax - bx;
v1y = ay - by;
v1z = az - bz;

v2x = cx - bx;
v2y = cy - by;
v2z = cz - bz;

// the cross poduct
nx = v2y * v1z - v2z * v1y;
ny = v2z * v1x - v2x * v1z;
nz = v2x * v1y - v2y * v1x;

// using the right triangle altitude theorem
// we can calculate the vector that is perpendicular to n
// in our triangle we are looking for q where p is nz, and h is sqrt(nx*nx+ny*ny)
// the theorem says p*q = h^2 so p = h^2 / q  - we use tp to disambiguate with the point p - we need to negate the value as it points into the opposite Z direction
tp = -(nx*nx + ny*ny) / nz;

// now our vector g = (nx, ny, tp) points into the direction of the steepest slope 
// and thus is perpendicular to the bounding lines

// given a point p (px, py, pz) we can now calculate the nearest point p2 (p2x, p2y, p2z) where min <= v(p2z) <= max

if (pz > max){
  // find k
  k = (max - pz) / tp;
  p2x = px + k * nx;
  p2y = py + k * ny;
  // proof: p2z = v = pz + k * tp = pz + ((max - pz) / tp) * tp = pz + max - pz = max
} else if (pz < min){
  // find k
  k = (min - pz) / tp;
  p2x = px + k * nx;
  p2y = py + k * ny;
} else {
  // already fits
  p2x = px;
  p2y = py;
}

Обратите внимание, что, очевидно, если треугольник вертикально ориентирован (в 2D он больше не является треугольником), nz обращается в нуль и tp не может быть вычислен. Это потому, что больше нет двух строк, где значение равно min или max соответственно. Для этого случая вам нужно будет выбрать другое значение на оставшейся строке или точке.