ኮንቬክስ ሃል አልጎሪዝም


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ ጂዮሜትራዊ ሞርጋን ስታንሊ ሳምሰንግ

በችግር ላይ “ኮንቬክስ ሃል አልጎሪዝም” የተወሰኑ ነጥቦችን ስብስብ ሰጥተናል ፡፡ በውስጣቸው ያሉትን ሌሎች ነጥቦችን በሙሉ ከያዙ ከነዚያ ነጥቦች ጋር ሊፈጠር የሚችል ትንሹ ፖሊጎን “ኮንቬክስ” ተብሎ ይጠራል ፡፡

ኮንቬክስ ሃል አልጎሪዝም

ይህንን በመጠቀም ማግኘት ይቻላል የጃርቪስ አልጎሪዝም.

አልጎሪዝም

  1. የግራ ጫፍን ወደ 0 ያስጀምሩ ፡፡
  2. ያውጅ ሀ ቬክተር የነጥብ ዓይነት የተሰየመ
  3. የፊተኛው ግራ ነጥብ እስኪገኝ ድረስ የነጥቦችን ነገር ድርድር ይጓዙ
  4. ያንን ነጥብ ወደ ውጤቱ ቬክተር ያክሉ
  5. ቀጣዩን ነጥብ ይፈልጉ "Q" ከሌሎቹ ነጥቦች ሁሉ በተቃራኒ ሰዓት አቅጣጫ ነው
  6. ወደ ነጥቡ ያቀናብሩ "Q" ለቀጣይ ድግግሞሽ.
  7. እየደመሩ ይቀጥሉ "ፒ" ከግራ ወደ ግራ እኩል አይደለም ፡፡

መግለጫ

ስለዚህ የ “ኮንቬክስ” ን ለመቅረፍ ዋናው ሀሳባችን አቅጣጫን መጠቀም ነው ፡፡ ከግራ ወይም ምናልባትም ዝቅተኛውን የ X ማስተባበሪያ ለማግኘት እና እንጀምራለን ፡፡ የአንዳንድ ነጥቦች ስብስብ ሊከማች በሚችልበት ሁሉም ነጥቦቻችን እስኪገኙ ድረስ ልንወስድ እንችላለን ፡፡

በኮዱ መጀመሪያ ላይ እኛ የምንገልፀውን የተጠቃሚ ክፍል ነጥብን የነጥብ ድርድር ነጥቦችን እናልፋለን ፡፡ የነጥቦቻችን እና የቁጥሩ ርዝመት ክርክሮቻችን ወደ ኮንቬክስ እቅፍ ተላልፈዋል ሥራ፣ ምርታችንን የምናከማችበትን ቬክተር የተሰየመበትን ውጤት እናሳውቃለን ፡፡

አሁን የግራውን ጫፍ ወደ 0. ያስጀምሩ እኛ ዝቅተኛው x አስተባባሪ ወይም የምንለውጠው የግራ ጫፍ ያለው ነጥብ ካገኘን ከ 0 ልንጀምር ነው ፡፡

አሁን ሁሉንም ነጥቦች አቋርጠው ዝቅተኛውን ይፈልጉ ፡፡ የግራውን አቀማመጥ ወደ ላይ ያከማቹ "ፒ" እና አንድ ነጥብ ያውጁ

አሁን ፣ እኛ የምናደርገው የመጀመሪያ ነገር እንደ መጀመሪያው ነጥብ እንደ መጀመሪያው ነጥብ የሚጨምርበትን ጊዜ-ጊዜን ሉፕ ይጀምሩ ፡፡

አሁን ወደ ሁሉም ሌሎች ነጥቦች በጣም በተቃራኒ ሰዓት አቅጣጫ መፈለግ አለብን ፣ ለዚህም እኛ አቅጣጫን እንጠቀማለን ፡፡ እኛ ለዚህ የተለየ ተግባር አደረግን ፣ ይህም የሶስትዮሽ አቅጣጫ 2 መሆን አለመሆኑን ያረጋግጣል ወይም 2 ሆኖ ከተገኘ የነጥቡን ዋጋ ያዘምኑ "Q".

ይህ እስከሚቀጥለው ድረስ መቀጠል አለበት "ፒ" ከግራ ወደ ግራ እኩል አይደለም ፡፡

ለምሳሌ

የተሰጡት ነጥቦች-

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

በግራ በኩል = 0;

ሁሉንም ነጥቦች ካለፍን በኋላ የመጀመሪያው ዝቅተኛው x አስተባባሪችን (0,3) ይሆናል በዚህም ምክንያት ያከማቻል።
አሁን የትኛው እንደሆነ ለማጣራት ነው x, y ጥንድ እንደ 2 አቅጣጫን ስለሚሰጥ እና የነጥብ ዋጋን የሚያሻሽል በመሆኑ በተቃራኒ ሰዓት አቅጣጫ በተቃራኒ ሰዓት አቅጣጫ አለው "Q".
ጥንድ እንደ (0,0) ሆኖ ይገኝ ፡፡
አሁን የነጥብ ዋጋን ይቅዱ "Q" በጣም በተቃራኒ ሰዓት አቅጣጫ እንደገና ለመፈለግ ወደ ቀጣዩ ነጥብ ወደ p.
የፒ እሴት ከግራው ጋር እኩል እስካልሆነ ድረስ ይህንን ዑደት እንጠቀማለን።
የእኛ ውጤት ይሆናል: (0,3), (0,0), (3,0), (3,3)

አፈጻጸም

የ C ++ ፕሮግራም ለ ‹ኮንቬክስ ሃል አልጎሪዝም›

#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)

የጃቫ ፕሮግራም ለ “ኮንቬክስ ሃል አልጎሪዝም”

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)

የኮንቬክስ ሃል አልጎሪዝም ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (m * n) የት n የግቤት ነጥቦች ቁጥር እና m የውጤት ነጥቦች ብዛት ነው ፡፡

የቦታ ውስብስብነት

ሆይ (n) የት n የመግቢያ ነጥቦች ቁጥር ነው ፡፡ የሚቀጥለውን እሴት ለማግኘት እዚህ የመጠን መጠንን N እንጠቀማለን ፡፡

ማጣቀሻ