Геометрия (школьный курс)

[facelift]

Геометрия (школьный курс)

Есть четыре точки. первые три задают треугольник. надо проверить лежит ли четвертая внутри него. Точки задаются координатами (x,y,z). Больше нет никаких условий. Помогите кто-нить пожалуйта))) Я уже в панике))

 

[kruglov]

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

 

[zerkms]

Точки задаются координатами (x,y,z).

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

 

[Alexandre]

Точки задаются координатами (x,y,z).

это три точки x,y,z, а для каждой координаты каждой (x,y)

если трехмерное пространство, то это уже далеко не школьная задачка, хотя тоже простая - проверить - принадлежит ли точка плоскости, заданной тремя точками (x,y,z).

Решение (двухмерное) приблизительное:
- вычисляем MaxX и MinX и проверяем условие MinX < Px< MaxX
- тоже и для Py

MaxX (MinX) вычисляется как наиболее дальняя (ближняя точка ) проекции на ось Х


Решение (более правильное)
- строим три линии через три точки (есть уравнение построение линии по двум точкам) и проверяем
- для положит угла ( < 180) точка должна быть под линией
- для отриц угла ( > 180 ) точка должна быть над линией

 

[zerkms]

придумалось только:

ABC - треугольник, X - точка

найти точку пересечения AX с BC, проверить что X лежит между A и <полученная точка пересечения>
повторить для двух оставшихся вершин

kruglov
при очень близких к границе точках твой метод будет давать погрешность ввиду округления при вычислении площадей

-~{}~ 11.05.06 21:56:

из ирц:

4.Точка, принадлежащая треугольнику (постулат 3) определяется следующим образом:
4.1. Координата X точки-претендента на принадлежность к треугольнику больше минимального значения координаты X в каждой из всех возможных пар (а их три, как ни странно), и меньше максимального значения координаты X в тех же парах.
4.2 Координата Y точки-претендента удовлетворяет аналогичным постулату 4.1. условиям но по координате Y для каждой из пар.
4.3 Координаты точки-претендента не равны координатам каждой из трёх точек, определяющих треугольник.
(с)

-~{}~ 11.05.06 22:04:

хм... вышеописанный алгоритм повторить не могу
(0;0), (10;10), (20;0) - треугольник
(19;5) - точка

согласно 4.1:
19 > 0; 19 < 20

согласно 4.2:
5 > 0; 5 < 10

4.3
...

 

[Krishna]

Имхо лучше считать средствами аналитической геометрии. Векторы нормали и всё такое.

 

[StUV]

Krishna
см. название топика =)))

 

[Сергей Тарасов]

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

Красивое решение:
1) Из точки строиться луч(в любую сторону)
2) Находится кол-во пересечений луча с границами фигуры( в случае треугольника просто решается 3 уравнения пересечения луча со сторонами.
3) Если число пересечений - нечетное - то внутри, если четное - вне

 

[kruglov]

Надо еще, чтоб этот луч не проходил через вершину треугольника.

 

[Andreika]

расстояния AD (из т.A до искомой точки D) < расстояния от A до пересечения AD с противоположной стороной треугольника.. и также для B и C

Находится кол-во пересечений луча с границами фигуры
если границы фигуры - прямые, а не отрезки, то число пересечений - нечетное организовать очень даже легко из точки, не пренадлежашей треугольнику

 

[itprog]

<оффтоп>
такие бы задачи на олимпиаду надо

 

[Сергей Тарасов]

Да!
А та олимпиада, которая была - просто пипец какой-то.... )
Сплошной коммерческий кодинг...
Даже стыдно... )

 

[zerkms]

расстояния AD (из т.A до искомой точки D) < расстояния от A до пересечения AD с противоположной стороной треугольника.. и также для B и C

как раз то, что было в моём посте ранее

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

эм..... "прямые, а не отрезки"..хмхм.... и как? рисунок в студию

 

[Wicked]

делал такое в одном из своих проектов...

1) Строим матрицу аффинного отображения треугольника в треугольник (1, 0), (0, 0), (0, 1). Код см. ниже.
2) Отображаем этим аффинным отображением искомую точку - тупо использовал Pear-овский Math_Matrix::vectorMultiply().
3) Смотрим, лежит ли она в треугольнике (1, 0), (0, 0), (0, 1): x >= 0 && y >= 0 && x + y <= 1;

  function affine_to1triangle($v1, $v2, $v3) {
    $div = $v2[1] * $v3[0] - $v1[1] * $v3[0] - $v2[1] * $v1[0] + $v1[1] * $v2[0] + $v3[1] * $v1[0] - $v3[1] * $v2[0];

    $matrix_ar = array(
      array(
        ($v1[1] - $v3[1]) / $div,
        -(-$v3[0] + $v1[0]) / $div,
        -(-$v3[1] * $v1[0] + $v1[1] * $v3[0]) / $div,
      ),
      array(
        ($v2[1] - $v1[1]) / $div,
        -($v2[0] - $v1[0]) / $div,
        ($v1[1] * $v2[0] - $v2[1] * $v1[0]) / $div,
      ),
      array(
        0,
        0,
        1,
      ),
    );

    $matrix = new Math_Matrix($matrix_ar);
    return $matrix;
  }

 

[zerkms]

Wicked

Смотрим, лежит ли она в треугольнике (1, 0), (0, 0), (0, 1): x >= 0 && y >= 0 && x + y <= 1;

откуда взялись условия?

 

[Wicked]

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

 

[zerkms]

Wicked
а ты сможешь автоматизировать процесс определения знака условия?

 

[Wicked]

прости, что?

 

[Andreika]

маразм крепчал...

Wicked
разпиши пжалста для учительницы аффтора Pear-овский Math_Matrix::vectorMultiply на бумажке в клеточку, а то боюсь она не оценит использование сторонних библиотек в домашнем задании по геометрии

 

[Wicked]

гы %) понял, отстал... не посмотрел, в каком разделе трэд