Test if line segments are part of a triangle

Question

This looks simple, but I can't figure it out. I want an algorithm that will determine if three line segments are part of a triangle.

• If the line segments form a triangle the answer should be True.
• If one can get a triangle by extending one or more line segment, the answer should be True.
• If some portion of one or more line segment would not be part of the triangle, the answer should be False.

The line segments in my first example are part of a triangle:

lines1 = Line[{{{3.4, 3}, {3, 0}}, {{3, 0}, {5, 0.2}}, {{5, 0.2}, {4.2, 5}}}];
Graphics[lines1, ImageSize -> {150, 150}]

The lines in the next two examples are not part of a triangle:

lines2 = Line[{{{0, 0.8}, {3, 0}}, {{3, 0}, {5, 0.2}}, {{5, 0.2}, {8, 3}}}];
Graphics[lines2, ImageSize -> {150, 150}]

lines3 = Line[{{{3.4, 2}, {3, 0}}, {{3, 0}, {5, 0.2}}, {{5, 0.2}, {6, -3}}}];
Graphics[lines3, ImageSize -> {150, 150}]

Answer 1

Using an angle calculation function (anglecalc) to measure the angle between two vectors. With closedQ to check whether the lines will converge to a triangle.

anglecalc[u_, v_] := Mod[(ArcTan @@ v) - (ArcTan @@ u), 2 Pi]

closedQ[lines_] := Module[{a, b, c, d, e, f},
  {{c, d}, {e, f}} = #1 - #2 & @@@ Partition[lines, 2, 1];
  {a, b} = anglecalc[##] 180/Pi & @@@ {{-d, c}, {-f, e}};
  a + b < 180 || a + b > 540]

Mapping closedQ over the OP's lines.

lines1 = {{{3.4, 3}, {3, 0}}, {{3, 0}, {5, 0.2}}, {{5, 0.2}, {4.2, 5}}};
lines2 = {{{0, 0.8}, {3, 0}}, {{3, 0}, {5, 0.2}}, {{5, 0.2}, {8, 3}}};
lines3 = {{{3.4, 2}, {3, 0}}, {{3, 0}, {5, 0.2}}, {{5, 0.2}, {6, -3}}};

closedQ /@ {lines1, lines2, lines3}

{True, False, False}

How it works

anglecalc finds the clockwise angle from v to u.

x = lines3[[{1, 2}]]
Graphics[Line[x], ImageSize -> 150]
{u, v} = lines3[[1]] - lines3[[2]]
anglecalc[u, v] 180/Pi

{u, v}

{{0.4, 2}, {-2, -0.2}}

Answer 2

Here is a fast and simple solution.

The infinite lines extending any given line segments will always create a triangle on a plane as long as they are not parallel. Therefore, what you want is that all of the given line segments should belong to that triangle.

An easy way to check this is to consider the region ball which encloses that triangle, and then use the command RegionWithin to check if the given line segments belong to that ball. If all of them belong to that ball, then the answer to your question is True.

Following command basically does that:

ClearAll[test];
test = Module[{lines, points, disk, lineSegments},
lines[i_] := (InfiniteLine /@ #)[[i]];
points = 
 Flatten[Table[{x, y} /. 
    Flatten[Solve[{x, y} \[Element] lines[i] && {x, y} \[Element] 
        lines[j], {x, y}]], {i, 1, 2}, {j, i + 1, 3}], 1];
disk = BoundingRegion[points, "MinDisk"];
lineSegments = 
 Flatten@Table[Line[{#[[i]], #[[j]]}], {i, 1, 2}, {j, i + 1, 3}];
Graphics[Flatten@Join[{disk}, {Red}, lineSegments]]
And @@ Table[RegionWithin[disk, lineSegments[[i]]], {i, 3}]
] &;

The scooping variable lines are the infinite lines to which given line segments belong to. The variable points are the intersection points with which we create the variable disk. Finally, we generate the line segments with the variable lineSegments and check if they belong to the region of ball.

The good thing about this method is that it also visualizes how the situation is True or False. For example, for the examples you gave, we immediately see that for

lines1 = {{{3.4, 3}, {3, 0}}, {{3, 0}, {5, 0.2}}, {{5, 0.2}, {4.2, 5}}};
lines2 = {{{0, 0.8}, {3, 0}}, {{3, 0}, {5, 0.2}}, {{5, 0.2}, {8, 3}}};
lines3 = {{{3.4, 2}, {3, 0}}, {{3, 0}, {5, 0.2}}, {{5, 0.2}, {6, -3}}};

we get

Of course there is nothing special about the lines being connected to each other, which is the case in your examples. We see that the code works equally well for disconnected line segments, for example:

test4 = {{{1, 2}, {1, 1}}, {{2, 2}, {3, 3}}, {{4, 4}, {3, 4}}};
test5 = {{{1, 4}, {1, 1}}, {{2, 2}, {3, 3}}, {{4, 4}, {3, 4}}};
test6 = {{{1, 5}, {1, 1}}, {{2, 2}, {3, 3}}, {{4, 4}, {3, 4}}};

Answer 3

lines1 is part of a triangle if and only if P[[2, 1]] == P[[1, 2]] and P[[2,2]] == P[[3, 1]] are fulfilled and if the following linear equation in the two variables s and t has a solution with t>=0 and s>=0:

 P = N@lines1[[1]];
 Solve[P[[1, 2]] + s (P[[1, 1]] - P[[1, 2]]) == P[[3, 1]] + t (P[[3, 2]] - P[[3, 1]]), {s, t}]

The following function checks for all of this:

triangleQ[line_Line] := With[{P = N@line[[1]]},
  If[Length[P] == 3,
   If[P[[1, 2]] == P[[2, 1]] && P[[2, 2]] == P[[3, 1]],
    With[{
      A = Transpose[{(P[[1, 1]] - P[[1, 2]]), -(P[[3, 2]] - P[[3, 1]])}],
      b = P[[2, 2]] - P[[2, 1]]
      },
     If[Abs[Det[A]] > Sqrt[$MachineEpsilon],
      And @@ Thread[LinearSolve[A, b] >= 0.],
      False
      ]
     ],
    False
    ],
   False
   ]
  ]

Of course, this function can be optimized, for example, by solving the linear 2 x 2 system symbolically and by applying Compile.