Convex hull generation with C + + implementation

Convex Hull is a concept in computational geometry (graphics), which is simply to say that for a given point set, we need to find a convex polygon to include all the given point sets.

Attach my results first:

As shown in the figure above, a convex polygon connected by green lines is a convex hull, which contains all the points in the point set.

1, Algorithm flow

1. Find out four points that meet the requirements of min(x-y), min(x+y), max(x-y), max(x+y) in the point set, and form a chain list of points according to the counter clockwise (or clockwise) direction. These four points are the closest to the four corners of the circumscribed rectangle containing the discrete points. These four points form a polygon as the initial convex hull.

2. For point I on each convex hull and its subsequent point J, calculate the distance from all points on the right side of vector line IJ to IJ (if clockwise chain list, calculate the point on the left side), and find the point K with the largest distance.

3. If K exists, insert k after I and before J, and assign K to J (that is, update vector segment IJ = IK).

4. Repeat steps 2 and 3 until there is no point on the right side of segment IJ.

5. Assign J to I, take the subsequent points of J, and repeat steps 2, 3 and 4.

6, When there is no discrete point on the right side of any connecting line between two adjacent points in the convex hull, the process of finding the convex hull of the end point set is completed.

 

2, My realization

void ConvexHull::generateHull(Vector<Point> pts)
{
    List<Point> othpts; 
    List<Point> hullpts; //Save the location of the bump point
    for(int i =0; i< pts.size(); i++)
    {
        othpts.push_back(pts[i]);
    }
    //Find out the following four points: min(x-y), min(x+y), max(x-y), max(x+y) and put them into an array in sequence to form the initial convex hull. Here we build a clockwise convex hull
    Sort::quickSort(pts,0,pts.size()-1,cmpXsubY);

    hullpts.push_back(pts[0]);
    hullpts.push_back(pts[pts.size()-1]);
    othpts.removeOne(pts[0]);
    othpts.removeOne(pts[pts.size()-1]);
    Sort::quickSort(pts,0,pts.size()-1,cmpXandY);
    if(!hullpts.contains(pts[0]))
    {
        hullpts.insert(1,pts[0]);
    }
    if(!hullpts.contains(pts[pts.size()-1]))
    {
        hullpts.push_back(pts[pts.size()-1]);
    }
   
    for( int i =0; i< hullpts.size();i++)
    {
        hullpts[i].print();
    }
    othpts.removeOne(pts[0]);
    othpts.removeOne(pts[pts.size()-1]);
    int i = 0;
   

    while(i<hullpts.size())  //Ergodic all convex hull
    {
        Line cline;//A line of convex hull
        if(i == hullpts.size() -1 ) //Last point, connect the first point
        {
            cline.init(hullpts[i],hullpts[0]);
        }else
        {
             cline.init(hullpts[i],hullpts[i+1]);
        }
        float maxdis = 0;
        bool over = true;
        int maxdisIndex = 0;

        for( int m = 0; m< othpts.size(); m++)
        {
            if(IsRightPoint(othpts[m],cline))  //Note here that it should have been on the left, but I used the coordinate system in the screen (y-axis down), so I had to make a conversion
            {
                float dist = PointToLine(othpts[m],cline); //Distance from point to line

                if(dist > maxdis)
                {
                    maxdis = dist;
                    maxdisIndex = m;
                    over =false; //If there's a lateral point, it doesn't end,
                }
            }
        }
        if(over == true) //At the end, the next iteration will find the next line of the convex hull
        {
            i++;
        }else{// No end, the next iteration still starts at point i, but the next point will be updated to the position with the maximum distance from the outside
            hullpts.insert(i+1,othpts[maxdisIndex]);
            over = true;
        }

    }

}

Posted on Wed, 08 Jan 2020 07:35:37 -0800 by chokies12