1

I need to check if given three line segments form a triangle. A line segment can be expressed as an array of 4 integers giving the end-points coordinates in the form [ x1, y1, x2, y2 ]. So I need to write a function that is given as input three line segments K, L and M and will return 1 if they form a triangle, 0 otherwise. If the input parameters are outside the range of the algorithm supports I need to return -1. Examples :

function trigTest(K, L, M)

var K=[2,3,6,9], L=[8,1,6,9], M=[8,1,2,3], X=[1,7,6,9]
trigTest(K, L, M) // -> 1
trigTest(L, K, M) // -> 1
trigTest(M, K, L) // -> 1
trigTest(L, L, M) // -> 0
trigTest(X, L, M) // -> 0

enter image description here

I actually have a solution but it's pretty cumbersome and I don't think it is the right way. First I calculate the distance of every line segment and then I use triangle inequalities to check if they can actually form a triangles base on their lengths.

function distance(line){
var x1 = line[0],
y1 = line[1],
x2 = line[2],
y2 = line[3];

return Math.sqrt(Math.pow((x2-x1),2) + Math.pow(y2-y1),2) 
}

function trigTest(K,L,M){
var distanceK = distance(K), distanceL = distance(L), distanceM = distance(M);
if((distanceK + distanceL) > distanceM && (distanceK + distanceM) > distanceL && distanceL + distanceM > distanceK){
// algorithm here
}else{
return 0;
}
}

Update

Thanks to @antoniskamamis and @trincot I have made a similar solution if someone wants to stick with arrays instead of working with strings. Big shout out to them.

function trigTest(K, L, M) {
  var points = [];
  var k = dots(K), l = dots(L), m = dots(M);

  if(ifDotsOnSameLineAreEqual(k) || ifDotsOnSameLineAreEqual(l) || ifDotsOnSameLineAreEqual(m)){
    return false;
  }else{
    return points.concat(k,l,m).every(function(point, index, array){
      return array.filter(function(i){ return ifTwoDotsAreEqual(i,point)}).length == 2;
    })
  }
}

function dots(line) {
  var x1 = line[0], 
      y1 = line[1],
      x2 = line[2],
      y2 = line[3];
  return [[x1,y1],[x2, y2]];
}

function ifTwoDotsAreEqual(x,y){
  return x[0] == y[0] && x[1] == y[1];
}

function ifDotsOnSameLineAreEqual(line){
  return ifTwoDotsAreEqual(line[0],line[1]);
}
4
  • What have you tried so far? Can you show more code than just the function header?
    – trincot
    Feb 15, 2016 at 22:14
  • @trincot updated, and I will keep on updating as solving the case. Feb 15, 2016 at 22:23
  • Couldn't you just calculate the surface area of given points, and if it equals zero it's not a triangle? Feb 15, 2016 at 22:28
  • @ItsGreg nope, you can't. These are particular coordinates and not line segment lengths. Feb 15, 2016 at 22:30

3 Answers 3

3

you could use this approach

function trigTest(a,b,c){
   var parts = [];
   Array.prototype.slice.call(arguments).forEach(function(item){
    parts.push(item.slice(0,2).join("|"));
    parts.push(item.slice(2).join("|"));
   })

   return parts.every(function(item, index, array){
     return array.filter( function(x){ return x == item}).length == 2;
   })
}

What it does is:

  1. runs through the list of arguments Array.prototype.slice.call(arguments).forEach
  2. seperates the arrays into points first two, last two as strings parts.push(item.slice(0,2).join(""));parts.push(item.slice(2).join(""));
  3. given the array of points it checks that each point is present two times parts.every(function(item, index, array){ return array.filter( function(x){ return x == item}).length == 2; })

Using a 'one liner'

function trigTest(a,b,c){
   var slice = Array.prototype.slice;
   return slice.call(arguments).reduce(function(previous, current){
     previous.push(current.slice(0,2).join("|"));
     previous.push(current.slice(2).join("|"));
     return previous;
   }, [])
  .every(function(item, index, array){
    return array.filter( function(x){ return x == item; }).length == 2;
   })
}

Checking for zero length lines

if we know that the inputs are not validated to be lines before we have to add a check if any of the given lines has start and end points the same (is a 0 length line or a point)

in this case our code will have to be like this

function trigTest(a,b,c){
   var slice = Array.prototype.slice;

   if(slice.call(arguments).some(isPoint)){
     return false;
   };

   return slice.call(arguments).reduce(function(previous, current){
     previous.push(current.slice(0,2).join("|"));
     previous.push(current.slice(2).join("|"));
     return previous;
   }, [])
  .every(function(item, index, array){
    return array.filter( function(x){ return x == item; }).length == 2;
   })
}

