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

Question

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

Допустим, у меня есть прямоугольник, который64x64 пикселей.С помощью этого прямоугольника я хочу вернуть значение ИСТИНА, если пройденная точка находится в верхнем левом углу прямоугольника, и ЛОЖЬ, если это не так.

-----
|  /|
| / |
|<__|

Ужас за плохое искусство ASCII.

В любом случае, гипотетические точки для этого треугольника, которые будут возвращать TRUE, будут (0,0) и (63,0) и (0, 63).Если точка приземляется на линию (например, 50,0), она также возвращает TRUE.

Предполагается, что 0,0 находится в верхнем левом углу и увеличивается вниз ...

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

Должен быть лучший способ.

РЕДАКТИРОВАТЬ: Прямоугольник также может выглядеть так же

-----
|\  |
| \ |
|__>|

Но я полагаю, что в большинстве случаев уже предоставленные текущие ответы должны все еще держаться ...

Answer 1

Верхний левый / нижний правый треугольник: Для всех точек в верхнем левом треугольнике, x+y<=64. Точки в нижнем правом треугольнике имеют x+y>64.

(для прямоугольника размера (w, h) используйте w * y + h * x-w * h <0) </p>

Верхний правый / нижний левый треугольники: Для всех точек нижнего левого треугольника, x<=y. Точки в верхнем правом треугольнике имеют x>y.

(для прямоугольника размера (w, h) используйте h * x-w * y <0) </p>

---

Как мы туда попали?

Для прямоугольника измерений (w, h) и треугольников TL / BR, уравнение диагонали (попробуйте! Назначьте x = 0 и убедитесь, что вы получите y == h, и назначьте y = 0 и убедитесь, что x == w)

h*x + w*y - w*h = 0

Точки на одной стороне этой линии будут иметь

h*x + w*y - w*h > 0

В то время как очки на другом будут иметь

h*x + w*y - w*h < 0

Вставив 64 для w и h, получим:

64x + 64y - 64*64 < 0

Деление на 64 дает нам:

x+y < 64

Для треугольников TR / BL, уравнение линии и получающиеся неравенства:

h*x - w*y = 0
h*x - w*y < 0
h*x - w*y > 0

Вставив 64 для w и h, получим

64x-64y < 0
=> x<y

Answer 2

Вы можете представить треугольник с тремя аффинными функциями

взять единичный треугольник с углами в (0, 0), (1, 0) и (1, 1).стороны представлены тремя линиями

1. y = 0
2. x = 1
3. y = x

Итак, интерьери границы треугольника задаются как пересечение множеств

1. x> = 1
2. y> = 0
3. y <= x </li>

поэтому, учитывая точку (x, y), вам просто нужно проверить, что она удовлетворяет этим трем неравенствам.

Вы, конечно, можете обобщить это на любой треугольник, используя тот факт, что любая аффинная функция(представляющий строку) может быть записан в виде y = mx + b.

Answer 3

Предположим, что ваш прямоугольный треугольник имеет один угол в 0,0 и диагональный угол в a, b.

Так что y = mx + c c = 0, когда мы начинаем в начале координат.

т = B / A

Итак, у = bx / a

Чтобы узнать, на какую половину треугольника попадает ваша точка (c, d)

if (d <= (bc / a)) {// точка находится в нижней половине} </p>

if (d> (bc / a)) {// точка находится в верхней половине}

Я думаю ...

Answer 4

Уравнение для линии выглядит так:

y = mx + b

Итак, если вы добавите свои x и y-значения в это уравнение, оно, вероятно, больше не будет выполняться Давайте переформулируем это:

mx + b - y = 0

То же самое, другой взгляд. Опять же, результат, вероятно, не ноль. Но результат теперь скажет вам, находится ли он на одной стороне линии или на другой.

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

Answer 5

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

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