How do I find if two triangles are adjacent, when they differ in size?

Say I have triangles as shown:

Its easy to see that ABC is adjacent to ACJ: ABC and ACJ share 2 vertices (A and C).

However FEC and ACJ are also adjacent, but only one vertex is shared.

How can I find if two triangles are adjacent when they differ in size?

-
Are the points given as coordinates? – J. M. Sep 5 '10 at 22:12
Sure! You have all the information in this diagram. – bobobobo Sep 5 '10 at 23:03
Hmm... just to make sure we understand each other: the points A, B, ... are represented as Cartesian coordinates in your application? – J. M. Sep 5 '10 at 23:14
Lets say that yes, the points A, B .. are 3-space Cartesian coordinates. Is there another way you might prefer to represent them? – bobobobo Sep 6 '10 at 13:17

First, we need a definition of "adjacent plane figures". If we take "plane figure" to mean a closed plane curve (the boundary) along with its interior, then one definition might be that two plane figures are adjacent when (a) the intersection of their boundaries is a curve but not a point; (b) their interiors are disjoint. For polygons (boundaries consist of line segments) any subtle topological issues disappear, so this will certainly do for triangles.

Given this, then I think it's probably not too hard to prove this hypothesis:

Theorem: Triangles ABC and DEF are adjacent iff all of these hold:

(a) At least one side of ABC (say AB) and one side of DEF (say DE) are identical as lines (not line segments).

(b) At least one of A and B is strictly between D and E, or at least one of D and E is strictly between A and B.

(c) C and F are on different sides of line AB (which is the same as line DE).

The nice thing about this theorem, if true, is that it should not be hard to come up with a simple algorithm to test for adjacency in the Cartesian plane. I suspect the image processing folks have done this and much much more along the same lines.

Here are some of the trickier cases...

-

To find all adjacent triangles to ACJ for ex, my first stab at this is to consider all triangles that share at least one vertex with ACJ.

So, ACJ shares one vertex with ADF and FEC (adjacent because an entire side is shared). It also shares one vertex with HBA and BIC (not adjacent because they don't share a side).

So, for two triangle t1 and t2 to be adjacent then:

• At least one vertex must be shared between the two triangles t1 and t2;
• At least one vertex other than the shared vertex from t2 must fall on a line that is drawn between the shared vertex and an unshared vertex on t1.

So for t1=ACJ and t2=FEC, FEC is adjacent to ACJ because:

• C is shared between ACJ and FEC
• F (from t2) falls on the line between C and A (from t1).

Thus ACJ and FEC are adjacent.

-
Are there any other answers? – bobobobo Sep 5 '10 at 19:42

I'm not so sure about this, but if you considered vectors FC and AC, the triangles are adjacent iff there exists some $x\in\mathbb{R}$ such that $FC = x(AC)$, and every point in AC as well as FC is contained in $L:X=\lambda(A-C)+Q$ given any $Q\in FC$.

-