Coplanar проверка отсутствует определенный случай

Question

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

public static bool IsCoplanar(Point[] points) 
{ 
    // Ensure there are greater than three points (otherwise always coplanar) 
    if (points.Length < 4) 
    { 
     return true; 
    } 

    Point pointA = points[0]; 
    Point pointB = points[1]; 
    Point pointC = points[2]; 

    // Calculate the scalar triple product using vectors formed from 
    // the first three points and each successive point to check that 
    // the point is on the same plane as the first three. 
    Vector vectorBA = pointB - pointA; 
    Vector vectorCA = pointC - pointA; 

    for (int i = 3; i < points.Length; i++) 
    { 
     Point pointD = points[i]; 

     Vector vectorDA = pointD - pointA; 

     if (!(System.Math.Abs(vectorBA.Dot(vectorCA.Cross(vectorDA))) < Epsilon)) 
     { 
      return false; 
     } 
    } 

    return true; 
} 

К сожалению, это, кажется, возвращает истину в случае, например, начиная с 3 копланарными баллы:

(-50, 50, -50) 
(-50, -50, -50) 
(-50, -50, 50) 

Которые являются точными. Но если вы добавите:

(50, -50, 50) 
(50, -50, -50) 

К списку и снова запустить, он по-прежнему возвращает true.

Я смотрел на это целую вечность, но не смог определить проблему, есть ли у кого-нибудь идеи?

Спасибо.

Answer 1

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

Учитывая формулу плоскости:

Ax + By + Cz + D = 0 

взять свои первые три очка, которые определяют плоскость, и генерировать коэффициенты A, B, C и D.

Для остальных точек, а затем проверить:

Point v; 

    float d = A * v.x + B * v.y + C * v.d; 

d теперь расстояние от этой точки до плоскости, вдоль плоскости нормаль.

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

, если abs(d - D) < float.Epsilon), тогда можно смело полагать, что точка лежит в плоскости.

Пример (from this site)

заданные точки P, Q, R в пространстве, найти уравнение плоскости, проходящей через 3 очка.

Если P = (1, 1, 1), Q = (1, 2, 0), R = (-1, 2, 1).

Мы ищем коэффициенты уравнения Ax + By + CZ = D, где Р, Q и R удовлетворяют уравнениям, таким образом:

a + b + c = d 
a + 2b + 0c = d 
-a + 2b + c = d 

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

b - c = 0 
4b + c = 2d 

Добавление уравнений дает 5б = 2d, либо б = (2/5) d, то решение при с = Ь = (2/5) d, а затем a = d - b - c = (1/5) d.

Так уравнение (с ненулевой константой слева, чтобы выбрать) является d(1/5)x + d(2/5)y + d(2/5)z = d, поэтому один выбор постоянной дает

x + 2y + 2z = 5 

или, A = 1, B = 2, C = 2, и D = -5.

После того, как у вас есть это, проверка остальной части точек просто подставляет точки x, y, z в уравнение плоскости и сравнивает выход с расстоянием D от плоскости до начала координат.

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

Answer 2

Вот код на C#. Обратите внимание, что операции типа Cross и Equal должны быть операторами классов, я этого не делал. Кроме того, я включил проверку кросс-кода для таких вещей, как совпадающие точки. И.Е. что произойдет, если входные данные являются неповторимыми точками, например (50,50,50), за которыми следуют (50,50,50), ваш текущий код выходит из строя!

public static bool IsCoplanar(MyPoint[] points) 
    { 
     if (points.Length <= 3) 
      return true; 

     //input points may be the coincidental/same (edge case), 
     //so we first need to loop to find three unique points. 
     //the first unique point is by default at position 0, 
     //so we will start looking for second at position 1: 
     int unique_point2_index = 0; 
     int unique_point3_index = 0; 
     bool found_point2 = false; 
     bool found_point3 = false; 
     for (int i = 1; i < points.Length; ++i) 
     { 
      if (!found_point2) 
      { 
       if (!Equals(points[0], points[i])) 
       { 
        found_point2 = true; 
        unique_point2_index = i; 
       } 
      } 
      else if (!found_point3) 
      { 
       if (!Equals(points[0], points[i]) && !Equals(points[unique_point2_index], points[i])) 
       { 
        found_point3 = true; 
        unique_point3_index = i; 
       } 
      } 
      else 
       break; 
     } 

     //if we did not find three unique points, then all of the points are coplanar! 
     if (!found_point3) 
      return true; 

     //we found three unique points lets loop through the rest and check if those 
     //are also coplanar. We do that as following: 
     //First compute the plane normal: 
     MyPoint P1 = points[0]; 
     MyPoint P2 = points[unique_point2_index]; 
     MyPoint P3 = points[unique_point3_index]; 
     MyPoint vecP1P2 = Minus(P2, P1); //Should be class operator, P2 - P1 
     MyPoint vecP1P3 = Minus(P3, P1); 
     MyPoint normal = Cross(vecP1P2, vecP1P3); 

     //Secondly, for the remainder of points, we compute 
     //a vector from P1 to each point, 
     //and take the dot product with the normal. 
     //This should be zero (+- epsilon) for coplanar points 
     for (int i = unique_point3_index + 1; i < points.Length; ++i) 
     { 
      MyPoint testVec = Minus(points[i], P1); 
      double dot = Dot(testVec, normal); 
      //include error boundary for double precision 
      if (Math.Abs(dot) > 0.000001) 
       return false; 
     } 
     return true; 
    }