Perl Weekly Challenge 101: Origin-containing Triangle

You are given three points in the plane, as a list of six co-ordinates: A = (x1, y1), B = (x2, y2) and C = (x3, y3).

Write a script to find out if the triangle formed by the given three co-ordinates contain origin (0, 0).

Print 1 if found otherwise 0.

Examples

Example 1

Input: A = (0, 1), B = (1, 0) and C = (2, 2)

Output: 0

Because that triangle does not contain (0, 0).

Example 2

Input: A = (1, 1), B = (-1, 1) and C = (0, -3)

Output: 1

Because that triangle contains (0, 0) in its interior.

Example 3

Input: A = (0, 1), B = (2, 0) and C = (-6, 0)

Output: 1

Because (0, 0) is on the edge connecting B and C.

Solution

Overview

To determine whether a point lies inside a triangle, look at the lines connecting subsequent points; that is, look at the line through A and B, the line through B and C, and the line through C and A. (Direction is important here). A point lies inside the triangle if it lies to the same side of each of those lines — that is, either to the left, or the the right of each of those lines. If we consider a point to be inside the triangle if it lies on the line, then it becomes either left or on each of the lines, or right or on each of the lines.

There is a simple formula to determine whether a point lies to the right, the left, or on a line given two points on that line. This stackoverflow question has an example (by Kornel Kisielewicz):

