Re^2: Contour mapping?

I'd be curious whether the triangles evince some relevant property, like (maybe): no XY coordinate is contained within any such triangle, or the XY plane is fully covered without overlap by the set of triangles

The triangles are a non-overlapping mesh (Delaunay or complient Delaunay Trangulation); the data is from a Finite Element Modeling program.

And yes; I'm also pretty sure the triangles are the key. Having played a little with my stratification idea; it is clear that it is going no where -- producing a tangled web of string rather than nice flowing contours.

This is what I now think I need to do:

Starting with a simple triangular mesh of points, with the heights at the nodes:

                                             /4\
                                           /  |  \
                                         /    |   \
                                       /      |      \
                                     /        |        \
                                   /          |          \
                                 /            |            \
                               /              |              \
                             /                |                \
                           /                  |                  \
                         /                    |                    \
                        3--------------------6.5--------------------5
                       /|\                    |                    /| 
+\
                     /  |  \                  |                  /  | 
+  \
                   /    |    \                |                /    | 
+    \
                 /      |      \              |              /      | 
+      \
               /        |        \            |            /        | 
+        \
             /          |          \          |          /          | 
+          \
           /            |            \        |        /            | 
+            \
         /              |              \      |   .  /              | 
+              \
       /                |                \    |    /                | 
+                \
     /                  |                  \  |  /      .           | 
+                  \
   /                    |                    \|/                    | 
+                    \
  2--------------------5.5--------------------9--------------------7.5
+---------------------6
   \                    |                    /|\                    | 
+                    /
     \                  |                  /  |  \                  | 
+                  /
       \                |                /    |    \                | 
+                /
         \              |              /      |  .   \              | 
+              /
           \            |            /        |        \            | 
+            /
             \          |          /          |          \          | 
+          /
               \        |        /            |            \        | 
+        /
                 \      |      /              |              \      | 
+      /
                   \    |    /                |                \    | 
+    /
                     \  |  /                  |                  \  | 
+  /
                       \|/                    |                    \| 
+/
                        3--------------------6.5--------------------6
                         \                    |                    / 
                           \                  |                  / 
                             \                |                / 
                               \              |              / 
                                 \            |            / 
                                   \          |          /
                                     \        |        /
                                       \      |      /
                                         \    |    /
                                           \  |  /
                                             \4/
[download]

I pick my contour values -- integers 3 to 8 are convenient for this examples -- and process the edges of the triangles linearly (being careful not to process edges twice where they are part of two triangles), and interpolate the positions on those edges where any of my chosen contour values will cross.

Eg. On the edge between value 2 and 5.5, I find the positions are which 3, 4, 5 cross that edge; and store those coordinates in separate arrays for each value. I end up with something as below:

                                             /4\
                                           /  |  \
                                         /    |   \
                                       /      |      \
                                     /        |        \
                                   /          5          \
                                 /            |            \
                               /              |              \
                             /                |                \
                           /                  6                  \
                         /                    |                    \
                        3-----4------5-----6-6.5-----6--------------5
                       /|\                    |                    /| 
+\
                     /  |  4                  |                  /  | 
+  \
                   /    |    \                7                6    | 
+    \
                 /      |      5              |              /      | 
+      \
               /        4        \            |            /        6 
+        \
             /          |          6          |          7          | 
+          \
           /            |            \        8        /            | 
+            \
         /              |              7      |   .  /              | 
+              \
       /                5                \    |   8                 | 
+                \
     /                  |                  8  |  /      .           7 
+                  \
   /                    |                    \|/                    | 
+                    \
  2-----3------4----5 -5.5--6-----7-----8-----9-------------8------7.5
+------7--------------6
   \                    |                    /|\                    | 
+                    /
     \                  |                  8  |  \                  | 
+                  /
       \                5                /    |    \                | 
+                /
         \              |              7      |  .   \              7 
+              /
           \            |            /        8        8            | 
+            /
             \          |          6          |          \          | 
+          /
               \        4        /            |            \        | 
+        /
                 \      |      5              |              \      | 
+      /
                   \    |    /                7                7    | 
+    /
                     \  |  4                  |                  \  | 
+  /
                       \|/                    |                    \| 
+/
                        3-----4------5-----6-6.5--------------------6
                         \                    |                    / 
                           \                  |                  / 
                             \                6                / 
                               \              |              / 
                                 \            |            / 
                                   \          |          5
                                     \        5        /
                                       \      |      /
                                         \    |    /
                                           \  |  /
                                             \4/
[download]

Then it just a case of ordering those arrays of points to produce the polylines that make up the contours something like this:

                                            

                                             /4\
                                           / *|  \
                                         /  * |   \
                                       /   *  |      \
                                     /   *    |        \
                                   /   *      5          \
                                 /   *      * |  *         \
                               /    *     *   |     *        \
                             /    *      *    |        *       \
                           /     *     *      6*           *     \
                         /     *      *     * |   *             *  \
                        3-----4------5-----6-6.5-----6--------------5
                       /|\   *      *     *   |        *           /|\
                     / *|  4      *      *    |           *      /  | 
+ \
                   /  * | *  \  *      *     *7 *            * 6    | 
+   \
                 /  *   |*     5      *     * |     *        /   ** | 
+     \
               /   *    4     *  \  *      *  |        *   /        6 
+       \
             /    *    *|   *      6     *    |          7*         | 
+ *       \
           /    *     * | *      *   \  *     8        /     *      | 
+    *      \
         /    *      *  |*      *      7     *| * .  /          *   | 
+       *     \
       /    *      *    5      *      *  \  * |   8               * | 
