Introduction
As part of a larger program (related to rendering of volumetric graphics), I have a small but tricky subproblem where an arbitrary (but finite) triangular 2D mesh needs to be labeled in a specific way. Already a while ago I wrote a solution (see below) which was good enough for the test meshes I had at the time, even though I realized that the approach will probably not work very well for every possible mesh that one could think of. Now I have finally encountered a mesh for which the present solution does not perform that well at all -- and it looks like I should come up with a totally different kind of an approach. Unfortunately, it seems that I am not really able to reset my lines of thinking, which is why I thought I'd ask here.
The problem
Consider the picture below. (The colors are not part of the problem; I just added them to improve (?) the visualization. Also the varying edge width is a totally irrelevant artifact.)
For every triangle (e.g., the orange ABC and the green ABD), each of the three edges needs to be given one of two labels, say "0" or "1". There are just two requirements:
- Not all the edges of a triangle can have the same label. In other words, for every triangle there must be two "0"s and one "1", or two "1"s and one "0".
- If an edge is shared by two triangles, it must have the same label for both. In other words, if the edge AB in the picture is labeled "0" for the triangle ABC, it must be labeled "0" for ABD, too.
The mesh is a genuine 2D one, and it is finite: i.e., it does not wrap, and it has a well-defined outer border. Obviously, on the border it is quite easy to satisfy the requirements -- but it gets more difficult inside.
Intuitively, it looks like at least one solution should always exist, even though I cannot prove it. (Usually there are several -- any one of them is enough.)
Current solution
My current solution is a really brute-force one (provided here just for completeness -- feel free to skip this section):
- Maintain four sets of triangles -- one for each possible count (0..3) of edges remaining to be labeled. In the beginning, every triangle is in the set where three edges remain to be labeled.
- For as long as there are triangles with non-labeled edges:
Find the smallest non-zero number of unallocated edges for which there are still triangles left. In other words: at any given time, we try to minimize the number of triangles for which the labeling has been partially completed. The number of edges remaining will be anything between 1 and 3. Then, just pick one such triangle with this specific number of edges remaining to be allocated. For this triangle, do the following:- See if the labeling of any remaining edge is already imposed by the labeling of some other triangle. If so, assign the labels as implied by requirement #2 above.
- If this results in a dead end (i.e., requirement #1 can no more be satisfied for the present triangle), then start over the whole process from the very beginning.
- Allocate any remaining edges as follows:
- If no edges have been labeled so far, assign the first one randomly.
- When one edge already allocated, assign the second one so that it will have the opposite label.
- When two edges allocated: if they have the same label, assign the third one to have the opposite label (obviously); if the two have different labels, assign the third one randomly.
- Update the sets of triangles for the different counts of unallocated edges.
- If we ever get here, then we have a solution -- hooray!
Usually this approach finds a solution within just a couple of iterations, but recently I encountered a mesh for which the algorithm tends to terminate only after one or two thousands of retries... Which obviously suggests that there may be meshes for which it never terminates.
Now, I would love to have a deterministic algorithm that is guaranteed to always find a solution. Computational complexity is not that big an issue, because the meshes are not very large and the labeling basically only has to be done when a new mesh is loaded, which does not happen all the time -- so an algorithm with (for example) exponential complexity ought to be fine, as long as it works. (But of course: the more efficient, the better.)
Thank you for reading this far. Now, any help would be greatly appreciated!
Edit: Results based on suggested solutions
Unfortunately, I cannot get the approach suggested by Dialecticus to work. Maybe I did not get it right... Anyway, consider the following mesh, with the start point indicated by a green dot:
Let's zoom in a little bit...
Now, let's start the algorithm. After the first step, the labeling looks like this (red = "starred paths", blue = "ringed paths"):
So far so good. After the second step:
And the third:
... fourth:
But now we have a problem! Let's do one more round - but please pay attention on the triangle plotted in magenta:
According to my current implementation, all the edges of the magenta triangle are on a ring path, so they should be blue -- which effectively makes this a counterexample. Now maybe I got it wrong somehow... But in any case the two edges that are nearest to the start node obviously cannot be red; and if the third one is labeled red, then it seems that the solution does not really fit the idea anymore.
Btw, here is the data used. Each row represents one edge, and the columns are to be interpreted as follows:
- Index of first node
- Index of second node
- x coordinate of first node
- y coordinate of first node
- x coordinate of second node
- y coordinate of second node
The start node is the one having index 1.
I guess that next I should try the method suggested by Rafał Dowgird... But perhaps I ought to do something completely different for a while :)
