Simplify a convex hull

Question

My problem is as follows: I have a convex hull which could look like this:

I would like to group significantly close points together to be represented by some form of averaging, which could be the mean or median point for example.

I am more so focused on how to do the grouping.

How can I perform this grouping in a systematic way?

I understand this seems like a very simple question and the answer is obvious. My main problem is in attempts to solve this I end up with some corner cases such as the answer will change depending on where I start on the hull. For example if I started from the red line and worked clockwise I would end up with (if I made no attempt to catch the corner case):

I had many attempts at this and every time I rethought my idea I ended up with a new corner case that felt unwieldy. I have a habit of finding the most un-intuitive way to solve a problem so I thought it best to ask the a community. A comparative example to the problem I am having now is I've been asked to find an element in a sorted array and I'm initially performing a linear search and I have a gut feeling there is something better out there.

I could not find exactly what I wanted with my research. I found hull simplifying algorithms but it changed the shape of the hull too much which did not suit the goal of my program.

I will add a note here at the end that I am using OpenCV with C++ to generate a convex hull on a project I am working on. Just in case this is a worth while detail (and why I added OpenCV as a tag).

Answer 1

Consider using Douglas–Peucker algorithm

It is intended to simplify polylines, throwing out less important points.

Thanks Berriel for addition: it is implemented in OpenCV: approxPolyDP