MarioYC's blog

Live Archive 4116 — Entangled Triangles
By MarioYC, 12 years ago, In English

Link

Hi everyone, today i saw this problem, and since i'm usually not good with 3D geometry, i tried to turn it into a linear algebra problem using barycentric coordinates. So if the vertices of the first triangle are A1, B1, C1 and the vertices of the second triangle are A2, B2, C2, we can represent points inside the first triangle like: A1*w1 + B1*w2 + C1*w3, such that w1+w2+w3 = 1, and we can get a similar equation for points inside the second one: A2*w4 + B2*w5 + C2*w6, such that w4+w5+w6 = 1. We also need 0 <= wi <= 1, for every 1 <= i <= 6. Now we can make an equation for the common points:

A1*w1 + B1*w2 + C1*w3 = A2*w4 + B2*w5 + C2*w6

which is actually two equations, one for X's and another for Y's.

Now we could work with 4 equations and maybe reach some conclusion by looking at the rank of the system of equations. But I don't have and idea about how to deal with the inequalities 0 <= wi <= 1.

Can the problem be solved this way? Anyways I would also be interested in another way to solve, or other problems where barycentric coordinates can be used.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey dude, I'm the geometry guy of the team xD

  1. Let say the triangles are T1 and T2
  2. The triangles are entangled iff exactly one edge of T1 crosses T2 (and viceversa, under the input assumptions).
  3. An edge(3D segment) crosses a triangle iff there is a point P that belongs to the edge and the triangle.
  4. Point P can be found with ternary search since it's also the edge's point with minimum distance to the triangle's plane.
  5. Finally just make sure Point P is inside the triangle:
  • It's distance to the plane should be 0
  • It should be inside the triangle (here we would use barycentric coordinates, 2 eq, 2 incog)
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Then there's no need for ternary search, for each of the sides find the instersection between the line that contains the edge and the plane that contains the other triangle, you do this three times, for each of the points check if any of them is inside the triangle.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, but there should be an if somewhere to check if they actually intersect.

      → Reply