Поиск параллелограммов

parallel.jpg

Задача: Найти все параллелограммы, которые могут быть построены с тремя вершинами во множестве точек А и одной вершиной в точке C
Использованный API: GTK/GDK;
Среда разработки: Dev-C++

Пусть нам задано множество точек A и точка C. Необходимо найти все параллелограммы, одна из вершин которых - C, а остальные 3 содержатся во множестве A. Для того, чтобы можно было быстрее находить первое вхождение вектора в массиве, а также убирать повторные вхождения в какой-то массив, мы упорядочим векторы и тройки следующим образом:
Упорядочиваем множество векторов следующим образом: если первая координата вектора не равна второй, то упорядочиваем по ней, иначе упорядочиваем по второй координате.
Упорядочим множество троек следующим образом: если наибольший элемент первой тройки не равен наибольшему элемента второй тройки, упорядочиваем по нему, иначе берём следующие по величине элементы и упорядочиваем по ним, а если и они равны, то по наименьшему элементу
Также будем называть тройку хорошей, если ни один элемент в ней не повторяется, а если взять эти вершины в качестве вершин параллелограмма, то получится невырожденный параллелограмм(Вектор c->a1 не параллелен c->a3, значит их координаты не пропорциональны)

Для решения этой задачи с количеством операций, пропорциональным N2 log2 N , где N - количество вершин, будем использовать следующий алгоритм:

1) заполним массив vect, который будет содержать все вектора, которые можно провести между двумя различными точками множества A

// перебираем каждую упорядоченную пару различных точек из A
for(i=0;i<point_cnt;i++)
{
	for(j=0;j<point_cnt;j++)
	{
		if(i==j) continue;
		// добавляем вектор из Aj в Ai {t.l,t.m} в массив vect и запоминаем из какой вершины в какую этот
		// вектор идёт
		t.l=a[j].l-a[i].l;
		t.m=a[j].m-a[i].m;
		t.b=i;
		t.e=j;
		vect[vect_cnt]=t;
		vect_cnt++;
	}
}

2) сортируем полученный массив векторов
3) для каждой вершины из множества A проделаем следующую операцию:
Ищем вектор c->Ai (в массиве vect одинаковые элементы идут подряд, поэтому найдём первое вхождение
двоичным поиском, а дальше будем обрабатывать их подряд). Дальше мы будем перебирать все вектора, начиная с текущего, пока не встретим вектора, не равного искомому, или массив не закончится. В результат будем добавлять все тройки, в которых все 3 числа различные, а если построить параллелограмм на этих вершинах, он не будет вырожден. Первое вхождение вектора находится следующей функцией (количество операций порядка log(N2) ):
int binary_search(vector t)
{
	//l - левая граница интервала поиска, r - правая граница интервала поиска
	//с - середина [l;r] (если l+r не делится на 2, то округляем вниз)
	int l=0,r=vect_cnt-1,c;
	while(l<r)
	{
		c=(l+r)/2;
		if(vector_islesser(&vect[c],&t))
		{
		// если текущий элемент меньше t, то левее будут элементы ещё меньшие,
		// а значит искать будем справа от текущего положения
			l=c+1;
		}
		else
		{
		// если текущий элемент больше или равен t, то значит нужно искать элемент
		// левее текущего положения или в этом положении
			r=c;
		}
	}
	return l;
}

Т.к. точки не повторяются, то, выбрав первую и вторую точки, мы можем N-1 способами выбрать третью, а четвёртая точка может быть выбрана единственным образом: от третей точки отложить вектор "вторая точка->первая точка" (точки нумеруются в порядке обхода вершин параллелограмма). Значит выбрав одну точку, дополнить её остальными точками из A до параллелограмма можно не более чем N способами. Поэтому внутренний цикл будет работать не более N раз
cur_cnt=0;
for(i=0;i<point_cnt;i++)
{
	// составляем вектор t, который будем искать
	t.l=a[i].l-c.l;
	t.m=a[i].m-c.m;
	t.b=-1;
	t.e=-1;
 
	tr.a1=i;
 
	//находим первое вхождение этого вектора в массив
	p=binary_search(t);
	while(p<vect_cnt&&vector_isequal(vect[p],t))
	{
		//идём по массив vect, начиная с p и добавляем каждую "хорошую точку" в результирующий массив
		tr.a2=vect[p].e;
		tr.a3=vect[p].b;
		tr=order(tr);
		if(triple_isgood(tr))
		{
			cur_triple[cur_cnt]=tr;
			cur_cnt++;
		}
		p++;
	}
}

4) уберём повторяющиеся точки из cur_triple и переносим их в массив parallel
// упорядочиваем массив cur_triple, в котором могут быть повторяющиеся тройки
triple_quicksort(cur_cnt-1,cur_triple);
 
if(cur_cnt!=0)
{
	//уберём повторения, перенеся в массив parallel по следующему принципу:
	//1) перенесём первую тройку в ответ
	//2) будем перебирать элементы массива и добавлять в ответ каждую
	//тройку, которая отличается от предыдущей
	cnt=1;
	parallel[0]=cur_triple[0];
	for(i=1;i<cur_cnt;i++)
	{
		if(!triple_isequal(cur_triple[i-1],cur_triple[i]))
		{
			parallel[cnt++]=cur_triple[i];
		}
	}
	parallel_cnt=cnt;
}

В результате работы этого алгоритма массив parallel будет содержать тройки с номерами вершин, которые образуют параллелограммы.
Управление в программе: стрелочка влево - предыдущий параллелограмм, вправо - следующий параллелограмм

ВложениеРазмер
parallel.zip13.49 кб