Проверьте, является ли угол, определенный 3 точками, внутренним или внешним

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

классификация углов

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

Для каждой ломаной линии я беру вершины 3 на 3 и могу распознать, является ли центральная точка углом, или нет, и измерить ее значение числом от 0 до 180 градусов.

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

1) Просто «знак двумерного перекрестного продукта» (я знаю, что это не математически правильная терминология):

//given 3 contiguous vertices a,b,c
//check if b is a inner (+1) or outer (-1) vertex (0 in other cases)

double cross = ((b.x - a.x)*(c.y - a.y)) - ((b.y - a.y)*(c.x - a.x));

if(cross > 0){
return 1;
} else if (cross < 0) {
return -1;
}
return 0;

Но, похоже, он работает только в нижнем левом квадранте, в правом верхнем углу работает точно так же, как и другие, и я не могу понять, почему.

2) Сравните норму вершин

if b.norm() < a.norm() && b.norm() < c.norm
then return +1
else return -1

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

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

3

Решение

Краткая версия:

Опишите два угловых вектора, приходящих из центральной точки, как a а также b, И опишите вектор из вашей центральной точки в начало координат как center,

Угол будет описан как «внутренний», если:

dot( a + b, center ) > 0.0 && dot( cross( a, center ), cross( b, center ) ) < 0.0

Объяснение:

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

Здесь это решается в два этапа.

1. Является ли угол наведения Больше в сторону происхождения, чем далеко?

Угол указывает больше к чем далеко если вы определяете «направление, на которое указывает угол», суммируя два угловых вектора.

Обратите внимание, что если отдельные длины a а также b отличаются, вы можете получить неправильные граничные случаи для очень широких углов. Нормализация a а также b это исправлю.

`dot( a + b, center ) > 0.0`

2. Векторы a а также b указывая на противоположные стороны происхождения?

векторы a а также b указывают на противоположные стороны происхождения, если их перекрестные произведения указывают в противоположных направлениях.

`dot( cross( a, center ), cross( b, center ) ) < 0.0`

Если и только если они оба истинны, ваш угол определяется как «внутренний».

4

Другие решения

Чтобы определить, является ли угол abc внутренним, необходимо проверить, является ли вектор b0 (от b до начала координат) выпуклой комбинацией векторов ba и bc.

Если вектор px + qy является выпуклой комбинацией векторов p1x + q1y и p2x + q2y, существуют такие положительные постоянные r и s, что r * (p1, q1) + s * (p2, q2) = (p, q) , Если мы решим для r и s алгебраически, мы получим r = (pq2 — p2q) / (p1q2 — q1p2) и s = (p1q — pq1) / (p1q2 — q1p2). Если r и s оба положительны, abc является внутренним.

3

Лично я бы просто использовал точечный продукт. Конкретно (если a представляет вектор от твоя вершина в происхождение и b а также c ваши краевые векторы направлены из вершины), тогда угол является внешним, если оба a dot b а также a dot c положительны. В противном случае это внутреннее.

Но я немного запутался по поводу вашего реального определения «внутреннего» и «внешнего» …

0