Выпуклая оболочка 4 балла

Question

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

Answer 1

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

triangle_ABC= (A.y-B.y)*C.x + (B.x-A.x)*C.y + (A.x*B.y-B.x*A.y)

Для правосторонней системы координат это значение будет положительным, если ABC против часовой стрелки, отрицательным для часовой стрелки и нулевым, если они коллинеарны. Но следующее будет работать так же хорошо для левой системы координат, так как ориентация относительна.

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

triangle_ABD= (A.y-B.y)*D.x + (B.x-A.x)*D.y + (A.x*B.y-B.x*A.y)
triangle_BCD= (B.y-C.y)*D.x + (C.x-B.x)*D.y + (B.x*C.y-C.x*B.y)
triangle_CAD= (C.y-A.y)*D.x + (A.x-C.x)*D.y + (C.x*A.y-A.x*C.y)

Если все три из {ABD, BCD, CAD} имеют тот же знак, что и ABC, то D находится внутри ABC, а корпус - это треугольник ABC.

Если два из {ABD, BCD, CAD} имеют тот же знак, что и ABC, а один имеет противоположный знак, то все четыре точки являются экстремальными, а корпус четырехугольным ABCD.

Если один из {ABD, BCD, CAD} имеет тот же знак, что и ABC, а два имеют противоположный знак, то выпуклая оболочка - это треугольник с тем же знаком; остальная точка находится внутри него.

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

Для тех случаев, когда ABC положительна:

ABC  ABD  BCD  CAD  hull
------------------------
 +    +    +    +   ABC
 +    +    +    -   ABCD
 +    +    -    +   ABDC
 +    +    -    -   ABD
 +    -    +    +   ADBC
 +    -    +    -   BCD
 +    -    -    +   CAD
 +    -    -    -   [should not happen]

Answer 2

Или просто используйте Джарвис марш .

Answer 3

Вот более специальный алгоритм, характерный для 4 точек:

• Найдите индексы точек с минимальным-X, максимальным-X, минимальным-Y и максимальным-Y и получите из этого уникальные значения. Например, индексы могут быть 0,2,1,2, а уникальные значения будут 0,2,1.
• Если имеется 4 уникальных значения, то выпуклая оболочка состоит из всех 4 точек.
• Если существует 3 уникальных значения, то эти 3 точки обязательно находятся в выпуклой оболочке. Проверьте, находится ли 4-ая точка в этом треугольнике; если нет, то это также часть выпуклой оболочки.
• Если есть 2 уникальных значения, то эти 2 точки находятся на корпусе. Из двух других точек точка, которая находится дальше от этой линии, соединяющей эти две точки, определенно находится на корпусе. Выполните тест сдерживания треугольника, чтобы проверить, находится ли другая точка также в корпусе.
• Если существует 1 уникальное значение, то все 4 точки являются со-инцидентами.

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

Answer 4

вот полный анализ проблемы и эффективный код рубина (минимизирует количество сравнений)

#   positions for d:
#
#           abc > 0                               abc < 0
#         (+-+- doesn't exist)               (-+-+ doesn't exist)
#
#
#                     |        /       ---+ \   --++    | -+++
#                     |       /        bdc   \  acbd    | acd
#                     | +-++ /                \         |
#                     | abd /         ---------A--------B---------
#                     |    /                    \  --+- |
#                     |   /                      \ acb  |
#                     |  /                        \     |
#                     | /                          \    |
#                     |/                  ----      \   | -++-
#                     C                   adcb       \  | acdb
#                    /|                               \ |
#                   / |                                \|
#         ++++     /  |                                 C
#         abcd    /   |                                 |\
#                /    | +--+                            | \
#               /     | abdc                            |  \
#              / ++-+ |                                 |   \
#             /  abc  |                                 |    \
#   ---------A--------B---------                        |     \
#     +++-  /         |                                 |      \
#     bcd  /   ++--   | +---                            | -+--  \
#         /    adbc   | adc                             | adb    \
#
#   or as table
#
#   ++++ abcd       -+++ acd
#   +++- bcd        -++- acdb
#   ++-+ abc        -+-+ XXXX
#   ++-- adbc       -+-- adb
#   +-++ abd        --++ acbd
#   +-+- XXXX       --+- acb
#   +--+ abdc       ---+ bdc
#   +--- adc        ---- adcb
#
# if there are some collinear points, the hull will be nil (for the moment)
#
def point_point_point_orientation(p, q, r)
  (q.x - p.x) * (r.y - q.y) - (q.y - p.y) * (r.x - q.x)
end



