layers.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#include "balls.h"

static vector<Collision> completeGraph(vector<Ball *> balls);
static vector<Collision> matching(vector<Collision> edges);
static vector<Collision> diff(vector<Collision> a, vector<Collision> b);

vector<vector<Collision>>
partitionCollisions(vector<Ball *> balls) {
	vector<vector<Collision>> layers;

	vector<Collision> collisions = completeGraph(balls);
	while (!collisions.empty()) {
		cout << "\nadd layer\n";
		cout << "layers.size(): " << layers.size() << "\n";

		vector<Collision> layerCollisions = matching(collisions);
		cout << "layer collisions: ";
		for (Collision c : layerCollisions)
			cout << c << " ";
		cout << "\n";
		collisions = diff(collisions, layerCollisions);

		vector<Collision> thisLayer;
		for (Collision c : layerCollisions) {
			cout << "create node with " << c << "\n";
			thisLayer.push_back(c);
		}
		cout << "thisLayer.size(): " << thisLayer.size() << "\n";
		layers.push_back(thisLayer);
	}
	return layers;
}

static vector<Collision>
completeGraph(vector<Ball *> balls) {
	vector<Collision> edges;
	size_t i, j;

	for (i = 0; i < balls.size(); i++)
		for (j = i+1; j < balls.size(); j++)
			edges.push_back(Collision(balls.at(i), balls.at(j)));
	return edges;
}

static vector<Collision>
matching(vector<Collision> edges) {
	vector<Collision> matching;
	size_t i;

	for (Collision e : edges) {
		for (i = 0; i < matching.size(); i++)
			if (e.b1 == matching[i].b1 || e.b1 == matching[i].b2 || e.b2 == matching[i].b1 || e.b2 == matching[i].b2)
				break;
		if (i == matching.size()) /* no shared vertices */
			matching.push_back(e);
	}
	return matching;
}

static vector<Collision>
diff(vector<Collision> a, vector<Collision> b) {
	vector<Collision> diff;
	set_difference(a.begin(), a.end(),
		b.begin(), b.end(),
		inserter(diff, diff.begin()));
	return diff;
}