How to resolve the algorithm Determine if two triangles overlap step by step in the Ruby programming language

Published on 12 May 2024 09:40 PM
#Ruby

How to resolve the algorithm Determine if two triangles overlap step by step in the Ruby programming language

Table of Contents

Problem Statement

Determining if two triangles in the same plane overlap is an important topic in collision detection.

Determine which of these pairs of triangles overlap in 2D:

Optionally, see what the result is when only a single corner is in contact (there is no definitive correct answer):

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Determine if two triangles overlap step by step in the Ruby programming language

This code implements a function that checks if two triangles collide. The triangles are represented as lists of two-dimensional vectors. The function first checks if the triangles are wound in the same direction, and if not, it swaps the order of the points in one of the triangles. It then checks if any of the edges of one triangle lie on the outside of the other triangle, and if so, it returns false to indicate that the triangles do not collide. If none of the edges of one triangle lie on the outside of the other triangle, it returns true to indicate that the triangles do collide. The function also has an additional parameter that specifies whether to consider points on the boundary of the triangles as colliding. If this parameter is set to true, then the function will consider points on the boundary of the triangles as colliding. If this parameter is set to false, then the function will not consider points on the boundary of the triangles as colliding. The main function tests the function with several different pairs of triangles.

Source code in the ruby programming language

require "matrix"

def det2D(p1, p2, p3)
    return p1[0] * (p2[1] - p3[1]) + p2[0] * (p3[1] - p1[1]) + p3[0] * (p1[1] - p2[1])
end

def checkTriWinding(p1, p2, p3, allowReversed)
    detTri = det2D(p1, p2, p3)
    if detTri < 0.0 then
        if allowReversed then
            p2[0], p3[0] = p3[0], p2[0]
            p2[1], p3[1] = p3[1], p2[1]
        else
            raise "Triangle has incorrect winding"
        end
    end
end

def boundaryCollideChk(p1, p2, p3, eps)
    return det2D(p1, p2, p3) < eps
end

def boundaryDoesntCollideChk(p1, p2, p3, eps)
    return det2D(p1, p2, p3) <= eps
end

def triTri2D(t1, t2, eps, allowReversed, onBoundary)
    # Triangles must be expressed anti-clockwise
    checkTriWinding(t1[0], t1[1], t1[2], allowReversed)
    checkTriWinding(t2[0], t2[1], t2[2], allowReversed)

    if onBoundary then
        # Points on the boundary are considered as colliding
        chkEdge = -> (p1, p2, p3, eps) { boundaryCollideChk(p1, p2, p3, eps) }
    else
        # Points on the boundary are not considered as colliding
        chkEdge = -> (p1, p2, p3, eps) { boundaryDoesntCollideChk(p1, p2, p3, eps) }
    end

    # For edge E of triangle 1
    for i in 0..2 do
        j = (i + 1) % 3

        # Check all points of trangle 2 lay on the external side of the edge E. If
        # they do, the triangles do not collide.
        if chkEdge.(t1[i], t1[j], t2[0], eps) and chkEdge.(t1[i], t1[j], t2[1], eps) and chkEdge.(t1[i], t1[j], t2[2], eps) then
            return false
        end
    end

    # For edge E of triangle 2
    for i in 0..2 do
        j = (i + 1) % 3

        # Check all points of trangle 1 lay on the external side of the edge E. If
        # they do, the triangles do not collide.
        if chkEdge.(t2[i], t2[j], t1[0], eps) and chkEdge.(t2[i], t2[j], t1[1], eps) and chkEdge.(t2[i], t2[j], t1[2], eps) then
            return false
        end
    end

    # The triangles collide
    return true
end

def main
    t1 = [Vector[0,0], Vector[5,0], Vector[0,5]]
    t2 = [Vector[0,0], Vector[5,0], Vector[0,6]]
    print "Triangle: ", t1, "\n"
    print "Triangle: ", t2, "\n"
    print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]

    t1 = [Vector[0,0], Vector[0,5], Vector[5,0]]
    t2 = [Vector[0,0], Vector[0,5], Vector[5,0]]
    print "Triangle: ", t1, "\n"
    print "Triangle: ", t2, "\n"
    print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, true, true)]

    t1 = [Vector[  0,0], Vector[ 5,0], Vector[ 0,5]]
    t2 = [Vector[-10,0], Vector[-5,0], Vector[-1,6]]
    print "Triangle: ", t1, "\n"
    print "Triangle: ", t2, "\n"
    print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]

    t1 = [Vector[0,0], Vector[  5, 0], Vector[2.5,5]]
    t2 = [Vector[0,4], Vector[2.5,-1], Vector[  5,4]]
    print "Triangle: ", t1, "\n"
    print "Triangle: ", t2, "\n"
    print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]

    t1 = [Vector[0,0], Vector[1,1], Vector[0,2]]
    t2 = [Vector[2,1], Vector[3,0], Vector[3,2]]
    print "Triangle: ", t1, "\n"
    print "Triangle: ", t2, "\n"
    print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]

    t1 = [Vector[0,0], Vector[1, 1], Vector[0,2]]
    t2 = [Vector[2,1], Vector[3,-2], Vector[3,4]]
    print "Triangle: ", t1, "\n"
    print "Triangle: ", t2, "\n"
    print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]

    # Barely touching
    t1 = [Vector[0,0], Vector[1,0], Vector[0,1]]
    t2 = [Vector[1,0], Vector[2,0], Vector[1,1]]
    print "Triangle: ", t1, "\n"
    print "Triangle: ", t2, "\n"
    print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]

    # Barely touching
    t1 = [Vector[0,0], Vector[1,0], Vector[0,1]]
    t2 = [Vector[1,0], Vector[2,0], Vector[1,1]]
    print "Triangle: ", t1, "\n"
    print "Triangle: ", t2, "\n"
    print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, false)]
end

main()

You may also check:How to resolve the algorithm Loops/For with a specified step step by step in the Oz programming language
You may also check:How to resolve the algorithm CRC-32 step by step in the REXX programming language
You may also check:How to resolve the algorithm Comma quibbling step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Temperature conversion step by step in the Scala programming language
You may also check:How to resolve the algorithm Roots of unity step by step in the Factor programming language