CG · Maths · Python

Testing a point inside triangle – Math at work in cg

Here we discuss ways to derive and implement the logic for testing a point inside a triangle. In other words, we define a system for which given three points as the vertex of a triangle, we find whether a point lies inside the triangle or not. For the purpose of simplicity, we will confine these test in a 2d coordinate system.

Back to High School

Before approaching any logic/methodology we first examine the fundamentals of mathematics involved. We revisit some high school math.

Every point in a two-dimensional space can be represented as a pair of coordinates, usually represented by x and y.

point p = (x, y)

 

coordinateSystem

 

I would like to touch python implementation in parallel here as well.

This point can be represented as python tuple of two floats and can be declared as :

p = (floatA, floatB)

To define a triangle, we need three points. Let’s call them a, b, c and define them as:

a = (x1, y1)

b = (x2, y2)

c = (x3, y3)

Now we define our test point p as:

p = (x, y)

triangle

 

If we look at the point definitions above, these are nothing but 8 numbers(floats). We will do some calculations on them. Namely, addition, subtraction, multiplication and division and arrive at another number as a result of these operations. And we have our test result. It is as simple as that. Nothing more, nothing less. So now let us begin applying our logic.

Convexity

Our test requires us to examine the concept of concavity/convexity.

 

Convexity is defined as :

‘Having a surface or boundary that curves or bulges outward’

 

The word ‘concave’ has the word ‘cave’ inside it. So it has something to do with a cave. This is how I remembered it from high school.

Which of these two figures below you think represents a cave.

caves

You are right, it’s fig b.

 

This is what a concave point is :

 

In the figure below point ‘p’ is concave to points ‘a’ and ‘b’, if we move from ‘a’ to ‘b’ looking towards the left of ‘a’. Note that we define left on the side of our choice to be considered ‘inside’.

concavity01

Convex is nothing but the opposite of concave.

convexity1

Now that we have the idea what convexity is, we will exploit this concept in our logic. For our given triangle, we will check whether the point ‘p’ is concave to the three lines ‘ab’, ‘bc’ and ‘ca’.

If it is concave to all three of them then it is inside the triangle, else not.

We devised a way to check if a given point lies to the left or right of a line. Here, the right/left side of a line is determined by going from one point to another. If we go from a —-> b, then imagine a person standing on point ‘a’ and facing point ‘b’. All the point lying on the right side of this person are right and all points on the left side of this person are left.

leftRight

Two Point Form Equation of  a Line

To do this, we make use of two-point-form of equation of a line:

y = y1 + [(x – x1) (y2 – y1) / (x2 – x1)]

 

Again going to python implementation, this could be easily written as

y = y1 + (   (x – x1) * (y2 – y1) / (x2 – x1) )

In the above the line is defined between the point (x1, y1) and point (x2, y2). The general point (x, y) represents any point on this line.

line

Now that we have a solid formula to use, let’s apply this to our case. Given the three sides of the triangle ‘ab’, ‘bc’ and ‘ca’, we test whether our test-point point lies to the left or right to each of these lines.

To find whether the point lies to left or right, we take the x coordinate of point ‘p’ and put in it the two-point-form equation of the line.

This will give us the y coordinate of the point ‘p’ if it were on the line.

Next, we check whether this y coordinate that we calculated is greater or smaller than the actual y coordinate of ‘p’. If it is greater than ‘p’ is on the left else it is on the right.

twoPointLineUse

Let the points forming the line be ‘a’ and ‘b’ defined as:

a = (x1, y1)

b= (x2, y2)

and point ‘p’ as:

p = (x3,  y3)

 

Next we find the y coordinate if were to lie on ‘ab’,

this will given by:

y = y1 + [(x3 – x1) (y2 – y1) / (x2 – x1)]

Let’s take a simple view of the above equation. In the above equation, we have five number on the right. x1, x2, x3, y1 and y2. We are doing simple operations of  +, – , x and / on them and we get a sixth number y. Now we just want to calculate whether y is greater than y3 or not. Simple, and we get the answer if lies on the left or right.

Also, we want to be sure that we take all the cases in going from ‘a’ to ‘b’. Point ‘b’ could be in any quadrant relative to ‘a’. There are exactly four possibilities for ‘b’ lying in each quadrant.

quadrants

If ‘b’ lies in quadrant ’0′ or ’3′ then we note that:

y > y3, ‘p’ is on the right of ‘ab’

y < y3, ‘p’ is on  the left of ‘ab’

 

if ‘b’ is in quadrant ’1′ or ’2′ then the conditions are reversed.

y > y3, ‘p’ is on the left of ‘ab’

y < y3, ‘p’ is on right of ‘ab’

 

So we have to check for ‘b’ position with respect to ‘a’. And then use that information along the comparisons to finally get the result.

Let us put the python implementation for this. This code is more verbose than what it should be. It could definitely be more concise. Parts of it are also redundant. But I wanted this to be more readable and hence the verbosity.

 

def isConvex(pointA, pointP, pointB):
    x1, y1 = pointA

    x2, y2 = pointB

    x3, y3 = pointP

    if x2 > x1 and y2 > y1:
        quadB = 0
    elif x2 < x1 and y2 > y1:
        quadB = 1
    elif x2 < x1 and y2 < y1: quadB = 2 elif x2 > x1 and y2 < y1: quadB = 3 y = y1 + ((x3 - x1) * (y2 - y1) / (x2 - x1)) if quadB == 0 or quadB == 3: if y > y3:
            return True
        else:
            return False
    elif quadB == 1 or quadB == 2:
        if y > y3:
            return False
        else:
            return True

Following is the example of the above function at work.

>>a = (1.0, 6.0)
>>b = (3.0, 8.0)
>>p = (2.0, 12.0)
>>isConvex(a, p, b)
>>False

Now that we have a working function to test for convexity(‘right’). It is very easy to get all the three points of a triangle – ‘a’, ‘b’, ‘c’ and test a point – ‘p’ is inside or outside.

Let write the code for that:

def insideTriangle(a, b, c, p):
    if (not isConvex(a, p, b)) and (not isConvex(b, p, c)) and (not isConvex(c, p ,a)):
        return True
    else:
        return False

Please note that we are using the function isConvex() which we defined earlier.

And that’s it, we have our function to check whether the point lies in the triangle or not.

 

Now that  we know the concept of our test inside-out, let’s put it to a simple test. Please download the attached scene file and the script. There is a null called ‘p’ in the scene, that we test inside the triangle defined by three other nulls ‘a’, ‘b’ and ‘c’.

 

Here’s the final script to run the test inside the sample scene file

def getObjectByUserKeyword(inKeyword):
    oColl = Application.ActiveSceneRoot.FindChildren('')

    for o in oColl:
        keywordColl = Application.GetUserKeyword(o)
        for thisKeyword in keywordColl:
            if thisKeyword == inKeyword:
                return o

    return None

def getScenePoints():
    a = getObjectByUserKeyword('a')
    b = getObjectByUserKeyword('b')
    c = getObjectByUserKeyword('c')
    p = getObjectByUserKeyword('p')

    return a, b, c, p

def getPointCoordinates(inPoint):
    x = inPoint.Kinematics.Global.Parameters('PosX').Value
    y = inPoint.Kinematics.Global.Parameters('PosY').Value

    return x, y

def getPointCoordinateList(inList):
    coordinateList = []
    for point in inList:
        coordinateList.append(getPointCoordinates(point))

    return coordinateList

def setVisibility(on=True):
    inside = getObjectByUserKeyword('inside')
    outside = getObjectByUserKeyword('outside')
    inside.Properties('Visibility').Parameters('viewvis').Value = on
    outside.Properties('Visibility').Parameters('viewvis').Value = not on

    return

def isConvex(pointA, pointP, pointB):
    x1, y1 = pointA

    x2, y2 = pointB

    x3, y3 = pointP

    if x2 > x1 and y2 > y1:
        quadB = 0
    elif x2 < x1 and y2 > y1:
        quadB = 1
    elif x2 < x1 and y2 < y1: quadB = 2 elif x2 > x1 and y2 < y1: quadB = 3 y = y1 + ((x3 - x1) * (y2 - y1) / (x2 - x1)) if quadB == 0 or quadB == 3: if y > y3:
            return True
        else:
            return False
    elif quadB == 1 or quadB == 2:
        if y > y3:
            return False
        else:
            return True
def insideTriangle(a, b, c, p):
    if (not isConvex(a, p, b)) and (not isConvex(b, p, c)) and (not isConvex(c, p ,a)):
        return True
    else:
        return False

scenePoints = getScenePoints()

a, b, c, p = getPointCoordinateList(scenePoints)

testValue = insideTriangle(a, b, c, p)

setVisibility(testValue)

To run the test:

1. Move the null ‘p’ , or any of the nulls ‘a’, ‘b’ and/or ‘c’  to make ‘p’ lie inside or outside the triangle in the front view. If you move the points ‘a’ , ‘b’ or ‘c’, please make sure that cyclic order ‘abc’ is maintained in the anticlockwise direction. This is important so that we always test for points on the left of the line.

2. Run the script.

3. The text-curves ‘inside’ and ‘outside’ will be visible according to the result of the test.

 

Note that, as we are testing in a 2D plane , we use the only the front view as our coordinate plane and the points have their position z = 0.

Enjoy !!

 

Download insideTriangleTest.scn

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