קאַנוועקס כאַל אַלגערידאַם


שוועריקייט לעוועל מיטל
אָפט געבעטן אין דזשיאַמעטריק מאָרגאַן סטאַנלי סאַמסונג

אין פּראָבלעם "קאַנוועקס כאַל אַלגערידאַם" מיר האָבן געגעבן אַ סכום פון עטלעכע פונקטן. דער קלענסטער פילעק וואָס קענען זיין געשאפן מיט די ווייזט וואָס כּולל אַלע אנדערע פונקטן ין עס וועט זיין גערופֿן זייַן קאַנוועקס כאַל.

קאַנוועקס כאַל אַלגערידאַם

דעם קענען זיין אַטשיווד דורך ניצן דזשאַרוויס אַלגאָריטהם.

אַלגאָריטהם

  1. יניטיאַליזירן די פונט פון די לינקס לינקס צו 0.
  2. דערקלערן א וועקטאָר געהייסן רעזולטאַט פון פּוינט טיפּ
  3. אַריבער די ווייזט כייפעץ מענגע ביז די פאָרמאָוסט לינקס פונט איז געפונען
  4. לייג דעם פונט צו די רעזולטאַט וועקטאָר
  5. געפֿינען די ווייַטער פונט "Q" אַזאַ אַז עס איז די מערסט קאַונטערקלאָקווייז פונט אַוועק אַלע אנדערע פונקטן
  6. שטעלן פּ צו פונט "Q" פֿאַר דער ווייַטער יטעראַטיאָן.
  7. האַלטן אַדינג אַרויף בשעת "P" איז נישט גלייך צום לינקן.

באַשרייַבונג

דער הויפּט געדאַנק צו סאָלווע די קאַנוועקס כאַל איז צו נוצן אָריענטירונג. מיר וועלן געפֿינען און אָנהייבן מיט די לינקס אָדער די לאָואַסט X קאָואָרדאַנאַט. און מיר קענען נעמען עס ביז אַלע אונדזער ווייזט זענען געפֿונען אין וואָס אַ סכום פון עטלעכע ווייזט קענען אָנקלייַבן.

מיר וועלן פאָרן די אָבדזשעקט מענגע פונקטן פון באַניצער סאָרט פונט, וואָס מיר שוין דעפינירן אין די אָנהייב פון די קאָד. אונדזער אַרגומענטן פון ווייזט און לענגקטס פון די גאַנץ נומער זענען דורכגעגאנגען אין די קאַנוועקס כאַל פונקציאָנירן, וווּ מיר וועלן דערקלערן די וועקטאָר געהייסן רעזולטאַט אין וואָס מיר וועלן צו קראָם אונדזער פּראָדוקציע.

איניציאליזירן דעם לינקער פונט צו 0. מיר וועלן אָנהייבן עס פון 0, אויב מיר באַקומען די פונט וואָס האט די לאָואַסט רענטגענ קאָואָרדאַנאַט אָדער די לינקס לינקס פונט מיר וועלן טוישן עס.

איצט אַריבער אַלע די פונקטן און געפֿינען די לאָואַסט. סטאָר די פּאָזיציע פון ​​די לינקס לינקס צו "P" און דערקלערן אַ פונט

איצט, אָנהייב אַ שלייף אין וואָס דער ערשטער זאַך מיר טאָן איז צו לייגן די ערשטער פונט ווי אַ רעזולטאַט.

איצט מיר האָבן צו געפֿינען די מערסט קאַונטערקלאָקווייז פונט צו אַלע אנדערע ווייזט. פֿאַר דעם, מיר וועלן נוצן אָריענטירונג. מיר געמאכט אַ באַזונדער פונקציע פֿאַר דעם, וואָס קאָנטראָלירן אויב די אָריענטירונג פון טריפּלאַץ איז 2 אָדער נישט אויב עס איז געפֿונען צו זיין 2, דערהייַנטיקן די ווערט פון פונט "Q".

דעם זאָל זיין געצויגן אַרויף ביז די "P" איז נישט גלייך צום לינקן.

בייַשפּיל

די פונקטן זענען:

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

לעפטמאָסט = 0;

נאָך דורכפאָר אַלע די ווייזט, אונדזער ערשטער לאָואַסט רענטגענ קאָואָרדאַנאַט וועט זיין (0,3).
איצט עס איז צו קאָנטראָלירן וואָס x, y פּאָר האט רובֿ קאַונטערקלאָקווייז ווייַל עס וועט געבן אָריענטירונג ווי 2 און דערהייַנטיקן די ווערט פון פונט "Q".
פּאָר צו געפֿינען ווי (0,0).
איצט, נאָכמאַכן די ווערט פון פונט "Q" אין פּ ווי אַ ווייַטער פונט פֿאַר ווידער דערגייונג די מערסט קאַונטערקלאָקווייז פונט.
ביז די ווערט פון פּ איז נישט גלייַך צו די לעפטמאָסט, מיר וועלן נוצן דעם שלייף.
אונדזער פּראָדוקציע וועט זיין: (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)

Java פּראָגראַם פֿאַר קאַנוועקס כאַל אַלגערידאַם

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 צו געפֿינען די ווייַטער ווערט.

דערמאָנען