function isPoint(value){
  return value[0] == value[2] && value[1] == value[3];
}
11
  • That's a dangerous join. the pair 22, 1 will join the same way as 2, 21. Better put a character there.
    – trincot
    Feb 15, 2016 at 22:58
  • 1
    awesome solution, I was doing the same thing checking if the point is present 2 times, but I represented the points as arrays so I had to write a function that checks equality of an array since javascript doesn't have it. Thank you, this is an awesome solution. Btw thank you for refactoring the code. Feb 15, 2016 at 23:00
  • 2
    @antoniskamamis, trigTest([22,3,6,9], [8,1,6,9], [8,1,2,23]) returns true. It should return false. You need to do join("|") (whatever character that separates numbers).
    – trincot
    Feb 15, 2016 at 23:04
  • @antoniskamamis he does have a point there, haven't thought about a case besides one digit numbers... Feb 15, 2016 at 23:08
  • @VlatkoRistovski i updated the answer with a different join character Feb 15, 2016 at 23:10
1

Based on your examples, the key criteria is that you have exactly two copies of three x,y coordinates, so rather than deal with this from a geometric or trigonometric standpoint, you may have an easier time dealing with this based on basic set-theory: to have a triangle formed from three points A, B, C, your line segments must follow the pattern [Ax, Ay, Bx, By], [Bx, By, Cx, Cy], [Cx, Cy, Ax, Ay].

These segments are not required to be in that order, such as [Bx, By, Ax, Ay] is also valid for the first term.

To check for a valid triangle, count repeated coordinates first to verify two repeats of three unique coordinates (this will also eliminate repeated line segments), then verify that each line segment is non-zero in length (not [Ax, Ay, Ax, Ay]). Those two checks will handle the first two requirements.

I don't know the boundary limits, so I cannot advise on how to test whether it is outside the bounds of the algorithm, but I suspect that will require checking the actual coordinate range, which is integer arithmetic.

This approach should be usable in any javascript engine, although your specific choice of javascript engine will determine the best way to implement it.

0
    var getRandom = () => 1+ Math.floor( Math.random() * 3 ) ;

    // get random line
    var getLine = () => 
        {   
            do
                var l =  { 
                        'a' : {
                            'x' : getRandom(), 
                            'y' : getRandom()
                        },
                        'b' : {
                            'x' : getRandom(),
                            'y' : getRandom() 
                        }
                };

            // repeat until startPoint differ from endPoint
            while ( l.a.x == l.b.x & l.a.y == l.b.y )

            return l;
        };

    var match = (K, L, M) => {

        // Tirangle consist of three points

        // three lines -> six points
        var p1 = K.a.x + "," + K.a.y,
            p2 = K.b.x + "," + K.b.y,
            p3 = L.a.x + "," + L.a.y,
            p4 = L.b.x + "," + L.b.y,
            p5 = M.a.x + "," + M.a.y,
            p6 = M.b.x + "," + M.b.y;

        // count frequency
        var freq = {};

        freq[p1] = freq[p1] + 1 || 1;
        freq[p2] = freq[p2] + 1 || 1;
        freq[p3] = freq[p3] + 1 || 1;
        freq[p4] = freq[p4] + 1 || 1;
        freq[p5] = freq[p5] + 1 || 1;
        freq[p6] = freq[p6] + 1 || 1;

        // result Array
        var result = Array();

        for ( point in freq ){

            // if the point is common for two lines add to result array
            freq[point] == 2 ? result.push( point ) : false;
        }

        return result;
    }

    var test = () => {

        // Three random lines
        var K = getLine(), L = getLine(), M = getLine();

        // Test if three lines has three common points
        if ( match(K, L, M).length == 3 ) {

            printSvg(K,L,M);

            return 1

        } else {

            return 0
        }
    }

    // run when document ready
    var app = () => {

        // div#box needed to print svg with triangles
        const box = document.getElementById('box');

        // test random lines, repeat
        for (x =0;  x <= 1000; x++) {

                t = test ();
        }
    }

    // fire app() when document ready
    document.onreadystatechange = ()=> document.readyState == "complete" ? app() : false;


    // format legend html
    var printWsp = (L) => "("+ L.a.x + ","+ L.a.y+") ("+L.b.x+","+L.b.y+")";

    // append svg to div#box
    var printSvg = (K, L, M) => {

        var legend = '<div class="legend">K ' + printWsp(K) +"<br>L " + printWsp(L) +"<br>M "+ printWsp(M) + "</div>";

        var svgStr = "<svg height='250' width='250'>";
            svgStr += "<line x1="+K.a.x*60 +" y1="+K.a.y*60 +" x2="+K.b.x*60 +" y2="+K.b.y*60 +" style='stroke:rgb(255,0,0);stroke-width:2' />";
            svgStr += "<line x1="+L.a.x*60 +" y1="+L.a.y*60 +" x2="+L.b.x*60 +" y2="+L.b.y*60 +" style='stroke:rgb(0,255,0);stroke-width:2' />";
            svgStr += "<line x1="+M.a.x*60 +" y1="+M.a.y*60 +" x2="+M.b.x*60 +" y2="+M.b.y*60 +" style='stroke:rgb(255,0,255);stroke-width:2' />";
            svgStr += "</svg> ";

        box.insertAdjacentHTML('beforeend', legend);
        box.insertAdjacentHTML('beforeend', svgStr);

    }

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.