ສູດການຄິດໄລ່ Convex Hull


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ເລຂາຄະນິດ Morgan Stanley Samsung

ໃນບັນຫາ“ Convex Hull Algorithm” ພວກເຮົາໄດ້ ກຳ ນົດບາງຈຸດ. polygon ຂະຫນາດນ້ອຍທີ່ສຸດທີ່ສາມາດໄດ້ຮັບການສ້າງຕັ້ງຂຶ້ນກັບຈຸດທີ່ປະກອບດ້ວຍຈຸດອື່ນໆທັງຫມົດພາຍໃນມັນຈະຖືກເອີ້ນວ່າໂກນ convex ຂອງຕົນ.

ສູດການຄິດໄລ່ Convex Hull

ສິ່ງນີ້ສາມາດບັນລຸໄດ້ໂດຍການ ນຳ ໃຊ້ Jarvis Algorithm.

ລະບົບວິເຄາະ

  1. ເລີ່ມຕົ້ນຈຸດທີ່ຢູ່ເບື້ອງຊ້າຍຫາ 0.
  2. ປະກາດກ vector ຊື່ຜົນໄດ້ຮັບຂອງປະເພດຈຸດ
  3. ລອກເອົາຈຸດຂອງຈຸດປະສົງຈົນກ່ວາຈຸດທີ່ພົບເຫັນເບື້ອງຊ້າຍ
  4. ເພີ່ມຈຸດນັ້ນໃສ່ vector ຜົນໄດ້ຮັບ
  5. ຊອກຫາຈຸດຕໍ່ໄປ "Q" ເຊັ່ນວ່າມັນແມ່ນຈຸດກົງກັນຂ້າມທີ່ສຸດທີ່ປິດຈຸດອື່ນໆທັງ ໝົດ
  6. ຕັ້ງຄ່າ p ເຖິງຈຸດ "Q" ສໍາລັບ iteration ຕໍ່ໄປ.
  7. ສືບຕໍ່ເພີ່ມຂື້ນໃນຂະນະທີ່ "P" ບໍ່ເທົ່າກັບເບື້ອງຊ້າຍ.

ລາຍລະອຽດ

ສະນັ້ນແນວຄວາມຄິດຫລັກຂອງພວກເຮົາໃນການແກ້ໄຂຮູໂກນແມ່ນການໃຊ້ທິດທາງ. ພວກເຮົາ ກຳ ລັງຈະຊອກຫາແລະເລີ່ມຕົ້ນດ້ານຊ້າຍຫລືອາດຈະເປັນຕົວປະສານ X ຕໍ່າສຸດ. ແລະພວກເຮົາສາມາດເອົາມັນໄປຈົນກວ່າທຸກຈຸດຂອງພວກເຮົາພົບວ່າຊຸດຂອງບາງຈຸດສາມາດສະສົມ.

ພວກເຮົາ ກຳ ລັງຈະຜ່ານຈຸດ Array ຂອງຈຸດໃຊ້ Class Class ຂອງຜູ້ໃຊ້, ເຊິ່ງພວກເຮົາໄດ້ ກຳ ນົດມັນແລ້ວໃນຕອນເລີ່ມຕົ້ນຂອງລະຫັດ. ການໂຕ້ຖຽງຂອງພວກເຮົາກ່ຽວກັບຈຸດແລະຄວາມຍາວຂອງເລກເຕັມແມ່ນຖືກສົ່ງເຂົ້າໄປໃນຮູໂກນ ຫນ້າທີ່, ບ່ອນທີ່ພວກເຮົາຈະປະກາດຜົນ vector ຊື່ທີ່ພວກເຮົາຈະເກັບຜົນຜະລິດຂອງພວກເຮົາ.

ດຽວນີ້ເລີ່ມຕົ້ນຈຸດທີ່ຢູ່ເບື້ອງຊ້າຍຫາ 0. ພວກເຮົາຈະເລີ່ມຕົ້ນມັນຈາກ 0, ຖ້າພວກເຮົາໄດ້ຮັບຈຸດທີ່ມີຈຸດປະສານງານ x ຕ່ ຳ ສຸດຫລືຈຸດທີ່ຢູ່ເບື້ອງຊ້າຍພວກເຮົາຈະປ່ຽນມັນ.

ໃນປັດຈຸບັນລອກຈຸດທັງຫມົດແລະຊອກຫາຈຸດທີ່ຕໍ່າສຸດ. ເກັບຮັກສາຕໍາແຫນ່ງຂອງເບື້ອງຊ້າຍຫາ "P" ແລະປະກາດຈຸດໃດ ໜຶ່ງ

ໃນປັດຈຸບັນ, ເລີ່ມຕົ້ນເຮັດໃນຂະນະທີ່ loop ໃນສິ່ງທີ່ທໍາອິດທີ່ພວກເຮົາ gonna ເຮັດແມ່ນເພີ່ມຈຸດທໍາອິດເປັນຜົນໄດ້ຮັບ.

ດຽວນີ້ພວກເຮົາຕ້ອງຊອກຫາທິດທາງກົງກັນຂ້າມທີ່ສຸດເຖິງຈຸດອື່ນໆທັງ ໝົດ, ສຳ ລັບຈຸດນີ້, ພວກເຮົາຈະ ນຳ ໃຊ້ທິດທາງ. ພວກເຮົາໄດ້ເຮັດ ໜ້າ ທີ່ແຍກຕ່າງຫາກ ສຳ ລັບສິ່ງນີ້, ເຊິ່ງກວດເບິ່ງວ່າການ ກຳ ນົດທິດທາງຂອງ triplets ແມ່ນ 2 ຫລືບໍ່ຖ້າວ່າມັນພົບວ່າ 2 ແລ້ວປັບປຸງຄ່າຂອງຈຸດ "Q".

