Хорошо, поэтому то, что вы ищете, это оболочка con cave вместо выпуклого корпуса. В отличие от выпуклой оболочки, которая имеет только одно решение для любого заданного множества точек, вогнутый корпус имеет множество решений и множество способов их достижения. Двумя наиболее распространенными подходами являются альфа-формы или триангуляция Делоне , а из двух я рекомендую триангуляцию.
Коротким объяснением триангуляции Делоне является создание треугольной сетки из множества точек, так что минимальный внутренний угол любого заданного треугольника как можно больше. Существует много существующих библиотек, которые могут создать для вас триангуляцию Delauney. (Самый рекомендуемый - Triangle.NET ).
Когда у вас есть триангуляция, выполняемая в вашем наборе точек, вы практически отбрасываете информацию о треугольниках для всех сторон, которые разделяются между двумя треугольниками. Это оставляет вам только стороны, которые являются эксклюзивными для одного треугольника, который соответствует периметру многоугольника:
(Кредит Тимоти Шилдс по этому вопросу за изображение.)
Когда у вас есть этот граф ребер, вы можете просто пересечь их (переходя от края к подключенному узлу к соединенному ребру и т. Д.), Чтобы получить массив точек, определяющих ваш вогнутый корпус:
(Псевдокод)
public Point[] GetPolyFromEdgeGraph(Edge[] edges)
{
List<Point> poly = new List<Point>();
Edge edge = edges[0];
Point start = edge.PointA;
Point point = start;
do
{
poly.Add(point);
edge = point.EdgeA != edge ? point.EdgeA : point.EdgeB;
point = edge.PointA != point ? edge.PointA : edge.PointB;
} while (point != start);
return poly.ToArray();
}