Определите, обращен ли треугольник влево

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

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

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

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


3d math geometry rasterizing
person T .    schedule 11.08.2014    source источник
comment
Не могли бы вы уточнить, что вы имеете в виду, говоря «повернутым налево»?   -  person Mokosha    schedule 12.08.2014
comment
С левой стороны будет треугольник, в котором (по вертикали) средняя вершина лежит слева от линии, соединяющей верхнюю и нижнюю вершины.   -  person T .    schedule 12.08.2014
comment
для чего это используется? никогда раньше не слышал о такой классификации треугольников.   -  person Spektre    schedule 12.08.2014
comment
Nit: вы имеете в виду 5 вычитаний, да? Хотя, думаю, если вас интересует только знак результата, вы можете превратить это в 4 вычитания и одно сравнение.   -  person Mark Dickinson    schedule 13.08.2014
comment
Вы правы, это 5 вычитаний, хороший улов. Я исправил это   -  person T .    schedule 13.08.2014

Ответы (2)


arrow_upward
2
arrow_downward

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

Мне кажется, что ваше текущее решение, вероятно, довольно хорошее.

person Klas Lindbäck    schedule 12.08.2014

arrow_upward
0
arrow_downward

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

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

    • if any two points have the same Y coordinate
    • тогда вам нужно выбрать одну с координатой X ближе к другой точке Y min / max

  2. проверить координату x 3-й точки

    • if it is less then any other point it is Left facing
    • если она больше, чем любая другая точка, она обращена влево

треугольник лицом

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

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

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

  • треугольник имеет точки A, B, C

  • вычислить количество положительных и отрицательных dy таких строк:

    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;
  • для CCW он встроен ...
person Spektre    schedule 12.08.2014
comment
Если x-координата третьей вершины находится между x-координатами вершины 1 и 2, вам потребуются дополнительные вычисления. - person Klas Lindbäck; 12.08.2014
comment
@ KlasLindbäck Я знаю, что вы имеете в виду, но определяется ли облицовка в таком случае? кстати, ваш ответ завершается так же, как и мой, см. примечания :) - person Spektre; 12.08.2014
comment
Да, облицовка определяется. Он обращен влево, если третья вершина находится слева от стороны между вершиной 1 и вершиной 2. Пример: (0, 0), (2, 5), (1, 3) обращено влево, а (0, 0), (2, 5), (1, 2) обращены вправо. - person Klas Lindbäck; 12.08.2014