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.
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:
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.)
My current solution is a really brute-force one (provided here just for completeness -- feel free to skip this section):
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!
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:
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 :)
Boundary edges are only referenced by a single triangle in the mesh, so to find them you need to scan through all triangles in the mesh and take the edges with a single reference count. You can do this efficiently (in O(N) ) by making use of a hash table.
Many graphics software packages and hardware devices can operate more efficiently on triangles that are grouped into meshes than on a similar number of triangles that are presented individually. This is typically because computer graphics do operations on the vertices at the corners of triangles.
If you order the triangles so that for every triangle at most 2 of its neighbors precede it in the order, then you are set: just color them in this order. The condition guarantees that for each triangle being colored you will always have at least one uncolored edge whose color you can choose so that the condition is satisfied.
Such an order exists and can be constructed the following way:
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With