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

Published on 12 May 2024 09:40 PM
#Go

How to resolve the algorithm Determine if two triangles overlap step by step in the Go 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 Go programming language

The code defines types and functions to check if two triangles overlap in two dimensions. The main function creates several triangles and checks if they overlap.

  • The code defines a point type with two float64 fields, x and y.

  • It also defines a triangle type with three point fields, p1, p2, and p3.

  • The point type has a String method that returns a string representation of the point.

  • The triangle type also has a String method that returns a string representation of the triangle.

  • The triangle type has a det2D method that returns the determinant of the 2D matrix formed by the points of the triangle.

  • The det2D method is used to check the winding direction of the triangle.

  • The checkTriWinding method checks if the winding direction of the triangle is counterclockwise.

  • If the winding direction is not counterclockwise, the method panics.

  • The boundaryCollideChk and boundaryDoesntCollideChk functions are used to check if a point is on the boundary of a triangle.

  • The triTri2D function checks if two triangles overlap in two dimensions.

  • The function takes two triangles, t1 and t2, an epsilon value, eps, a boolean value allowReversed that indicates whether the triangles can be reversed, and a boolean value onBoundary that indicates whether points on the boundary are considered as colliding or not.

  • The function first checks if the winding direction of both triangles is counterclockwise.

  • If the winding direction is not counterclockwise, the function panics.

  • The function then checks if any of the points of t1 lie on the outside of any of the edges of t2.

  • If any of the points of t1 lie on the outside of any of the edges of t2, the function returns false.

  • The function then checks if any of the points of t2 lie on the outside of any of the edges of t1.

  • If any of the points of t2 lie on the outside of any of the edges of t1, the function returns false.

  • If none of the points of either triangle lie on the outside of any of the edges of the other triangle, the function returns true.

  • The iff function returns the first string if the condition is true, and the second string if the condition is false.

  • The main function creates several triangles and checks if they overlap.

  • The main function prints the results of the overlap checks to the console.

Source code in the go programming language

package main

import "fmt"

type point struct {
    x, y float64
}

func (p point) String() string {
    return fmt.Sprintf("(%.1f, %.1f)", p.x, p.y)
}

type triangle struct {
    p1, p2, p3 point
}

func (t *triangle) String() string {
    return fmt.Sprintf("Triangle %s, %s, %s", t.p1, t.p2, t.p3)
}

func (t *triangle) det2D() float64 {
    return t.p1.x * (t.p2.y - t.p3.y) +
           t.p2.x * (t.p3.y - t.p1.y) +
           t.p3.x * (t.p1.y - t.p2.y) 
}

func (t *triangle) checkTriWinding(allowReversed bool) {
    detTri := t.det2D()
    if detTri < 0.0 {
        if allowReversed {
            a := t.p3
            t.p3 = t.p2
            t.p2 = a
        } else {
            panic("Triangle has wrong winding direction.")
        }
    }
}

func boundaryCollideChk(t *triangle, eps float64) bool {
    return t.det2D() < eps
}

func boundaryDoesntCollideChk(t *triangle, eps float64) bool {
    return t.det2D() <= eps
}

func triTri2D(t1, t2 *triangle, eps float64, allowReversed, onBoundary bool) bool {
    // Triangles must be expressed anti-clockwise.
    t1.checkTriWinding(allowReversed)
    t2.checkTriWinding(allowReversed)

    // 'onBoundary' determines whether points on boundary are considered as colliding or not.
    var chkEdge func (*triangle, float64) bool
    if onBoundary {
        chkEdge = boundaryCollideChk
    } else {
        chkEdge = boundaryDoesntCollideChk
    }
    lp1 := [3]point{t1.p1, t1.p2, t1.p3}
    lp2 := [3]point{t2.p1, t2.p2, t2.p3}

    // for each edge E of t1
    for i := 0; i < 3; i++ {
        j := (i + 1) % 3
        // Check all points of t2 lay on the external side of edge E.
        // If they do, the triangles do not overlap.
        tri1 := &triangle{lp1[i], lp1[j], lp2[0]}
        tri2 := &triangle{lp1[i], lp1[j], lp2[1]}
        tri3 := &triangle{lp1[i], lp1[j], lp2[2]}
        if chkEdge(tri1, eps) && chkEdge(tri2, eps) && chkEdge(tri3, eps) {
            return false
        }
    }

    // for each edge E of t2
    for i := 0; i < 3; i++ {
        j := (i + 1) % 3
        // Check all points of t1 lay on the external side of edge E.
        // If they do, the triangles do not overlap.
        tri1 := &triangle{lp2[i], lp2[j], lp1[0]}
        tri2 := &triangle{lp2[i], lp2[j], lp1[1]}
        tri3 := &triangle{lp2[i], lp2[j], lp1[2]}
        if chkEdge(tri1, eps) && chkEdge(tri2, eps) && chkEdge(tri3, eps) {
            return false
        }
    }

    // The triangles overlap.
    return true
}

