Как объединить произвольное множество полигонов?

Question

[Валерий Осипов]

Есть несколько полигонов, которые могут быть объединены в один.
Выглядят они примерно так:

Полигоны выбирает оператор, так, что полигоны выбираются в случайном порядке — главная моя проблема проблема, определение следующего участка при объединении

Для двух полигонов я написал такой код

public List<Point2d> CombinePolylinePoints(List<Point2d> points1, List<Point2d> points2)
{
	var borderPoints = new List<Point2d>();
	for (int i = 0; i < points1.Count; i++)
	{
		if (points2.Contains(points1[i]))
		{
			Debug.WriteLine("Точка с индексом " + i + " - граничная");
			borderPoints.Add(points1[i]);
		}
	}
	if (borderPoints.Count < 2)
		return new List<Point2d>();
	// проходим по первому полигону?
	var goingFirstParcel = true;
	int iFirst = 0;
	int iSecond = 0;
	Point2d nextPoint = default(Point2d);
	var points = new List<Point2d>();
	while (nextPoint != points1[0])
	{

		if (goingFirstParcel)
		{
			Debug.WriteLine("Идем по первому участку..");
			var currPoint = points1[iFirst];
			points.Add(currPoint);
			if (borderPoints.Any(p => p.IsEqualTo(currPoint, Tolerance.Global)))
			{
				Debug.WriteLine("Текущая точка - граничная. Переходим на второй участок");
				goingFirstParcel = false;

				iSecond = points2.IndexOf(currPoint);
				if (iSecond == -1)
				{
					MessageBox.Show("IndexOf returned 0");
					return null;
				}
				iSecond++;
				if (iSecond >= points2.Count)
					iSecond = 0;
				Debug.WriteLine("iSecond = " + iSecond);
				nextPoint = points2[iSecond];
				continue;
			}
			iFirst++;
			if (iFirst >= points1.Count) iFirst = 0;
			nextPoint = points1[iFirst];
		}
		else if (!goingFirstParcel)
		{
			Debug.WriteLine("Идем по второму участку..");
			var currPoint = points2[iSecond];
			points.Add(currPoint);
			if (borderPoints.Any(p => p.IsEqualTo(currPoint, Tolerance.Global)))
			{
				Debug.WriteLine("Текущая точка - граничная. Переходим на первый участок");
				goingFirstParcel = true;
				iFirst = points1.IndexOf(currPoint);
				if (iFirst == -1)
				{
					MessageBox.Show("IndexOf iFirst returned 0");
					return null;
				}
				iFirst++;
				if (iFirst >= points1.Count)
					iFirst = 0;
				Debug.WriteLine("iFirst = " + iFirst);
				nextPoint = points1[iFirst];
				continue;
			}
			iSecond++;
			if (iSecond >= points2.Count) iSecond = 0;
			nextPoint = points2[iSecond];
		}
	}
	return points;
}

Вкратце:

1. ищем граничные точки
2. идем по первому участку, добавляя в список все точки
3. если текущая точка граничная, переходим на следующую точку второго участка
4. переходим на п.2, до тех пор пока следующая точка не станет первой точкой первого участка

Но для произвольного множества полигонов написать не получается — на некоторых тестовых данных, доходя до развилки (точка, общая для 3 и более участков) алгоритм идет по неправильному пути и зацикливается на нем.

Вопрос: как выбрать на какой полигон переходить на развилке?

Answer 1

[TheEternal]

Рекурсивно не получится?
Берем произвольный полигон и любой, который к нему прилегает. Объединяем их по приведенному выше алгоритму.
Повторяем.