+          *   \
     /     *      *   * |     *     *      8  |  /   *  .           7 
+*            *   \
   /     *      *    *  |    *     *      *  \|/         *          | 
+   *            *  \
  2-----3------4----5 -5.5--6-----7-----8-----9-------------8------7.5
+------7--------------6
   \     *      *    *  |    *     *     *   /|\           *        | 
+    *              * 
     \     *     *    * |     *      *     8  |  \        *         | 
+  *              * 
       \    *     *     5      *      *  /  * |    \     *          | 
+*              * 
         \    *     *   |*      *      7     *|  .   \  *           7 
+             * 
           \    *    *  |  *     *   /  *     8********8           *| 
+           * 
             \    *    *|    *    *6     *    |          \        * | 
+         * 
               \    *   4     *  /  *     *   |            \     *  | 
+       * 
                 \   *  |*     5      *     * |              \  *   | 
+     * 
                   \  * | *  /   *      *     7****************7    | 
+   * 
                     \ *|  4       *     *    |                  \  | 
+ * 
                       \|/  *       *     *   |                    \|*
+ 
                        3-----4------5-----6-6.5--------6.25--------6
                         \     *      *     * |               ***  / 
                           \    *       *    *|         ***      / 
                             \    *       *   6  ***           / 
                               \   *       *  |              / 
                                 \   *      * |            / 
                                   \   *     *|       * *5
                                     \  *     5 *  *   /
                                       \  *   |      /
                                         \  * |    /
                                           \ *|  /
                                             \4/
[download]

I don't have a full handle on the ordering process; but I've a few ideas to try. (Actually, I don't need to order them to do the intersections with the boundaries; though it might be nice to draw the contours to see that they are correct before going on.)

Then all I have to do :) is work out which of those contours intersect the polylines that form the boundaries and work out where and at what angle they intersect.

And then I can start on trying to collate the results in a way that is meaningful...the driving force behind the whole problem.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)

In the absence of evidence, opinion is indistinguishable from prejudice.

Comment on Re^2: Contour mapping? Select or Download Code

Replies are listed 'Best First'.
Re^3: Contour mapping? by graff (Chancellor) on Apr 28, 2016 at 07:02 UTC
Wow. I'd say don't worry about ordering (until later). Take one triangle at a time, and look at its three edges in whatever sequence is given. If one edge crosses a given whole-number Z value, then exactly one other edge in that triangle will cross that same value, so you'll get exactly one iso-contour line segment per whole-number Z per triangle, and its position and angle in the overall XY coordinate space can be worked out. While a single vertex (XY point) can be shared among a variable number of triangles (2 to ...8? 9?), a given vertex pair (i.e. an edge) will appear in at most two triangles. (Edges appearing in only one triangle define the outer boundary of the XY plane being charted.) Putting those two things together, as you march through each triangle, watch for the case where you come to an edge you've seen before (of course, its end points will be presented in opposite order, relative to the first time you saw this edge). If you've already seen it, you already know if it crosses any whole-number Z value(s), and you have the coordinates of the end points for that iso-contour line in the adjacent (previously done) triangle. When you find the other edge(s) of the current triangle crossing the same whole-number Z value(s) -- these also may be edges you've seen before -- you have what you need to maintain a linked list of the nodes for the given iso-contour line, in addition to knowing the position and angle of each line segment. For 2.4 million vertices (how many triangles?), it's a lot to keep track of, but it seems like just a matter of looping over triangles, and for each of those, looping over edges, keeping track of the edges you've done, and keeping a properly indexed list of iso-contour line segments as they come up, so that you know when you encounter each interior edge the second time, and can traverse the connections of linked contour lines. Regarding that first point above, the logical possibilities are: None of the three edges contain a whole-number Z value One or more of the vertices is itself a whole-number Z value An edge contains just one whole-number Z value, so that value appears on one other edge (or may be the at the opposite vertex) An edge contains two or more whole-number Z values; either all those values will also appear on one other edge, or else they'll be divvied up among the other two edges (or one of them may be at the opposite vertex) I hope you have a generous schedule (and are getting paid enough) for doing this. Sounds like a lot of work. (updated wording in a couple bullet points)	[reply]
Re^4: Contour mapping? by pryrt (Abbot) on Apr 28, 2016 at 13:24 UTC
I think this is going in a better direction than my suggestion. Regarding ordering: If you find edges that appear in only one triangle (a boundary edge), then any contour line that intersects that edge will "start" or "end" there. You can then traverse it to the other edge/vertex of that first triangle; that other edge will be shared with a new triangle, and so forth, for a continuous line in the proper order. It will get a bit more complicated when you hit a vertex instead of an edge for that contour, because then you have to try a couple of adjacent triangles to see which direction the contour flows... but in general, it's pretty straightforward Keep track of all the triangles you've processed for a given contour height as you're going Keep going until you reach another edge (or until you find a second intersection with a triangle you've already hit (for example, if the contour line were shaped like a number 9) If you don't have any "start" edges for a given contour height, you can just start at any edge/vertex that crosses the height under question, and start another contour loop/line from there. For a given contour height, you may have more than one starting point (like my two-island example), or if you've got a Y-shaped contour going off to the edges. So after you've ended one loop or line, check to see if there are any other edges/vertexes that you haven't processed yet that cross through your given height, and start again. Once you've used all the edges/vertexes that go thru a given height, move on to the next height. Those triangles ended up being a lot more help than I originally thought they would (++graff). Very interesting discussion, and I'll have to store away some of these concepts if I ever need the details of the contours, rather than just being able to visually see them.	[reply]