def convex_hull_4_points(a, b, c, d)
  abc = point_point_point_orientation(a, b, c)
  if abc.zero?
    # todo
    return nil
  end

  bcd = point_point_point_orientation(b, c, d)
  if bcd.zero?
    # todo
    return nil
  end

  cda = point_point_point_orientation(c, d, a)
  if cda.zero?
    # todo
    return nil
  end

  dab = point_point_point_orientation(d, a, b)
  if dab.zero?
    # todo
    return nil
  end

  if abc.positive?
    if bcd.positive?
      if cda.positive?
        if dab.positive?
          [a, b, c, d] # ++++
        else
          [b, c, d]    # +++-
        end
      else
        if dab.positive?
          [a, b, c]    # ++-+
        else
          [a, d, b, c] # ++--
        end
      end
    else
      if cda.positive?
        if dab.positive?
          [a, b, d]    # +-++
        else
          raise        # +-+-
        end
      else
        if dab.positive?
          [a, b, d, c] # +--+
        else
          [a, d, c]    # +---
        end
      end
    end
  else
    if bcd.positive?
      if cda.positive?
        if dab.positive?
          [a, c, d]    # -+++
        else
          [a, c, d, b] # -++-
        end
      else
        if dab.positive?
          raise        # -+-+
        else
          [a, d, b]    # -+--
        end
      end
    else
      if cda.positive?
        if dab.positive?
          [a, c, b, d] # --++
        else
          [a, c, b]    # --+-
        end
      else
        if dab.positive?
          [b, d, c]    # ---+
        else
          [a, d, c, b] # ----
        end
      end
    end
  end
end

Answer 5

На основе решения Comestorm я создал решение C #, которое обрабатывает вырожденные случаи (например, 4 точки из линии или точки).

https://gist.github.com/miyu/6e32e993d93d932c419f1f46020e23f0

  public static IntVector2[] ConvexHull3(IntVector2 a, IntVector2 b, IntVector2 c) {
     var abc = Clockness(a, b, c);
     if (abc == Clk.Neither) {
        var (s, t) = FindCollinearBounds(a, b, c);
        return s == t ? new[] { s } : new[] { s, t };
     }
     if (abc == Clk.Clockwise) {
        return new[] { c, b, a };
     }
     return new[] { a, b, c };
  }

  public static (IntVector2, IntVector2) FindCollinearBounds(IntVector2 a, IntVector2 b, IntVector2 c) {
     var ab = a.To(b).SquaredNorm2();
     var ac = a.To(c).SquaredNorm2();
     var bc = b.To(c).SquaredNorm2();
     if (ab > ac) {
        return ab > bc ? (a, b) : (b, c);
     } else {
        return ac > bc ? (a, c) : (b, c);
     }
  }

  // See /1608077/vypuklaya-obolochka-4-balla
  public static IntVector2[] ConvexHull4(IntVector2 a, IntVector2 b, IntVector2 c, IntVector2 d) {
     var abc = Clockness(a, b, c);

     if (abc == Clk.Neither) {
        var (s, t) = FindCollinearBounds(a, b, c);
        return ConvexHull3(s, t, d);
     }

     // make abc ccw
     if (abc == Clk.Clockwise) (a, c) = (c, a);

     var abd = Clockness(a, b, d);
     var bcd = Clockness(b, c, d);
     var cad = Clockness(c, a, d);

     if (abd == Clk.Neither) {
        var (s, t) = FindCollinearBounds(a, b, d);
        return ConvexHull3(s, t, c);
     }

     if (bcd == Clk.Neither) {
        var (s, t) = FindCollinearBounds(b, c, d);
        return ConvexHull3(s, t, a);
     }

     if (cad == Clk.Neither) {
        var (s, t) = FindCollinearBounds(c, a, d);
        return ConvexHull3(s, t, b);
     }

     if (abd == Clk.CounterClockwise) {
        if (bcd == Clk.CounterClockwise && cad == Clk.CounterClockwise) return new[] { a, b, c };
        if (bcd == Clk.CounterClockwise && cad == Clk.Clockwise) return new[] { a, b, c, d };
        if (bcd == Clk.Clockwise && cad == Clk.CounterClockwise) return new[] { a, b, d, c };
        if (bcd == Clk.Clockwise && cad == Clk.Clockwise) return new[] { a, b, d };
        throw new InvalidStateException();
     } else {
        if (bcd == Clk.CounterClockwise && cad == Clk.CounterClockwise) return new[] { a, d, b, c };
        if (bcd == Clk.CounterClockwise && cad == Clk.Clockwise) return new[] { d, b, c };
        if (bcd == Clk.Clockwise && cad == Clk.CounterClockwise) return new[] { a, d, c };
        // 4th state impossible
        throw new InvalidStateException();
     }
  }