float sign (fPoint p1, fPoint p2, fPoint p3) {
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

This function returns a negative number if point p1 lies to the left on the line through p2 and p3, and a positive number if p1 lies to the right of that line. If it lies on the line, 0 is returned.

Since we’re interested in the origin, we can simplify this to:

sub side ($x1, $y1, $x2, $y2) {
    ($y2 - $y1) * $x2 - ($x2 - $x1) * $y2;
}

Note that we now are passing in the coordinates separately, instead of a structure.

If we have the results of calling this function with each pair of points, all we need to check whether all results are either non-negative or non-positive. If this is the case, the origin lies in the triangle — otherwise, it does not.

We will be assuming we get the coordinates of the triangles on standard input — each triangle on a separate line. Each line consists of six numbers, separated by white space.

Perl

while (<>) {
    my ($x1, $y1, $x2, $y2, $x3, $y3) = split;

    my $s1 = side ($x2, $y2, $x3, $y3);
    my $s2 = side ($x3, $y3, $x1, $y1);
    my $s3 = side ($x1, $y1, $x2, $y2);

    say $s1 <= 0 && $s2 <= 0 && $s3 <= 0 ||
        $s1 >= 0 && $s2 >= 0 && $s3 >= 0 ? 1 : 0
}

We’re using the side function we’ve shown above. Once we have three results, we check whether they are all less then or equal to 0, or all greater than or equal to 0; if so, we print 1, else we print 0.

Find the complete program on GitHub.

AWK

The AWK solution is very similar to the Perl solution above. AWK automatically iterates over the input, and splits the input on white space, giving the fields as positional parameters ($1, $2, etc). This leads to the following program:

function side (x1, y1, x2, y2) {
    return (y2 - y1) * x2 - (x2 - x1) * y2
}

{   
    # x1 y1 x2 y2 x3 y3
    # $1 $2 $3 $4 $5 $6
    s1 = side($3, $4, $5, $6)
    s2 = side($5, $6, $1, $2)
    s3 = side($1, $2, $3, $4)

    print (s1 <= 0 && s2 <= 0 && s3 <= 0 ||
           s1 >= 0 && s2 >= 0 && s3 >= 0 ? 1 : 0)
}

Find the complete program on GitHub.

Bash

We can use the same algorithm in Bash. Bash does have its idiosyncrasies: functions don’t have (useful) return values, and functions use positional parameters to handle input parameters. Arithmetic is done with (( )) and $(( )).

function calc_side () {
    #
    # $1: x1; $2: y1; $3 = x2; $4 = y2
    #
    side=$((($4 - $2) * $3 - ($3 - $1) * $4))
}   
    
while read x1 y1 x2 y2 x3 y3
do    calc_side x2 y2 x3 y3; s1=$side
      calc_side x3 y3 x1 y1; s2=$side
      calc_side x1 y1 x2 y2; s3=$side
    
      echo $(( $s1 <= 0 && $s2 <= 0 && $s3 <= 0 ||
               $s1 >= 0 && $s2 >= 0 && $s3 >= 0 ? 1 : 0 ))
done

Find the complete program on GitHub.

Befunge-93

We will use the same algorithm in Befunge-93. However, the program looks very differently. Unlike the solutions in the other languages, we only accept one line of input.

&11p  &21p  &31p  &41p  &51p  &61p          v

 61g 41g - 51g * 51g 31g - 61g * - 71p     v>
 21g 61g - 11g * 11g 51g - 21g * - 81p    v>
 41g 21g - 31g * 31g 11g - 41g * - 91p   v>

  71g0` #v_  81g0` #v_  91g0` #v_ v      >
v        <          <          <  >            "1" v
>071g ` #v_ 081g ` #v_ 091g ` #v_ ^                >, 55+, @
         >          >          >               "0" ^

Befunge-93 does not have variables. It does have a stack, but we can only access the top two elements of the stack. We can, however, write values into the program itself.

The second line of the program is blank — and this is were we write values to. Six positions, ((1, 1) to (1, 6)) to are reserved for the input, and then three positions ((1, 7) to (1, 9)) for the results of where the origin lies relative to a line.

We start off by reading six numbers, and storing them:

&11p  &21p  &31p  &41p  &51p  &61p

here, reads a number and pushes it on the stack; 11 pushes two 1s on the stack, while p pops three values from the stack: the first two indicate the location where the third value is stored. So this line reads six numbers, which are stored on the second line of the program.

We then do the sign calculation. We don’t have functions in Befunge-93, so we will repeat the code to do the calculations. We’ll fetch the values using the g operator, which pops two coordinates from the stack, then pushes the value on found on that location on the stack. The results are stored on the locations (1, 7) to (1, 9).

 61g 41g - 51g * 51g 31g - 61g * - 71p     v>
 21g 61g - 11g * 11g 51g - 21g * - 81p    v>
 41g 21g - 31g * 31g 11g - 41g * - 91p   v>

Note that in Befunge-93 the program lies on the torus, so if we go to the left, we wrap around returning from the right.

We now check the results, if they are all less then or equal to 0, or if the are all greater than or equal to 0, we print 1; else we print 0:

  71g0` #v_  81g0` #v_  91g0` #v_ v      >
v        <          <          <  >            "1" v
>071g ` #v_ 081g ` #v_ 091g ` #v_ ^                >, 55+, @
         >          >          >               "0" ^

We are printing the characters 0 and 1, and not the numbers 0 and 1. This is because in Befunge-93, if a number is printed, a space is printed as well. And that would mean the output is different from the output of the solutions of the other languages.

Find the complete program on GitHub.

C

The algorithm translates easily to C. We’re using a typedef to avoid some typing.

typedef long double num;

num side (num x1, num y1, num x2, num y2) {
    return (y2 - y1) * x2 - (x2 - x1) * y2;
}

int main (void) {
    char *  line = NULL;
    size_t  len  = 0;

    while (getline (&line, &len, stdin) != -1) {
        num x1, y1, x2, y2, x3, y3;
        num s1, s2, s3;

        if (sscanf (line, "%Lf %Lf %Lf %Lf %Lf %Lf",
                           &x1, &y1, &x2, &y2, &x3, &y3) != 6) {
            fprintf (stderr, "Could not parse input\n");
            exit (1);
        }
 
        s1 = side (x2, y2, x3, y3);
        s2 = side (x3, y3, x1, y1);
        s3 = side (x1, y1, x2, y2);

        printf ("%d\n", (s1 <= 0 && s2 <= 0 && s3 <= 0) ||
                        (s1 >= 0 && s2 >= 0 && s3 >= 0) ? 1 : 0);
    }
    free (line);

    return (0);
}

Find the complete program on GitHub.

Lua

Nothing special in the Lua solution:

function side (x1, y1, x2, y2)
    return (y2 - y1) * x2 - (x2 - x1) * y2
end
          
for line in io . lines () do
    local _, _, x1, y1, x2, y2, x3, y3 =
          line : find ("(%S+) (%S+) (%S+) (%S+) (%S+) (%S+)")
        
    local s1 = side (x2, y2, x3, y3)
    local s2 = side (x3, y3, x1, y1)
    local s3 = side (x1, y1, x2, y2)
     
    if (s1 <= 0 and s2 <= 0 and s3 <= 0) or
       (s1 >= 0 and s2 >= 0 and s3 >= 0)
    then print (1)
    else print (0)
    end
end

Find the complete program on GitHub.

Node.js

A similar solution in Node.js:

function side (x1, y1, x2, y2) {
    return (y2 - y1) * x2 - (x2 - x1) * y2
}   
    
require ('readline')
. createInterface ({input: process . stdin})
. on ('line', _ => {
    let [x1, y1, x2, y2, x3, y3] = _ . split (/\s+/)
    
    let s1 = side (x2, y2, x3, y3)
    let s2 = side (x3, y3, x1, y1)
    let s3 = side (x1, y1, x2, y2)
    
    console . log ((s1 <= 0 && s2 <= 0 && s3 <= 0) ||
                   (s1 >= 0 && s2 >= 0 && s3 >= 0) ? 1 : 0)
});

Find the complete program on GitHub.

Python

Nothing special in the Python solution either:

def side (x1, y1, x2, y2):
    return (y2 - y1) * x2 - (x2 - x1) * y2

for line in fileinput . input ():
    x1, y1, x2, y2, x3, y3 = map (lambda f: float (f), line . split ())
      
    s1 = side (x2, y2, x3, y3)
    s2 = side (x3, y3, x1, y1)
    s3 = side (x1, y1, x2, y2)

    if s1 <= 0 and s2 <= 0 and s3 <= 0 or \
       s1 >= 0 and s2 >= 0 and s3 >= 0:
        print (1)
    else:
        print (0)

Find the complete program on GitHub.

Ruby

The Ruby solution is also very similar:

def side (x1, y1, x2, y2)
    return (y2 - y1) * x2 - (x2 - x1) * y2
end  
    
ARGF . each_line do|_|
    x1, y1, x2, y2, x3, y3 = _ . split . map {|_| _ . to_f}

    s1 = side x2, y2, x3, y3
    s2 = side x3, y3, x1, y1
    s3 = side x1, y1, x2, y2

    puts s1 <= 0 && s2 <= 0 && s3 <= 0 ||
         s1 >= 0 && s2 >= 0 && s3 >= 0 ? 1 : 0
end

Find the complete program on GitHub.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s