phantom11's blog

Convex Hull!!Is there a better approach
By phantom11, 12 years ago, In English

I was reading convex hull for the first time from CLRS.I thought for another algorithm that would work in O(n) time.I tested it for many test cases and it works fine.Can anyone point out flaws in the algorithm or support it.(Sorry for my bad english)
Lokesh-Scan(Points P)
{
 1.find the leftmost,rightmost,uppermost and lowermost points.In case of ties take the lower-left and upper    right most points;//Since these points are the corner ones they have to be in the hull/
2.Join the above mentioned points;//i.e include them in the hull
3.Now treat the four lines as reference axes individually.i.e if suppose p1,p2,p3,p4 are the lower,right,upper and left points respectively then firstly take p2 as origin and the line p2->p1 as the positive x-axis.If there are any points in the 1st quadrant of this axis system, include the one which has the maximum positive height from the axis in the hull.
4.Do this for all the four lines.(p2->p1,p3->p2,p4->p3 and p1->p4)
}
This algorithm (if correct) works in O(n) time.Line 1 takes O(n) time and line 3 takes O(n) time..
I hope I have made myself clear.Looking for your replies......

  • Vote: I like it
  • -10
  • Vote: I do not like it

12 years ago, # |
  Vote: I like it +19 Vote: I do not like it
6
0 4
4 0
8 4
4 8
1 2
1 1

1 2 is not in the hull.
→ Reply
  • 12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Sorry for that ,I forgot to write to choose the point which is of maximum height from the respective axis...Then your case is solved
    → Reply
12 years ago, # |
  Vote: I like it +13 Vote: I do not like it
Think of the following idea - proper convex hull algorithm should be "isotropic" - independent of rotation by any angle - while your algorithm looks very anisotropic. Why for example you are searching only for 4 bordering lines, and not enclose points set into triangle or hexagon? Only because it was simpler for you... ;-)

Keep such questions in mind next time you invent any algorithm. Try to answer them yourself. Try to answer "why nobody except me invented such a great idea" yourself... And who knows, maybe you once really invent something really new.

However you described your idea well so it is easy to understand you. It is very important ability - so I give "plus" to your post.
→ Reply
  • 12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I cannot get what you wanted to say in the first paragraph, but anyways the main motive of the convex hull algorithm is"the smallest convex polygon P for which each point is either on boundary or on its interior"...which my algorithm does (supposed) as after choosing the boundary points it looks for points which may go out of the hull if we draw a line segment joining the boundary points ...If there is a point then it puts the point which is farthest from the line segment thus enclosing all points...
    → Reply
    • 12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Imagine your algorithm working against set representing regular dodecagon.

      If there is a point then it puts the point which is farthest from the line segment thus enclosing all points...

      It could appear that there is two such points - neither of them could complete convex hull alone. Read the second example kindly presented by Ivan.

      About first paragraph. I told that proper algorithm should be independent of "leftmost/rightmost" etc points. Algorithm should give the same convex hull if you rotate your set by 45 degrees, for example. In case of your algorithm it is not so - you could get different results for the same set, if it is rotated. It lead us to the conclusion that algorithm could not be correct.
      → Reply
      • 12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        Ok got it....Thanks man!!! Your comments cleared my doubts
        → Reply
12 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

The idea is ok, it's an incomplete version of the QuickHull algorithm. 


QuickHull, from [1]
"The idea behind QuickHull is to discard points that are not on the hull as quickly as possible. QuickHull begins by computing the points with the maximum and minimum, x- and y-coordinates. Clearly these points must be on the hull. Horizontal and vertical lines passing through these points are support lines for the hull, and so define a bounding rectangle, within which the hull is contained. Furthermore, the convex quadrilateral defined by these four points lies within the convex hull, so the points lying within this quadrilateral can be eliminated from further consideration. All of this can be done in O(n) time.

To continue the algorithm, we classify the remaining points into the four corner triangles that remain. In general, as this algorithm executes, we will have an inner convex polygon, and associated with each edge we have a set of points that lie “outside” of that edge. (More formally, these points are witnesses to the fact that this edge is not on the convex hull, because they lie outside the half-plane defined by this edge.) When this set of points is empty, the edge is a final edge of the hull. Consider some edge ab. Assume that the points that lie “outside” of this hull edge have been placed in a bucket that is associated with ab. Our job is to find a point c among these points that lies on the hull, discard the points in the triangle abc, and split the remaining points into two subsets, those that lie outside ac and those than lie outside of cb. We can classify each point by making two orientation tests.

How should c be selected? There are a number of possible selection criteria that one might think of. The method that is most often proposed is to let c be the point that maximizes the perpendicular distance from the line ab."

Your algorithm is missing the part that I marked in bold, you should repeat until no point is found.
A variation of the algorithm is to just start with two extreme points except of four, and do the same, as shown in this gif:


Here is an image showing when your algorithm fails:

In red is the initial quadrilateral of the extreme points, then, when searching for the point with "max height" from the line (top-most, right-most), you miss a point. At this moment, you should repeat the algorithm for the new lines (in blue).

[1] Search for QuickHull in this article for more information:
→ Reply
  • 12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks Diego....So the changes in the algorithm should be:
    *After 1 eliminate all points in the interior of the hull.
    *Then do step 3 with the idea of elimination i.e. after choosing the reference line (say with p2->p1) 3.1 Find the point (pk)that is farthest from the axes system and in its first quadrant.
    3.2 Join p2,p1 and pk to form a triangle.Eliminate all points in the interior of this triangle.
    3.3 Put pk in the hull.
    3.4 If there are still points remaining in this quadrant repeat 3.1

    4.Do step 3 for all 4 reference lines

    The problem remains to implement it and calculate its complexity.Please help me with this because I dont know how to find the number of points within a triangle

    → Reply
    • 12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      The main problem is that with "repeat 3.1" this algorithm would not remain O(n). You can read links or search google for complexity. I think it is about O(n*log(n)), all the same... :-)
      → Reply
    • 12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      O(n*n) if all points belong to the hull.
      → Reply