Вам нужно будет реализовать этот шаблон для вашего типа вектора:

  // relative to screen coordinates, so top left origin, x+ right, y+ down.
  // clockwise goes from origin to x+ to x+/y+ to y+ to origin, like clockwise if
  // you were to stare at a clock on your screen
  //
  // That is, if you draw an angle between 3 points on your screen, the clockness of that
  // direction is the clockness this would return.
  public enum Clockness {
     Clockwise = -1,
     Neither = 0,
     CounterClockwise = 1
  }
  public static Clockness Clockness(IntVector2 a, IntVector2 b, IntVector2 c) => Clockness(b - a, b - c);
  public static Clockness Clockness(IntVector2 ba, IntVector2 bc) => Clockness(ba.X, ba.Y, bc.X, bc.Y);
  public static Clockness Clockness(cInt ax, cInt ay, cInt bx, cInt by, cInt cx, cInt cy) => Clockness(bx - ax, by - ay, bx - cx, by - cy);
  public static Clockness Clockness(cInt bax, cInt bay, cInt bcx, cInt bcy) => (Clockness)Math.Sign(Cross(bax, bay, bcx, bcy));

Answer 6

На основе ответа @comingstorm я создал решение Swift:

func convexHull4(a: Pt, b: Pt, c: Pt, d: Pt) -> [LineSegment]? {

    let abc = (a.y-b.y)*c.x + (b.x-a.x)*c.y + (a.x*b.y-b.x*a.y)
    let abd = (a.y-b.y)*d.x + (b.x-a.x)*d.y + (a.x*b.y-b.x*a.y)
    let bcd = (b.y-c.y)*d.x + (c.x-b.x)*d.y + (b.x*c.y-c.x*b.y)
    let cad = (c.y-a.y)*d.x + (a.x-c.x)*d.y + (c.x*a.y-a.x*c.y)

    if  (abc > 0 && abd > 0 && bcd > 0 && cad > 0) ||
        (abc < 0 && abd < 0 && bcd < 0 && cad < 0) {
        //abc
        return [
            LineSegment(p1: a, p2: b),
            LineSegment(p1: b, p2: c),
            LineSegment(p1: c, p2: a)
        ]
    } else if   (abc > 0 && abd > 0 && bcd > 0 && cad < 0) ||
                (abc < 0 && abd < 0 && bcd < 0 && cad > 0) {
        //abcd
        return [
            LineSegment(p1: a, p2: b),
            LineSegment(p1: b, p2: c),
            LineSegment(p1: c, p2: d),
            LineSegment(p1: d, p2: a)
        ]
    } else if   (abc > 0 && abd > 0 && bcd < 0 && cad > 0) ||
                (abc < 0 && abd < 0 && bcd > 0 && cad < 0) {
        //abdc
        return [
            LineSegment(p1: a, p2: b),
            LineSegment(p1: b, p2: d),
            LineSegment(p1: d, p2: c),
            LineSegment(p1: c, p2: a)
        ]
    } else if   (abc > 0 && abd < 0 && bcd > 0 && cad > 0) ||
                (abc < 0 && abd > 0 && bcd < 0 && cad < 0) {
        //acbd
        return [
            LineSegment(p1: a, p2: c),
            LineSegment(p1: c, p2: b),
            LineSegment(p1: b, p2: d),
            LineSegment(p1: d, p2: a)
        ]
    } else if   (abc > 0 && abd > 0 && bcd < 0 && cad < 0) ||
                (abc < 0 && abd < 0 && bcd > 0 && cad > 0) {
        //abd
        return [
            LineSegment(p1: a, p2: b),
            LineSegment(p1: b, p2: d),
            LineSegment(p1: d, p2: a)
        ]
    } else if   (abc > 0 && abd < 0 && bcd > 0 && cad < 0) ||
                (abc < 0 && abd > 0 && bcd < 0 && cad > 0) {
        //bcd
        return [
            LineSegment(p1: b, p2: c),
            LineSegment(p1: c, p2: d),
            LineSegment(p1: d, p2: b)
        ]
    } else if   (abc > 0 && abd < 0 && bcd < 0 && cad > 0) ||
                (abc < 0 && abd > 0 && bcd > 0 && cad < 0) {
        //cad
        return [
            LineSegment(p1: c, p2: a),
            LineSegment(p1: a, p2: d),
            LineSegment(p1: d, p2: c)
        ]
    }

    return nil

}

Answer 7

