 |
|
| Science Forum Index » Mathematics Forum » Creating a nicely directed triangular net |
|
Page 1 of 1 |
|
| Author |
Message |
| Toni Lassila |
 Posted: Fri Mar 04, 2005 9:47 am |
|
|
|
Guest
|
Assume an arbitrary polygon, dissected into a finite triangular net
with no hanging nodes. Then assign for each triangle T a direction of
traversal r(T), either clockwise (1) or anti-clockwise (-1), meaning
that the edges of the triangle must be traversed in that direction.
Under which conditions (for the net) can we assign the directions to
each triangle s.t. for any two adjacent triangles their common edge is
always traversed in the same direction for both triangles? In other
words, if two triangles are adjacent then their directions of
traversal are opposite, r(T1) = - r(T2).
--
"I'm not interested in mathematics that might have anything
to do with reality." -- Russell Easterly, in sci.math |
|
|
| Back to top |
|
|
|
| Keith A. Lewis |
| Posted: Fri Mar 04, 2005 9:47 am |
|
|
|
Guest
|
Toni Lassila <toni@nukespam.org> writes in article <6isg21hohko3d2t5vrlucvtn3g8mqj4qts@no.spam> dated Fri, 04 Mar 2005 16:47:03 +0200:
[quote:8291cee5ad]Assume an arbitrary polygon, dissected into a finite triangular net
with no hanging nodes. Then assign for each triangle T a direction of
traversal r(T), either clockwise (1) or anti-clockwise (-1), meaning
that the edges of the triangle must be traversed in that direction.
Under which conditions (for the net) can we assign the directions to
each triangle s.t. for any two adjacent triangles their common edge is
always traversed in the same direction for both triangles? In other
words, if two triangles are adjacent then their directions of
traversal are opposite, r(T1) = - r(T2).
[/quote:8291cee5ad]
You can do this if one triangle touches ("touch" meaning sharing an edge,
not just a point) only 1 other triangle and no triangle touches more than 2.
For example, you can dissect a convex polygon with all triangles sharing a
common vertex, then traverse the odd-numbered ones clockwise and the evens
counterclockwise.
The more general condition is that you must be able to partition the set of
triangles into 2 sets such that no 2 members of the same set touch each
other. But that doesn't go much beyond your original problem statement.
--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer. |
|
|
| Back to top |
|
|
|
| W. Dale Hall |
| Posted: Fri Mar 04, 2005 2:27 pm |
|
|
|
Guest
|
Toni Lassila wrote:
[quote:166586e6bd]Assume an arbitrary polygon, dissected into a finite triangular net
with no hanging nodes. Then assign for each triangle T a direction of
traversal r(T), either clockwise (1) or anti-clockwise (-1), meaning
that the edges of the triangle must be traversed in that direction.
Under which conditions (for the net) can we assign the directions to
each triangle s.t. for any two adjacent triangles their common edge is
always traversed in the same direction for both triangles? In other
words, if two triangles are adjacent then their directions of
traversal are opposite, r(T1) = - r(T2).
[/quote:166586e6bd]
I would imagine that you can form the dual graph (i.e., dual to the
triangulation. This is a graph formed by taking a vertex for each
triangle, and join vertices when two triangles share an edge: it can
be visualized by taking the centroids of the triangles, and drawing
lines from centroid to centroid, across the common edges). If you
find that all its cycles are even, then such an assignment could
be had. That is, starting at some given node N (of the dual graph, so N
is really a triangle in the triangulation), define r(N) = +1, and for
each node M, set r(M) = (-1)^d, where d is the length (= number of
edges) of a path from N to M. The evenness of all cycles forces the
number (-1)^d to be well-defined, since any two paths joining the same
endpoints differ by a cycle, and thus have the same number of edges
modulo 2.
The condition on the dual graph appears to be difficult to visualize,
so here's something that I think is equivalent:
If the polygon is simply-connected, then it may be sufficient that
each interior vertex of the triangulation have even degree, since in
the dual graph, this translates to the condition that the group of
cycles is generated by elements each having an even number of edges.
This, in turn, appears to force evenness of all cycles (I mean I think
I have a proof, but haven't hammered out the details; I'm assuming
that a proof can be fashioned).
If your polygon is not simply-connected, then the triangulation will
require, in addition to the above interior vertex condition, a further
one: take any hole (i.e., any component of the complement of the polygon
in the plane), and consider a chain of adjacent triangles that loops
around that hole. Any such chain must have an even number of triangles.
Actually, if the interior vertex condition is met (and assuming it's
correct that this implies the even-cycle condition on the dual graph),
the existence of one such even chain around each hole (that is, a
separate even chain around each individual hole) is sufficient.
Dale. |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Fri Dec 04, 2009 4:08 pm
|
|