Блог

Учитывая 4 неупорядоченных точки, как мне получить два треугольника из этих точек, НЕ формируя форму песочных часов или не перекрывая треугольники. Выпуклые четырехугольники — это хорошо, но я бы предпочел метод, который удалял бы точку вблизи центра, ограниченную другими точками внутри одного треугольника. У меня есть полурабочее решение, но оно не очень красивое. Ранее я пробовал триангуляцию Делоне, формируя 4 треугольника через центральную точку и перемещаясь вокруг нее радиально, добавляя точки для создания треугольников, среди других методов. Кажется, я не могу найти никакой информации по этой теме, кроме разделения треугольников.

Итак, это то, что я сделал, и, похоже, это сработало хорошо. Для первого треугольника возьмите первые 3 точки и сделайте из них треугольник. Затем сохраните список средних сечений точек для каждого ребра. Середина, ближайшая к четвертой точке, находится на ребре, на котором есть другие 2 точки, которые образуют ваш второй треугольник.

псевдокод

 func getMidsection(Point a, Point b) -> Point
{
  Point midsection = Point(
   (a.x   b.x) / 2,
   (a.y   b.y) / 2,
   (a.z   b.z) / 2
  );
  return midsection;
}

func getTrianglesFromPoints(Point[4] points) -> Triangle[2]
{
  // define first triangle as first 3 points
  Triangle tri1 = Triangle(points[0], points[1], points[2]);
  
  Point[3] midsections;
  float recordDist = -1;
  int closestMidsection;
  
  // loop through each edge in the first triangle 
  for(i : [0, 3) )
  {
    // get the midsection using the current point and next point in the first triangle
    midsections[i] = getMidsection(points[i], points[(i 1)%3]);
    // if the 4th point's distance to the midsection is smaller than past values, set the smallest dist to that point
    if(dist(points[3], midsections[i]) < recordDist or recordDist == -1)
    {
      recordDist = dist(points[3], midsections[i]);
      closestMidsection = i;
    }
  }
  // define triangle2 from the closest midsection
  Triangle tri2 = Triangle(points[closestMidsection], points[(closestMidsection   1) % 3, points[3]);

  // return the triangles
  return [tri1, tri2];
}