5
$\begingroup$

I have a 2D set and would like to determine from them the subset of points which, if joined together with lines, would result in an edge below which none of the points in the set exist.

This problem resembles the convex hull problem, but is fundamentally different in its definition.

One approach to determine these points might be to evaluate the cross-product of only x_1, x_2 and x_3, where x_1 is on the 'hull', x_2's 'hull'-ness is being evaluated and x_3 is another point on the set (all other points in the set should yield positive cross products if x_2 is indeed on the hull), with the additional constraint that x_1 < x_2 in one dimension.

I realize that this algorithm is not entirely perfect; the plot below shows that some valid points would be missed as a result of the convex hull constraint. How else can I define this edge?

Hope the question is clear.

Example plot

  • 0
    @Cristia$n$ : I am after a polygonal arc here.2011-06-05

1 Answers 1

4

It looks like you are looking for the lower [convex] hull. Some algorithms such as the Andrew's variant of Graham Scan actually compute this and compute the upper hull and then merge these two to obtain the convex hull. Andrew's algorithm can also be seen as a sweep algorithm, so if you want a quick implementation, you could just a vertical sweep algorithm (see the Wiki link for details).