Определите, имеет ли треугольник левую сторону

Question

Если у вас есть набор из трех вершин в (x1, y1), (x2, y2) и (x3, y3), как бы вы определили, будет ли треугольник, определенный этими тремя вершинами слева или справа?

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

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

Может быть, есть более простой и быстрый способ определить, есть ли треугольник слева, который мне не хватает?

Answer 1

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

У меня возникает ощущение, что ваше текущее решение, вероятно, довольно хорошее.

Answer 2

Я вижу это так:

1. найти 2 точки с минимальным и максимальным Y координате

   • , если любые две точки имеют одинаковые Y координат
   • , то вы должны выбрать один с координатой X ближе к другой Y мин/максимальная точка

2. проверить 3.th точки х координат

   • , если она меньше, чем любой другой точке она остается лицом
   • , если он больше, чем любой другой точке она остается лицом

[Примечание]

• эта реализация требует нескольких if состояний
• , который может быть медленнее, чем решить эту проблему путем перекрестного продукта ...
• даже если она имеет меньше операций

если ваши треугольники с установленным обмоткой (всегда CW или CCW)

• треугольник имеет а, в, с указуют

• подсчета вычислений положительного и отрицательного д линий, как это:

  int p=0,n=0; 
  if (B.y-A.y>=0) p++; else n++; 
  if (C.y-B.y>=0) p++; else n++; 
  if (A.y-C.y>=0) p++; else n++; 
  

• теперь для CW

• if (p<n) left_facing; else right_facing;
• для КОО это inegated ...