Я написал быструю реализацию ответа comestorm, используя таблицу поиска. Случай, когда все четыре точки являются коллинеарными, обрабатывается , а не , поскольку мое приложение не нуждается Если точки коллинеарны, алгоритм устанавливает нулевую первую точку указателя [0]. Корпус содержит 3 точки, если точка [3] является нулевым указателем, в противном случае корпус имеет 4 точки. Корпус расположен против часовой стрелки для системы координат, в которой ось Y указывает на верхнюю часть, а ось X - на правую.

const char hull4_table[] = {        
    1,2,3,0,1,2,3,0,1,2,4,3,1,2,3,0,1,2,3,0,1,2,4,0,1,2,3,4,1,2,4,0,1,2,4,0,
    1,2,3,0,1,2,3,0,1,4,3,0,1,2,3,0,0,0,0,0,0,0,0,0,2,3,4,0,0,0,0,0,0,0,0,0,
    1,4,2,3,1,4,3,0,1,4,3,0,2,3,4,0,0,0,0,0,0,0,0,0,2,3,4,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,2,4,3,0,0,0,0,0,0,0,0,0,1,2,4,0,1,3,4,0,1,2,4,0,1,2,4,0,
    0,0,0,0,0,0,0,0,1,4,3,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3,4,0,0,0,0,0,0,0,0,0,
    1,4,2,0,1,4,2,0,1,4,3,0,1,4,2,0,0,0,0,0,0,0,0,0,2,3,4,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,2,4,3,0,0,0,0,0,0,0,0,0,2,4,3,0,1,3,4,0,1,3,4,0,1,3,2,4,
    0,0,0,0,0,0,0,0,2,4,3,0,0,0,0,0,0,0,0,0,1,3,2,0,1,3,4,0,1,3,2,0,1,3,2,0,
    1,4,2,0,1,4,2,0,1,4,3,2,1,4,2,0,1,3,2,0,1,3,2,0,1,3,4,2,1,3,2,0,1,3,2,0
};
struct Vec2i {
    int x, y;
};
typedef long long int64;    
inline int sign(int64 x) {
    return (x > 0) - (x < 0);
}
inline int64 orientation(const Vec2i& a, const Vec2i& b, const Vec2i& c) {
    return (int64)(b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}

void convex_hull4(const Vec2i** points) {
    const Vec2i* p[5] = {(Vec2i*)0, points[0], points[1], points[2], points[3]};
    char abc = (char)1 - sign(orientation(*points[0], *points[1], *points[2]));
    char abd = (char)1 - sign(orientation(*points[0], *points[1], *points[3]));
    char cad = (char)1 - sign(orientation(*points[2], *points[0], *points[3]));
    char bcd = (char)1 - sign(orientation(*points[1], *points[2], *points[3]));

    const char* t = hull4_table + (int)4 * (bcd + 3*cad + 9*abd + 27*abc);
    points[0] = p[t[0]];
    points[1] = p[t[1]];
    points[2] = p[t[2]];
    points[3] = p[t[3]];
}

Answer 8

Я сделал доказательство концепции скрипки на основе грубой версии алгоритма упаковки подарков.

Неэффективно в общем случае, но достаточно только для 4 баллов.

function Point (x, y)
{
    this.x = x;
    this.y = y;
}

Point.prototype.equals = function (p)
{
    return this.x == p.x && this.y == p.y;
};

Point.prototype.distance = function (p)
{ 
    return Math.sqrt (Math.pow (this.x-p.x, 2) 
                    + Math.pow (this.y-p.y, 2));
};

function convex_hull (points)
{
    function left_oriented (p1, p2, candidate)
    {
        var det = (p2.x - p1.x) * (candidate.y - p1.y) 
                - (candidate.x - p1.x) * (p2.y - p1.y);
        if (det > 0) return true;  // left-oriented 
        if (det < 0) return false; // right oriented
        // select the farthest point in case of colinearity
        return p1.distance (candidate) > p1.distance (p2);
    }

    var N = points.length;
    var hull = [];

    // get leftmost point
    var min = 0;
    for (var i = 1; i != N; i++)
    {
        if (points[i].y < points[min].y) min = i;
    }
    hull_point = points[min];

    // walk the hull
    do
    {
        hull.push(hull_point);

        var end_point = points[0];
        for (var i = 1; i != N; i++) 
        {
            if (  hull_point.equals (end_point)
               || left_oriented (hull_point, 
                                 end_point, 
                                 points[i]))
            {
                end_point = points[i];
            }
        }
        hull_point = end_point;
    }
    /*
     * must compare coordinates values (and not simply objects)
     * for the case of 4 co-incident points
     */
    while (!end_point.equals (hull[0])); 
    return hull;
}

Это было весело :)