I have been working on a two dimensional Divide and Conquer algorithm written in c++, a language I am rather new to. I used this page to base my algorithm on. The Y-axis is inverted in my example images.
I create a grid with a chosen width and height. The program then selects a random coordinate within each cell, these are the points for the Delaunay Triangulation.
The algorithm works as follows
Sort the coordinates in ascending order on the x-axis (similar x values; sort on y)
Divide into subgroups, until each group contains no more than 3 coordinates. Connect each coordinate with a line (I call them 'Edges'). This is in a binary tree structure. The Leaves contain a vector of these edges.
Recursively merge the leaves upwards
- # Select the starting edge: select the coordinates, L and R, with the lowest y value from the left and right subgroup. If the edge L-R does not intersect with any edges of either group: select that edge. Else, select the next coordinate. (If the L-R edge intersects with an edge from the left subgroup select the next left coordinate. Ditto with the right group)
- Based on the starting edge ('base' in my code) select the next candidate from both groups, left_C and right_C (the following is the left subgroup selection process, the right subgroup is the same but only mirrored):
- Select the neighboring coordinates: all coordinates that have a direct connection to the base edge
- Sort the neighbors by increasing clockwise angles.
- @ The candidate selection process: Select first (i = 0) coordinate as the candidate C, the second (i + 1) as the next candidate nC.
- Check if the angle between the L-R and C is bigger than 180° or pi. If so: no candidate is selected, else move on to the next condition.
- & Check if, the nC is within the circumcircle defined by triangle L-R-C (distance between circumcircle center and nC < radius circumcircle). delete the edge defined by L-C. nC becomes the new candidate C, the candidate with the next highest angle becomes nC, repeat check.
- return candidate at the position i
- If neither left nor right groups return a candidate, then the merge is complete.
- Else if only one group returns a candidate, obviously that is the to-be-used candidate
- Else both subgroups return a candidate, then select the candidate where the circumcircle defined by it and the base edge does not contain the other.
- A triangle is created using the selected candidate and the base edge: an edge is created between the candidate and base-coordinate from the other subgroup ( eg. candidate of the left-subgroup: R-left_C ). This becomes the base edge for the next iteration.
- iterate until the merge is complete (neither subgroup offers a candidate)
And so the tree is merged recursively.
So TL;DR.
The issue that I am having is two steps of the D&C algorithm coming into conflict. the two are the selection of the starting base edge (see step #) and the selection of the candidate coordinates (see step @ and &)
The bug (read: feature) occurs with this orientation of the subgroups:
Animated Gif
It skips one of the coordinates of the right group in the first merger. This is because the algorithm specifies that you take the lowest y values of both groups that do not intersect with any other edges as the base edge. Then all the right group candidates, which are attached to the base edge, are selected with their counter-clockwise angle, the left with the clockwise angles. This skips one coordinate. leading to the following result.
I have no idea how to solve this.
Here is my code:
triangulate():
Node* Branch::triangulate() {
if (l != nullptr && r == nullptr) {
return l;
}
else {
// recursive merge
Node* left = l->triangulate();
Node* right = r->triangulate();
vector<Edge> left_edges = left->getEdges();
vector<Edge> right_edges = right->getEdges();
Edge base = selectBase(left_edges, right_edges);
bool merge = true;
vector<Edge> mergedEdges;
vector<Edge> newEdges;
newEdges.push_back(base);
while (merge) {
Coordinate left_candidate = selectCandidateFromSubgroup(left_edges, base, true);
Coordinate right_candidate = selectCandidateFromSubgroup(right_edges, base, false);
Coordinate null(DBL_MIN, DBL_MIN);
if (left_candidate == null && right_candidate == null) {
merge = false;
}
else {
Edge new_base;
if (right_candidate == null) {
new_base = Edge(left_candidate, *base.p2());
}
else if (left_candidate == null) {
new_base = Edge(*base.p1(), right_candidate);
}
else {
double left_a, left_b, left_c,
base_a, base_b, base_c;
functionFromEdge(base, base_a, base_b, base_c);
Edge left_edge(left_candidate, *base.p2());
functionFromEdge(left_edge, left_a, left_b, left_c);
perpendicularBisector(base, base_a, base_b, base_c);
perpendicularBisector(left_edge, left_a, left_b, left_c);
Coordinate left_circumcircle_center = intersection(left_a, left_b, left_c,
base_a, base_b, base_c);
new_base = (Coordinate::distance(left_circumcircle_center, left_candidate)
< Coordinate::distance(left_circumcircle_center, right_candidate))
? left_edge : Edge(*base.p1(), right_candidate);
}
newEdges.push_back(new_base);
base = new_base;
}
}
mergedEdges.reserve(newEdges.size() + left_edges.size() + right_edges.size());
for (Edge e : left_edges) {
mergedEdges.push_back(e);
}
for (Edge e : right_edges) {
mergedEdges.push_back(e);
}
for (Edge e : newEdges) {
mergedEdges.push_back(e);
}
return new Leaf(mergedEdges,i);
}
}
selectBase():
vector<Coordinate> left_points = extractCoordinates(left);
vector<Coordinate> right_points = extractCoordinates(right);
Edge* out = nullptr;
bool found = false;
int i = 0;
int j = 0;
while (!found) {
Coordinate l = left_points.at(i), r = right_points.at(j);
Edge base(l, r);
out = &base;
for (Edge e : left) {
if (out!= nullptr && e.intersects(base)) {
//cout << e << " intersects with " << *out << " i++" << endl;
i++;
out = nullptr;
}
if (out != nullptr && left_points.size() ==2 && (*e.p1() == *base.p1() || *e.p2() == *base.p1())) {
Coordinate other = (*e.p1() == *base.p1()) ? *e.p2() : *e.p1();
if (Angle::calcClockAngle(l, r, other, true).rad() > M_PI) {
out = nullptr; i++;
}
}
}
for (Edge e : right) {
if (out != nullptr && e.intersects(base)) {
//cout << e << " intersects with " << *out << " j++" << endl;
j++;
out = nullptr;
}
if (out != nullptr && right_points.size() == 2 && (*e.p1() == *base.p2() || *e.p2() == *base.p2())) {
Coordinate other = (*e.p1() == *base.p2()) ? *e.p2() : *e.p1();
if (Angle::calcClockAngle(r, l, other, false).rad() > M_PI) {
out = nullptr; j++;
}
}
}
if (out != nullptr) found = true;
}
return Edge(left_points.at(i), right_points.at(j));
}
In the above function I tried to make a check that checks if there is a skipped point, by checking in subgroups of size 2 if there is an angle larger than pi.
It worked for smaller groups. But the issue still occurs.
selectCandidateFromSubgroup:
Coordinate selectCandidateFromSubgroup(vector<Edge>& es, Edge& base, bool left) {
// select neighboring edges from base
Coordinate* shared_point = (left)? base.p1() : base.p2();
Coordinate* other_point = (left)? base.p2() : base.p1();
vector<Coordinate> candidates;
for (Edge e : es) {
if (*shared_point == *e.p2() || *shared_point == *e.p1()) {
Coordinate c = (*shared_point == *e.p2()) ? *e.p1() : *e.p2();
candidates.push_back(c);
}
}
if (candidates.size() != 0) {
algorithm::quicksort(candidates, 0, candidates.size() -1,
[&shared_point,&other_point,&left](Coordinate a, Coordinate b) {
double angle = Angle::calcClockAngle(*shared_point, *other_point, a, left).getDegrees();
double angle2 = Angle::calcClockAngle(*shared_point, *other_point, b, left).getDegrees();
return (angle < angle2 || (angle == angle2 && a.y() < b.y()));
});
double base_a, base_b, base_c;
functionFromEdge(base, base_a, base_b, base_c);
perpendicularBisector(base, base_a, base_b, base_c);
Coordinate* candidate=nullptr;
Coordinate* next_candidate = nullptr;
int i = 0;
bool checking_candidates = true;
while (checking_candidates) {
candidate = &candidates.at(i);
double angle = Angle::calcClockAngle(*shared_point,
*other_point,
*candidate,
left).rad();
if (angle < M_PI) {
Edge candidate_edge;
int cei = 0;
int j = 0;
for (Edge e : es) {
if ((*e.p1() == *shared_point && *e.p2() == *candidate) || (*e.p2() == *shared_point && *e.p1() == *candidate)) {
candidate_edge = e;
cei = j;
break;
}
j++;
}
if (i + 1 == candidates.size()) return *candidate;
next_candidate= &candidates.at(i+1);
double candidate_edge_a, candidate_edge_b, candidate_edge_c;
functionFromEdge(candidate_edge, candidate_edge_a,
candidate_edge_b, candidate_edge_c);
perpendicularBisector(candidate_edge, candidate_edge_a,
candidate_edge_b, candidate_edge_c);
Coordinate circumcicle_center = intersection(base_a, base_b, base_c,
candidate_edge_a, candidate_edge_b, candidate_edge_c);
double radius = Coordinate::distance(circumcicle_center, *shared_point);
double distance_center_nCandidate = Coordinate::distance(circumcicle_center, *next_candidate);
if (radius < distance_center_nCandidate) {
return *candidate;
}
else {
i++;
es.erase(es.begin() + cei);
}
}
else {
return Coordinate(DBL_MIN, DBL_MIN);
}
}
}
return Coordinate(DBL_MIN, DBL_MIN);
}
extractCoordinates(vector) extracts and sorts all coordiates on the y axis ascendingly.
functionFromEdge(Edge,double a,double b,double c) takes an edge and makes a functional representation of the lines like 'ax+by=c', which is used by
perpendicularBisector(Edge, double a, double b, double c) converts the a, b, and c values to represent the function of the perpendicular bisector of the Edge so that the algorithm can calulate the
intersection(double a1, double b1, double c1, double a2, double b2, double c2) of two functions.
the calcClockAngle(Coordinate a, Coordinate b, Coordinate c, bool clockwise) calulates the angle in a bewteen the vectors |AB| and |AC|, depending on the clockwise boolean, it calculates the cloclwise or counter clockwise angle.
If I forgot something please let me know.
Sorry for the long question. but I am seriously at a loss here.
I get results like this:
