How to resolve the algorithm Determine if two triangles overlap step by step in the Go programming language
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
andy
. -
It also defines a
triangle
type with threepoint
fields,p1
,p2
, andp3
. -
The
point
type has aString
method that returns a string representation of the point. -
The
triangle
type also has aString
method that returns a string representation of the triangle. -
The
triangle
type has adet2D
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
andboundaryDoesntCollideChk
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
andt2
, an epsilon value,eps
, a boolean valueallowReversed
that indicates whether the triangles can be reversed, and a boolean valueonBoundary
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 oft2
. -
If any of the points of
t1
lie on the outside of any of the edges oft2
, the function returns false. -
The function then checks if any of the points of
t2
lie on the outside of any of the edges oft1
. -
If any of the points of
t2
lie on the outside of any of the edges oft1
, 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