குவிந்த ஹல் அல்காரிதம்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது வடிவியல் மோர்கன் ஸ்டான்லி சாம்சங்

சிக்கலில் “குவிந்த ஹல் அல்காரிதம்” நாங்கள் சில புள்ளிகளின் தொகுப்பைக் கொடுத்துள்ளோம். அதன் உள்ளே மற்ற எல்லா புள்ளிகளையும் கொண்டிருக்கும் அந்த புள்ளிகளுடன் உருவாக்கக்கூடிய மிகச்சிறிய பலகோணம் அதன் குவிந்த ஹல் என்று அழைக்கப்படும்.

குவிந்த ஹல் அல்காரிதம்

பயன்படுத்துவதன் மூலம் இதை அடைய முடியும் ஜார்விஸ் அல்காரிதம்.

அல்காரிதம்

  1. இடதுபுற புள்ளியை 0 ஆகத் தொடங்கவும்.
  2. ஒரு அறிவிக்கவும் திசையன் புள்ளி வகையின் பெயரிடப்பட்ட முடிவு
  3. முதன்மையான இடது புள்ளி காணப்படும் வரை புள்ளிகள் பொருள் வரிசைக்கு பயணிக்கவும்
  4. முடிவு திசையனில் அந்த புள்ளியைச் சேர்க்கவும்
  5. அடுத்த புள்ளியைக் கண்டறியவும் "கே" இது மற்ற எல்லா புள்ளிகளிலிருந்தும் மிகவும் எதிரெதிர் திசையில் உள்ளது
  6. புள்ளிக்கு p ஐ அமைக்கவும் "கே" அடுத்த மறு செய்கைக்கு.
  7. சேர்க்கும்போது தொடர்ந்து சேர்க்கவும் "பி" இடதுபுறத்திற்கு சமமாக இல்லை.

விளக்கம்

எனவே குவிந்த ஹல் தீர்க்க எங்கள் முக்கிய யோசனை நோக்குநிலை பயன்படுத்த வேண்டும். நாம் இடதுபுறத்தில் அல்லது மிகக் குறைந்த எக்ஸ் ஒருங்கிணைப்பைக் கண்டுபிடித்து தொடங்கப் போகிறோம். எங்கள் எல்லா புள்ளிகளும் காணப்படும் வரை நாம் அதை எடுத்துக் கொள்ளலாம், அதில் சில புள்ளிகளின் தொகுப்பு குவிந்துவிடும்.

பயனர் வகுப்பு புள்ளியின் பொருள் வரிசை புள்ளிகளை நாம் அனுப்பப் போகிறோம், அதை குறியீட்டின் தொடக்கத்தில் ஏற்கனவே வரையறுத்துள்ளோம். புள்ளிகள் மற்றும் முழு எண்ணின் நீளம் பற்றிய எங்கள் வாதங்கள் குவிந்த ஓல் வழியாக அனுப்பப்படுகின்றன செயல்பாடு, எங்களுடைய வெளியீட்டை சேமிக்கப் போகிற திசையன் என பெயரிடப்பட்ட முடிவை அறிவிப்போம்.

இப்போது இடதுபுற புள்ளியை 0 க்கு துவக்கவும். மிகக் குறைந்த x ஒருங்கிணைப்பைக் கொண்ட புள்ளி அல்லது இடதுபுற புள்ளியைப் பெற்றால் அதை 0 இலிருந்து தொடங்கப் போகிறோம்.

இப்போது எல்லா புள்ளிகளையும் கடந்து மிகக் குறைந்த ஒன்றைக் கண்டறியவும். இடப்பக்கத்தின் நிலையை சேமிக்கவும் "பி" ஒரு புள்ளியை அறிவிக்கவும்

இப்போது, ​​ஒரு செய்ய வேண்டிய சுழற்சியைத் தொடங்கவும், அதில் நாம் செய்யப்போகும் முதல் விஷயம் முதல் புள்ளியை வெளியீடாகச் சேர்ப்பதாகும்.

இப்போது நாம் மற்ற எல்லா புள்ளிகளுக்கும் மிகவும் எதிரெதிர் திசையில் கண்டுபிடிக்க வேண்டும், இதற்காக, நாம் நோக்குநிலையைப் பயன்படுத்தப் போகிறோம். இதற்காக நாங்கள் ஒரு தனி செயல்பாட்டைச் செய்துள்ளோம், இது மும்மூர்த்திகளின் நோக்குநிலை 2 ஆக இருக்கிறதா இல்லையா என்பதைச் சரிபார்க்கிறது, அது 2 எனக் கண்டறியப்பட்டால், புள்ளியின் மதிப்பைப் புதுப்பிக்கவும் "கே".

இது வரை தொடர வேண்டும் "பி" இடதுபுறத்திற்கு சமமாக இல்லை.

உதாரணமாக

கொடுக்கப்பட்ட புள்ளிகள்:

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

leftmost = 0;

எல்லா புள்ளிகளையும் கடந்து சென்ற பிறகு, எங்கள் முதல் மிகக் குறைந்த x ஒருங்கிணைப்பு (0,3) ஆக இருக்கும், இதன் விளைவாக அது சேமிக்கப்படும்.
இப்போது அது எது என்பதை சரிபார்க்கப் போகிறது x, y ஜோடி மிகவும் எதிரெதிர் திசையில் உள்ளது, ஏனெனில் இது நோக்குநிலையை 2 ஆகக் கொடுக்கும் மற்றும் புள்ளியின் மதிப்பைப் புதுப்பிக்கும் "கே".
(0,0) எனக் காண வேண்டிய ஜோடி.
இப்போது, ​​புள்ளியின் மதிப்பை நகலெடுக்கவும் "கே" மிகவும் எதிரெதிர் திசையில் மீண்டும் கண்டுபிடிப்பதற்கான அடுத்த புள்ளியாக p க்குள்.
P இன் மதிப்பு இடதுபுறத்திற்கு சமமாக இல்லாத வரை நாம் இந்த வளையத்தைப் பயன்படுத்தப் போகிறோம்.
எங்கள் வெளியீடு: (0,3), (0,0), (3,0), (3,3)

நடைமுறைப்படுத்தல்

குவிந்த ஹல் அல்காரிதத்திற்கான சி ++ நிரல்

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

குவிந்த ஹல் அல்காரிதத்திற்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (மீ * என்) n என்பது உள்ளீட்டு புள்ளிகளின் எண்ணிக்கை மற்றும் m என்பது வெளியீட்டு புள்ளிகளின் எண்ணிக்கை.

விண்வெளி சிக்கலானது

ஓ (n) n என்பது உள்ளீட்டு புள்ளிகளின் எண்ணிக்கை. அடுத்த மதிப்பைக் கண்டுபிடிக்க இங்கே நாம் N அளவு வரிசையைப் பயன்படுத்துகிறோம்.

குறிப்பு