Треугольники не могут быть вогнутыми. Вы имеете в виду, что ваша сетка вогнутая?
Я не понял, что вы говорите об определенной технике. После небольшого исследования, я думаю, что понимаю вашу проблему достаточно, чтобы попытаться ответить.
Предположим, вы пересекаете вершины своего многоугольника против часовой стрелки. Если мы пройдем их в этом порядке, тело многоугольника всегда будет слева. Мы рассматриваем три вершины: A , B и C . Представьте, что мы испускаем луч от A до B . Если C слева от этого луча, то это правильно сформированный треугольник, являющийся частью многоугольника. Если C справа от этого луча, то он представляет отрицательное пространство.
ОК, давайте создадим векторы v (что составляет A → B ) и w (что составляет B). → C ). Кроме того, давайте построим v ', который равен v , но повернут на 90 градусов против часовой стрелки. v ' = <-v [y], v [x]>
Чтобы узнать, находится ли C слева или справа от v , нам просто нужно измерить угол между v ' и ш . Если он находится в пределах (0, 90) или (270, 360), то он слева. Если оно в пределах (90, 270), то это справа. Это удобно, потому что это точно соответствует, где cos (Θ)> 0 и где cos (Θ) <0 соответственно. Итак, если cos (Θ)> 0, то C слева, а если cos (Θ) <0, то C справа. </p>
Мы можем использовать точечные продукты, чтобы помочь нам определить cos (Θ). Помните, что cos (Θ) = ( v ' • w ) / (mag ( v' ) ⋅ mag ( w )) , Однако на самом деле нам не нужен cos (Θ), нам нужен только знак (cos (Θ)). Поскольку mag ( v ') и mag ( w ) должны быть положительными, мы можем их игнорировать. Следовательно, если v ' • w > 0, то C находится слева, и три точки соответствуют треугольнику, который является частью многоугольника. С другой стороны, если v ' • w <0, то C находится справа, а три точки соответствуют отрицательному пространству вне многоугольника. </p>
На самом деле я не пробовал это, кроме простых тестов, но я верю, что это (или что-то похожее) будет работать.
О, и для других, кто (как и я) никогда не слышал об этой технике, вы можете прочитать об этом здесь .