Smallest Convex polygon around point

1
votes

I got a bunch of 2d points. What I'm trying to find is the smallest polygon around (created from minimal set of points that fully enclose) one specific point. I tried to use convex hull and Voronoi but none of them produce the results I'm looking for and I'm running out of ideas...

What I want is to find are the lines (in red) that represent the smallest convex polygon around a point (in green) as demonstrated on the image below:

enter image description here

Another example:

enter image description here

Any code, suggestions, or known algorithm would be greatly appreciated...

1
c++calgorithmmath
Are there any restrictions in terms of how many vertices the polygon can have? By "smallest" you mean surface and not circumference, right? Oh, and how is this problem related to c++ or c? – Jerome Reinländer
by "the smallest polygon" do you mean, the polygon with the smallest area or the polygon with the smallest number of points, or something else? – Eziz Durdyyev
That should be on Software Engineering section – Ollaw
@McBob So is it not always 3 or impossible? In the first example i can see a polygon that contains the green point with only 3 vertices ... – Fantastic Mr Fox
In your first example, there is a triangle of black points that contain the green point, although it looks like its area is larger than the red quadrilateral you drew. But you have stated that you are looking for the fewest number of vertices, so the example is wrong. – Ian Abbott

1 Answers

0
votes

Start from any black point in your diagram, let's call it A. Draw the line from point A to the green point G. Now draw the line from point A to any other point A1, A2,... . If in a clockwise sense, this line is after line AG, ignore it. From all other lines choose the one that forms the smallest angle with line AG. Now move point A to the next point. Repeat until you are visiting a point for the second time.