Определите, находится ли точка внутри треугольника, образованного 3 точками с заданной широтой / долготой

Question

У меня есть 3 точки (широта, долгота), которые образуют треугольник. Как я могу найти, если точка находится внутри этого треугольника?

Answer 1

Java-код только для треугольника, то есть 3 балла.

    public static boolean pntInTriangle(double px, double py, double x1, double y1, double x2, double y2, double x3, double y3) {

    double o1 = getOrientationResult(x1, y1, x2, y2, px, py);
    double o2 = getOrientationResult(x2, y2, x3, y3, px, py);
    double o3 = getOrientationResult(x3, y3, x1, y1, px, py);

    return (o1 == o2) && (o2 == o3);
}

private static int getOrientationResult(double x1, double y1, double x2, double y2, double px, double py) {
    double orientation = ((x2 - x1) * (py - y1)) - ((px - x1) * (y2 - y1));
    if (orientation > 0) {
        return 1;
    }
    else if (orientation < 0) {
        return -1;
    }
    else {
        return 0;
    }
}

Answer 2

Вот реализация Javascript решения барицентрических координат , обсуждаемого здесь :

// Returns true if point P inside the triangle with vertices at A, B and C
// representing 2D vectors and points as [x,y]. Based on                        
// http://www.blackpawn.com/texts/pointinpoly/default.html
function pointInTriange(P, A, B, C) {
  // Compute vectors        
  function vec(from, to) {  return [to[0] - from[0], to[1] - from[1]];  }
  var v0 = vec(A, C);
  var v1 = vec(A, B);
  var v2 = vec(A, P);
  // Compute dot products
  function dot(u, v) {  return u[0] * v[0] + u[1] * v[1];  }
  var dot00 = dot(v0, v0);
  var dot01 = dot(v0, v1);
  var dot02 = dot(v0, v2);
  var dot11 = dot(v1, v1);
  var dot12 = dot(v1, v2);
  // Compute barycentric coordinates
  var invDenom = 1.0 / (dot00 * dot11 - dot01 * dot01);
  var u = (dot11 * dot02 - dot01 * dot12) * invDenom;
  var v = (dot00 * dot12 - dot01 * dot02) * invDenom;
  // Check if point is in triangle
  return (u >= 0) && (v >= 0) && (u + v < 1);
}

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

Answer 3

Большинство языков включают функцию для этого. В Java это Polygon.contains () http://docs.oracle.com/javase/7/docs/api/java/awt/Polygon.html

Просто создайте многоугольник из ваших точек, а затем вызовите в вашей контрольной точке ().

Answer 4

Вы можете использовать тест точки-полигона.

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

Это работает для любого типа многоугольника.

Answer 5

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

Если это так, то что-то простое, например, барицентрические координаты, будет хорошо работать.

Answer 6

Я сделал что-то подобное сегодня! Также с (lat, lon), на самом деле (theta, phi), хотя я знал немного больше о меше, с которым я работал. Я работаю с (theta, phi) с 0 <= theta <= PI && 0 <= phi <= 2 * PI. </p>

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

Во всех других случаях, если вы конвертировали свою точку в (широта, долгота) / (тета, фи). Должно быть просто использовать метод, описанный @Michelle Six.

Answer 7

function SameSide(p1,p2, a,b)
    cp1 = CrossProduct(b-a, p1-a)
    cp2 = CrossProduct(b-a, p2-a)
    if DotProduct(cp1, cp2) >= 0 then return true
    else return false

function PointInTriangle(p, a,b,c)
    if SameSide(p,a, b,c) and SameSide(p,b, a,c)
        and SameSide(p,c, a,b) then return true
    else return false

Объясняется по ссылке ниже

http://www.blackpawn.com/texts/pointinpoly/default.html

Answer 8

Попробуйте алгоритм наведения лучей.

http://en.wikipedia.org/wiki/Point_in_polygon

Это довольно просто реализовать.