CODEWITHSUNDEEP
javac++openglvertexconvex-hull
Slymodi
Slymodi

Reputation: 195

Finding the minimum bounding box of a convex hull

Let's say that I have a n sided convex hull, now how do I get the Right/Left Top/Bottom corners of said convex hull, now let's say that maybe N is 3 and the triangle coordinates are 0,0 50,0 0,50 or something else, we know what the corners are and that 0,50 counts as both the Right top and left, so is there some way to get this rather than what I have here, where Left_Bottom and so on are vectors and values is a vector array

    Left_Bottom = values[0];
    Left_Top = values[0];
    Right_Bottom = values[0];
    Right_Top = values[0];
    for (int i = 1; i < values.length; i++) {
        if (!Left_Bottom.XisLess(values[i])) {
            if (Left_Bottom.YisLess(values[i])) {
                Left_Bottom = values[i];
            }
        }

        if (!Left_Top.XisLess(values[i])) {
            if (!Left_Top.YisLess(values[i])) {
                Left_Top = values[i];
            }
        }

        if (Right_Bottom.XisLess(values[i])) {
            if (Right_Bottom.YisLess(values[i])) {
                Right_Bottom = values[i];
            }
        }

        if (Right_Top.XisLess(values[i])) {
            if (!Right_Top.YisLess(values[i])) {
                Right_Top = values[i];
            }
        }
    }

Upvotes: 3

Views: 4858

Answers (1)

herohuyongtao
herohuyongtao

Reputation: 50667

  1. If you are looking for the problem of finding the convex hull of a finite set of points, take a look at here. You can find several solutions to do this in O(n*log n)

enter image description here

  1. If you are just looking for the four corners of the bounding rectangle of this convex hull, actually you are looking for minimum bounding box for the convex hull.

    • If the bounding box is parallel to the coordinate axes, just find the min_x, min_y, max_x and max_y among all these convex hull points. Then the four corners (clockwisely) are:

      1. (min_x, min_y)

      2. (max_x, min_y)

      3. (max_x, max_y)

      4. (min_x, max_y)

enter image description here

  • If the bounding box is not parallel to the coordinate axes, this becomes complex. Check out the references introduced in here and here for the implementation.

enter image description here

Upvotes: 2

Related Questions