ສິ່ງນີ້ຄວນໄດ້ຮັບການສືບຕໍ່ຈົນກ່ວາ "P" ບໍ່ເທົ່າກັບເບື້ອງຊ້າຍ.

ຍົກຕົວຢ່າງ

ຈຸດທີ່ໄດ້ຮັບແມ່ນ:

{{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}};

leftmost = 0;

ຫຼັງຈາກຜ່ານຈຸດທັງ ໝົດ, ການປະສານງານ x ຕ່ ຳ ສຸດ ທຳ ອິດຂອງພວກເຮົາຈະເປັນ (0,3) ມັນຈະເກັບໄວ້ເປັນຜົນ.
ດຽວນີ້ ກຳ ລັງຈະກວດສອບວ່າ x, y ຄູ່ມີທິດທາງກົງກັນຂ້າມຫຼາຍທີ່ສຸດຍ້ອນວ່າມັນຈະເຮັດໃຫ້ການປະຖົມນິເທດເປັນ 2 ແລະປັບປຸງມູນຄ່າຂອງຈຸດ "Q".
ຄູ່ທີ່ຈະພົບເຫັນເປັນ (0,0).
ດຽວນີ້, ສຳ ເນົາມູນຄ່າຂອງຈຸດ "Q" p ເປັນຈຸດຕໍ່ໄປ ສຳ ລັບການຊອກຫາຈຸດກົງກັນຂ້າມທີ່ສຸດ.
ຈົນກ່ວາມູນຄ່າຂອງ p ແມ່ນບໍ່ເທົ່າກັບເບື້ອງຊ້າຍພວກເຮົາກໍາລັງໃຊ້ວົງຈອນນີ້.
ຜົນຜະລິດຂອງພວກເຮົາຈະເປັນ: (0,3), (0,0), (3,0), (3,3)

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ສຳ ລັບ Convex Hull Algorithm

#include <iostream>
using namespace std;
#define INF 10000

struct Point
{
        int x;
        int y;
};

int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);

    if (val == 0)
        return 0;
    return (val > 0) ? 1 : 2;
}

void convexHull(Point points[], int n)
{
    if (n < 3)
        return;
    int next[n];

    for (int i = 0; i < n; i++)
        next[i] = -1;

    int l = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[l].x)
            l = i;

    int p = l, q;
    do
    {
        q = (p + 1) % n;
        for (int i = 0; i < n; i++)
            if (orientation(points[p], points[i], points[q]) == 2)
                q = i;

        next[p] = q;
        p = q;
    }
    while (p != l);

    for (int i = 0; i < n; i++)
    {
        if (next[i] != -1)
            cout << "(" << points[i].x << ", " << points[i].y << ")\n";
    }
}

int main()
{
    Point points[] = { { 0, 3 }, { 2, 2 }, { 1, 1 }, { 2, 1 }, { 3, 0 },
            { 0, 0 }, { 3, 3 } };
    cout << "The points in the convex hull are: ";
    int n = sizeof(points) / sizeof(points[0]);
    convexHull(points, n);
    return 0;
}
The points in the convex hull are: (0, 3)
(3, 0)
(0, 0)
(3, 3)

ໂປແກຼມ Java ສຳ ລັບ Convex Hull Algorithm

import java.util.*;
class Point {

  int x, y;

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

class ConvexHull{

  public static int OrientationMatch(Point check1, Point check2, Point check3) {

    int val = (check2.y - check1.y) * (check3.x - check2.x) - (check2.x - check1.x) * (check3.y - check2.y);

    if (val == 0)
      return 0;

    return (val > 0) ? 1 : 2;
  }

  public static void convex_hull(Point points[], int lengths) {

    if (lengths<3) return;

    Vector<Point> result = new Vector<Point> ();

    int leftmost = 0;

    for (int i = 1; i<lengths; i++)
      if (points[i].x<points[leftmost].x)
        leftmost = i;

    int p = leftmost, pointq;

    do {

      result.add(points[p]);

      pointq = (p + 1) % lengths;

      for (int i = 0; i<lengths; i++) {
        if (OrientationMatch(points[p], points[i], points[pointq]) == 2) {
          pointq = i;
        }
      }
      p = pointq;
    }

    while (p != leftmost);

    System.out.print("The points in the convex hull are: ");
    for (Point temp: result)
      System.out.println("(" + temp.x + ", " + temp.y + ")");

  }

  public static void main(String[] args) {

    Point points[] = new Point[7];
    points[0] = new Point(0, 3);
    points[1] = new Point(2, 3);
    points[2] = new Point(1, 1);
    points[3] = new Point(2, 1);
    points[4] = new Point(3, 0);
    points[5] = new Point(0, 0);
    points[6] = new Point(3, 3);

    int lengths = points.length;
    convex_hull(points, lengths);
  }
}
The points in the convex hull are: (0, 3)
(0, 0)
(3, 0)
(3, 3)

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບ Convex Hull Algorithm

ຄວາມສັບສົນເວລາ

O (m * n) ບ່ອນທີ່ n ແມ່ນຕົວເລກຂອງຈຸດປ້ອນຂໍ້ມູນແລະ m ແມ່ນ ຈຳ ນວນຂອງຈຸດຜົນຜະລິດ.

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ບ່ອນທີ່ n ແມ່ນ ຈຳ ນວນຈຸດເຂົ້າ. ນີ້ພວກເຮົາໃຊ້ອາເລຂະ ໜາດ N ເພື່ອຊອກຫາມູນຄ່າຕໍ່ໄປ.

ກະສານອ້າງອີງ