func iff(cond bool, s1, s2 string) string {
    if cond {
        return s1
    }
    return s2
}

func main() {
    t1 := &triangle{point{0.0, 0.0}, point{5.0, 0.0}, point{0.0, 5.0}}
    t2 := &triangle{point{0.0, 0.0}, point{5.0, 0.0}, point{0.0, 6.0}}
    fmt.Printf("%s and\n%s\n", t1, t2)
    overlapping := triTri2D(t1, t2, 0.0, false, true)
    fmt.Println(iff(overlapping, "overlap", "do not overlap"))

    // Need to allow reversed for this pair to avoid panic.
    t1 = &triangle{point{0.0, 0.0}, point{0.0, 5.0}, point{5.0, 0.0}}
    t2 = t1
    fmt.Printf("\n%s and\n%s\n", t1, t2)
    overlapping = triTri2D(t1, t2, 0.0, true, true)
    fmt.Println(iff(overlapping, "overlap (reversed)", "do not overlap"))

    t1 = &triangle{point{0.0, 0.0}, point{5.0, 0.0}, point{0.0, 5.0}}
    t2 = &triangle{point{-10.0, 0.0}, point{-5.0, 0.0}, point{-1.0, 6.0}}
    fmt.Printf("\n%s and\n%s\n", t1, t2)
    overlapping = triTri2D(t1, t2, 0.0, false, true)
    fmt.Println(iff(overlapping, "overlap", "do not overlap"))

    t1.p3 = point{2.5, 5.0}
    t2 = &triangle{point{0.0, 4.0}, point{2.5, -1.0}, point{5.0, 4.0}}
    fmt.Printf("\n%s and\n%s\n", t1, t2)
    overlapping = triTri2D(t1, t2, 0.0, false, true)
    fmt.Println(iff(overlapping, "overlap", "do not overlap"))

    t1 = &triangle{point{0.0, 0.0}, point{1.0, 1.0}, point{0.0, 2.0}}
    t2 = &triangle{point{2.0, 1.0}, point{3.0, 0.0}, point{3.0, 2.0}}
    fmt.Printf("\n%s and\n%s\n", t1, t2)
    overlapping = triTri2D(t1, t2, 0.0, false, true)
    fmt.Println(iff(overlapping, "overlap", "do not overlap"))

    t2 = &triangle{point{2.0, 1.0}, point{3.0, -2.0}, point{3.0, 4.0}}
    fmt.Printf("\n%s and\n%s\n", t1, t2)
    overlapping = triTri2D(t1, t2, 0.0, false, true)
    fmt.Println(iff(overlapping, "overlap", "do not overlap"))

    t1 = &triangle{point{0.0, 0.0}, point{1.0, 0.0}, point{0.0, 1.0}}
    t2 = &triangle{point{1.0, 0.0}, point{2.0, 0.0}, point{1.0, 1.1}}
    fmt.Printf("\n%s and\n%s\n", t1, t2)
    println("which have only a single corner in contact, if boundary points collide")
    overlapping = triTri2D(t1, t2, 0.0, false, true)
    fmt.Println(iff(overlapping, "overlap", "do not overlap"))

    fmt.Printf("\n%s and\n%s\n", t1, t2)
    fmt.Println("which have only a single corner in contact, if boundary points do not collide")
    overlapping = triTri2D(t1, t2, 0.0, false, false)
    fmt.Println(iff(overlapping, "overlap", "do not overlap"))
}


  

You may also check:How to resolve the algorithm Sorting algorithms/Strand sort step by step in the jq programming language
You may also check:How to resolve the algorithm Floyd's triangle step by step in the COBOL programming language
You may also check:How to resolve the algorithm String length step by step in the VBA programming language
You may also check:How to resolve the algorithm Loops/With multiple ranges step by step in the M2000 Interpreter programming language
You may also check:How to resolve the algorithm Knapsack problem/0-1 step by step in the LSL programming language