8
$\begingroup$

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}]

example 1

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}]

example 2

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

example 3

$\endgroup$
4
  • 1
    $\begingroup$ Your examples 2 and 3 are not clear: according to your rule "If can get a triangle by extending one or more line segment, the answer should be True" they are part of triangle. $\endgroup$
    – yarchik
    Apr 22, 2018 at 20:36
  • $\begingroup$ It is sufficient to check if none of 2 vectors out of 3 along the segments are collinear. $\endgroup$
    – yarchik
    Apr 22, 2018 at 20:38
  • $\begingroup$ In examples 2, 3 line segments could be extended to make a triangle, but in each of those examples would violate the third bullet that I specify. Part of at least one line segment would not be part of the triangle. It is not enough to perform a collinear check. $\endgroup$
    – Ted Ersek
    Apr 23, 2018 at 1:08
  • 1
    $\begingroup$ Thanks for making these clarifications. Can line segments be disconnected, or are you only considering 2D objects that are specified by 4 (or less) distinct points? $\endgroup$
    – yarchik
    Apr 23, 2018 at 8:16

3 Answers 3

4
$\begingroup$

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

enter image description here

{u, v}
{{0.4, 2}, {-2, -0.2}}
$\endgroup$
1
  • $\begingroup$ This method does not check if any line segment would not be part of the triangle, e.g. test6 = {{{1, 4}, {1, 1}}, {{1, 1}, {2, 2}}, {{2, 2}, {1, 2}}}; isclosed = closedQ[test6]; Graphics[{Arrowheads[0.2], Arrow[test6], Text[isclosed, Center]}] $\endgroup$ Apr 23, 2018 at 11:47
5
$\begingroup$

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 region check example 1

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}}};

region check example 2

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Similarly to my answer, yours does not check for line segments outside the triangle. E.g. test6 = Line[{{{1, 4}, {1, 1}}, {{1, 1}, {2, 2}}, {{2, 2}, {1, 2}}}]; istriangle = triangleQ[test6]; Graphics[{Arrowheads[0.2], Arrow[test6[[1]]], Text[istriangle, Center]}] $\endgroup$ Apr 23, 2018 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.