I just had to write a function that seemed simple to write, but when I actually did it, it turned out way gorier than I had expected. It's really bugging me, I feel like there's a better solution, but my brain is going crazy trying to think of it, so therefore I'm turning to you fine folks.
Basically, I have 2 triangles, and I want to know if they share a common edge. The triangles are indexed by their vertices (i.e. their vertices is just an index to an array containing the actual coordinates), so it comes down to finding if two sets of three numbers have two numbers in common. I.e. triangles (1,2,3) and (3,1,5) do share an edge, the (1,3) edge. However, triangles (1,2,3) and (1,5,6) does not share an edge (only a vertex) and neither does (1,2,3) and (4,5,6).
How would you write this "two numbers in common function"? You can assume all values inside each set are distinct (i.e. (1, 1, 2) is not going to be an input) and you can also assume that two sets don't equal each other (i.e. I'm not going to compare (1,2,3) and (1,3,2), because those two are the same triangle). However, no assumptions can be made regarding order, they are not sorted or anything like that.
This is basically what I came up with (assuming the sets are (x0, x1, x2) and (y0, y1, y2)):
// If the x0 is equal to any of (y0, y1, y2), make sure at least one of (x1, x2)
// is equal to one of the y numbers
if (x0 == y0) {
return x1 == y1 || x1 == y2 || x2 == y1 || x2 == y2;
} else if (x0 == y1) {
return x1 == y0 || x1 == y2 || x2 == y0 || x2 == y2;
} else if (x0 == y2) {
return x1 == y0 || x1 == y1 || x2 == y0 || x2 == y1;
} else {
// if x0 is not equal to any of (y0, y1, y2), then x1 and x2 both have
// to be equal to two of the y numbers.
return (x1 == y0 && x2 == y1)
|| (x1 == y0 && x2 == y2)
|| (x1 == y1 && x2 == y0)
|| (x1 == y1 && x2 == y2)
|| (x1 == y2 && x2 == y0)
|| (x1 == y2 && x2 == y1);
}
but it feels so gory to me! So many branches and such long boolean statements! I feel like i'm missing an obvious easy solution, and it's driving me insane.
In addition, this happens in an inner loop in a very performance sensitive application, so performance (branching, arithmetic, whatever) matters.
BTW, the code I'm writing is C#, but the question is the same in more or less any imperative language.
EDIT:
I put together a quick benchmark (here's the code) with the suggestions so far. Here are the results (running it at a million random pairs of triangles):
Original method result: 7035, time elapsed in ms: 8.6252
qwertyman method result: 7035, time elapsed in ms: 8.2537
midjji method result: 7035, time elapsed in ms: 8.7984
Single HashSet method result: 7035, time elapsed in ms: 184.4984
Many HashSets method result: 7035, time elapsed in ms: 190.5785
The numbers remain fairly consistent run to run, with @qwertyman's method always being a bit faster than my original version or @midjii's. It also has the advantage of being the cleanest and nicest of them all, so I'm going to go with that one.
I was actually a bit surprised that the "Many HashSets" was so close to "Single HashSet", I would have thought constructing a million HashSets would have a bigger overhead than around 16 milliseconds (though this obviously doesn't count the increased pressure on the garbage collector), though they're both obviously far behind the other methods.
Thanks for the help!