Orthogonal hull algorithm

Question

I am trying to find a way to determine the rectilinear polygon from a set of integer points (indicated by the red dots in the pictures below). The image below shows what I would like to achieve:

1.

I need only the minimal set of points that define the boundary of the rectilinear polygon. Most hull algorithms I can find do not satisfy the orthogonal nature of this problem, such as the gift-wrapping algorithm, which produce the following result (which is not what I want)...

2.

How can I get the set of points that defines the boundary shown in image 1.?

Updated:

Figure 1. is no longer refereed to as convex..

Answer 1

Following the definition from wikipedia, it is rather easy to create a fast algorithm.

1. Start constructing upper hull from the leftmost point (uppermost among such if there are many). Add this point to a list.
2. Find the next point: among all the points with both coordinates strictly greater than of the current point, choose the one with minimal x coordinate. Add this point to your list and continue from it.
3. Continue adding points in step 2 as long as you can.
4. Repeat the same from the rightmost point (uppermost among such), but going to the left. I.e. each time choose the next point with greater y, less x, and difference in x must be minimal.
5. Merge the two lists you got from steps 3 and 4, you got upper hull.
6. Do the same steps 1-5 for lower hull analogously.
7. Merge the upper and lower hulls found at steps 5 and 6.

In order to find the next point quickly, just sort your points by x coordinate. For example, when building the very first right-up chain, you sort by x increasing. Then iterate over all points. For each point check if its y coordinate is greater than the current value. If yes, add the point to the list and make it current.

Overall complexity would be O(N log N) for sorting.

EDIT: The description above only shows how to trace the main vertices of the hull. If you want to have a full rectilinear polygon (with line segments between consecutive points), then you have to add an additional point to your chain each time you find next point. For example, when building the right-up chain, if you find a point (x2, y2) from the current point (x1, y1), you have to add (x2, y1) and (x2, y2) to the current chain list (in this order).

Answer 2

I think what you want to compute is the Rectilinear Convex Hull (or Orthogonal Convex Hull) of the set of points. The rectilinear convex hull is an ortho-convex shape, that is, the intersection of the shape with any horizontal or vertical line results in an empty set, a point, or a line segment.

The vertices of the rectilinear convex hull are the set of maximal points under vector dominance. The rectilinear convex hull can then be computed in optimal O(n log n) time. A very simple algorithm is presented in Preparata's book on Computational Geometry (see the section 4.1.3).