Origin containing triangle

Overview

In this article we will try to solve a problem mention in the Perl Weekly Challenge called Origin-containing triangle. We are given the coordinates of the triangle A(x1, y1), B(x2, y2) and C(x3, y3). We need to find whether the origin O(0, 0) lies between the triangle.

Solution

What we need to do is to find the areas of triangle ABO, BCO and ACO. if the sum of the areas of these triangle is equal to the area of triangle ABC then we know that the origin lies between the triangle.

To find the area of the given triangle we will use the below formula:

Area of triangle = (x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))/2

Now lets find the area of smaller triangles:

double area_1 = Math.abs((x2*y3 + x3*(-y2)) / 2.0);
double area_2 = Math.abs((x1*(-y3) + x3*y1) / 2.0);
double area_3 = Math.abs((x1*y2 + x2*(-y1)) / 2.0);

OriginContainingTriangle.java

public static int doesTriangleContainsOrigin(int x1, int y1, int x2, int y2, int x3, int y3) {
    double area = Math.abs((x1*(y2 - y3) + x2*(y3 - y1) + x3*(y1 - y2)) / 2.0);

    double area_1 = Math.abs((x2*y3 + x3*(-y2)) / 2.0);
    double area_2 = Math.abs((x1*(-y3) + x3*y1) / 2.0);
    double area_3 = Math.abs((x1*y2 + x2*(-y1)) / 2.0);

    double aumOfAreaOfSmallTriangles = area_1 + area_2 + area_3;
    return area == aumOfAreaOfSmallTriangles ? 1 : 0;
}

Test

Below is the simple to test to check the code above:

import org.junit.Test;

import static org.junit.Assert.*;

public class OriginContainingTriangleTest {

    @Test
    public void doesTriangleContainsOrigin() {
        assertEquals(0, OriginContainingTriangle.doesTriangleContainsOrigin(0, 1, 1, 0, 2, 2));
        assertEquals(1, OriginContainingTriangle.doesTriangleContainsOrigin(1, 1, -1, 1, 0, -3));
        assertEquals(1, OriginContainingTriangle.doesTriangleContainsOrigin(0, 1, 2, 0, -6, 0));
    }
}

Conclusion

In this article we looked as how to find if the origin lies between a given triangle using Java.

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

%d bloggers like this: