Determine if two triangles overlap: Difference between revisions

:::*   (0,0),(1,0),(0,1)   and   (1,0),(2,0),(1,1)

<br><br>

 

=={{header|Ada}}==

WITH Ada.Text_IO; USE Ada.Text_IO;

 

Put ((0.0, 0.0, 1.0, 0.0, 0.0, 1.0), (1.0, 0.0, 2.0, 0.0, 1.0, 1.0));

END Main;

{{out}}

<pre>true

false

true

</pre>

 

{{Trans|Kotlin}}

... with different output format (based on Modula 2).

record Point ( real x, y );

record Triangle ( reference(Point) p1, p2, p3 );

CheckOverlap( t1, t2, 0.0, false, false );

end

{{out}}

<pre>

Triangles (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and (1.0, 0.0), (2.0, 0.0), (1.0, 1.1) overlap

Triangles (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and (1.0, 0.0), (2.0, 0.0), (1.0, 1.1) do not overlap

</pre>

 

=={{header|AutoHotkey}}==

counter := 0

for i, Pt in T1

isBetween(x, p1, p2){

return !((x>p1 && x>p2) || (x<p1 && x<p2))

result .= TrianglesIntersect([[0,0],[5,0],[0,5]], [[0,0],[5,0],[0,6]]) "`n"

result .= TrianglesIntersect([[0,0],[0,5],[5,0]], [[0,0],[0,5],[5,0]]) "`n"

result .= TrianglesIntersect([[0,0],[1,0],[0,1]], [[1,0],[2,0],[1,1]]) "`n"

MsgBox % result

Outputs:<pre>1

1

=={{header|C}}==

{{trans|C++}}

#include <stdbool.h>

#include <stdio.h>

 

return EXIT_SUCCESS;

{{out}}

<pre>1,true

 

=={{header|C sharp|C#}}==

using System.Collections.Generic;

 

}

}

{{out}}

<pre>Triangle: (0, 0), (5, 0), (0, 5) and

 

=={{header|C++}}==

#include <iostream>

#include <stdexcept>

cout << TriTri2D(t1, t2, 0.0, false, false) << "," << false << endl;}

 

 

{{out}}

=={{header|D}}==

{{trans|Kotlin}}

import std.typecons;

 

writeln("which have only a single corner in contact, if boundary points do not collide");

overlap(t1, t2, 0.0, false, false);

 

{{out}}

which have only a single corner in contact, if boundary points do not collide

do not overlap</pre>

 

{{trans|Kotlin}}

 

type Point = double * double

Console.WriteLine("{0} and\n{1}\nwhich have only a single corner in contact, if boundary points do not collide\n{2}", t11, t12, if TriTri2D 0.0 false false t11 t12 then "overlap" else "do not overlap")

 

{{out}}

<pre>((0, 0), (5, 0), (0, 5)) and

 

=={{header|FreeBASIC}}==

Iif(x>y,y,x)

#endmacro

print triangle_overlap( a(), b() )

next t

{{out}}

<pre>

=={{header|Go}}==

{{trans|Kotlin}}

 

import "fmt"

overlapping = triTri2D(t1, t2, 0.0, false, false)

fmt.Println(iff(overlapping, "overlap", "do not overlap"))

 

{{out}}

=={{header|Groovy}}==

{{trans|Java}}

 

class TriangleOverlap {

}

}

{{out}}

<pre>Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and

which have only a single corner in contact, if boundary points do not collide

do not overlap</pre>

 

=={{header|Java}}==

{{trans|Kotlin}}

{{works with|Java|8}}

 

public class TriangleOverlap {

}

}

{{out}}

<pre>Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and

which have only a single corner in contact, if boundary points do not collide

do not overlap</pre>

 

=={{header|Julia}}==

{{trans|Python}}

'''Module''':

 

using LinearAlgebra

end

 

 

'''Main''':

 

t1 = [0 0; 5 0; 0 5]

t1 = [0 0; 1 0; 0 1]

t2 = [1 0; 2 0; 1 1]

 

{{out}}

=={{header|Kotlin}}==

{{trans|C++}}

 

typealias Point = Pair<Double, Double>

println("which have only a single corner in contact, if boundary points do not collide")

println(if (triTri2D(t1, t2, 0.0, false, false)) "overlap" else "do not overlap")

 

{{out}}

 

=={{header|Lambdatalk}}==

Here we present a rasterized version based on a single function "isInside".

 

.............................11

..............................1

 

=={{header|Lua}}==

{{trans|C++}}

return p1.x * (p2.y - p3.y)

+ p2.x * (p3.y - p1.y)

print(formatTri(t1).." and")

print(formatTri(t2))

{{out}}

<pre>Triangle: (0, 0), (5, 0), (0, 5) and

Triangle: (1, 0), (2, 0), (1, 1)

overlap</pre>

 

=={{header|Modula-2}}==

FROM EXCEPTIONS IMPORT AllocateSource,ExceptionSource,GetMessage,RAISE;

FROM LongStr IMPORT RealToFixed;

 

ReadChar

 

=={{header|Nim}}==

{{trans|Go}}

 

type Point = tuple[x, y: float]

echo "which have only a single corner in contact, if boundary points do not collide"

overlapping = triTri2D(t1, t2, 0, false, false)

 

{{out}}

 

=={{header|ooRexx}}==

* Determine if two triangles overlap

* Fully (?) tested with integer coordinates of the 6 corners

* This was/is an exercise with ooRexx

* Removed the fraction arithmetic

*-------------------------------------------------------------------*/

Parse Version v

oid='trioo.txt'; 'erase' oid

Call o v

Call trio_test '0 0 1 1 0 2 2 1 3 -2 3 4'

Call trio_test '0 0 1 0 0 1 1 0 2 0 1 1'

Exit

/* Other test cases */

tlist=space(tlist)

tl1=tlist ; Call trio_t tl1

tl2=reversex(tlist) ; Call trio_t tl2

tl3=''

tl4=reversex(tl3) ; Call trio_t tl4

tl5=subword(tl4,7) subword(tl4,1,6) ; Call trio_t tl5

Return

 

Parse Arg tlist

tlist=space(tlist)

case+=1

Parse Arg ax ay bx by cx cy dx dy ex ey fx fy

a=.point~new(ax,ay); b=.point~new(bx,by); c=.point~new(cx,cy)

d=.point~new(dx,dy); e=.point~new(ex,ey); f=.point~new(fx,fy)

abc=.triangle~new(a,b,c)

def=.triangle~new(d,e,f)

expose point edge

use arg p1,p2,p3

point=.array~new

point[1]=p1

res=res word(list,i)

End

{{out}}

Triangle: ABC: (0,0) (4,0) (0,4)

Triangle: DEF: (1,1) (2,1) (1,2)

(1,1) (2,1) (1,2) is fully contained in (0,0) (4,0) (0,4)

 

Triangle: ABC: (2,1) (1,2) (1,1)

Triangle: DEF: (4,0) (0,4) (0,0)

(2,1) (1,2) (1,1) is fully contained in (4,0) (0,4) (0,0)

 

Triangle: ABC: (1,2) (2,1) (1,1)

Triangle: DEF: (0,4) (4,0) (0,0)

(1,2) (2,1) (1,1) is fully contained in (0,4) (4,0) (0,0)

 

Triangle: ABC: (0,0) (0,4) (4,0)

Triangle: DEF: (1,1) (1,2) (2,1)

(1,1) (1,2) (2,1) is fully contained in (0,0) (0,4) (4,0)

 

Triangle: ABC: (1,1) (1,2) (2,1)

Triangle: DEF: (0,0) (0,4) (4,0)

(1,1) (1,2) (2,1) is fully contained in (0,0) (0,4) (4,0)

 

 

Triangle: ABC: (0,0) (0,6) (8,3)

Triangle: DEF: (8,0) (8,8) (0,3)

Corner(s) that touch the other triangle: (0,3) (8,3)

Triangles overlap and touch on (0,3) (8,3)

Triangle: ABC: (3,0) (8,8) (0,8)

Triangle: DEF: (3,8) (6,0) (0,0)

Corner(s) that touch the other triangle: (3,8) (3,0)

Triangles overlap and touch on (3,8) (3,0)

Triangle: ABC: (0,3) (8,8) (8,0)

Triangle: DEF: (8,3) (0,6) (0,0)

Corner(s) that touch the other triangle: (8,3) (0,3)

Triangles overlap and touch on (8,3) (0,3)

Triangle: ABC: (0,0) (6,0) (3,8)

Triangle: DEF: (0,8) (8,8) (3,0)

Corner(s) that touch the other triangle: (3,0) (3,8)

Triangles overlap and touch on (3,0) (3,8)

Triangle: ABC: (0,8) (8,8) (3,0)

Triangle: DEF: (0,0) (6,0) (3,8)

Corner(s) that touch the other triangle: (3,8) (3,0)

Triangles overlap and touch on (3,8) (3,0)

Triangle: ABC: (0,0) (0,2) (2,0)

Triangle: DEF: (0,0) (4,0) (0,6)

Triangles overlap and touch on (0,0) (0,2) (2,0)

 

Triangle: ABC: (6,0) (0,4) (0,0)

Triangle: DEF: (0,2) (2,0) (0,0)

Triangles overlap and touch on (0,2) (2,0) (0,0)

 

Triangle: ABC: (0,6) (4,0) (0,0)

Triangle: DEF: (2,0) (0,2) (0,0)

Triangles overlap and touch on (2,0) (0,2) (0,0)

 

Triangle: ABC: (0,0) (2,0) (0,2)

Triangle: DEF: (0,0) (0,4) (6,0)

Triangles overlap and touch on (0,0) (2,0) (0,2)

 

Triangle: ABC: (0,0) (0,4) (6,0)

Triangle: DEF: (0,0) (2,0) (0,2)

Triangles overlap and touch on (0,0) (2,0) (0,2)

 

 

Triangle: ABC: (0,0) (5,0) (0,5)

Triangle: DEF: (0,0) (5,0) (0,6)

Triangles have an edge in common: (0,0) (5,0)

 

Triangle: ABC: (6,0) (0,5) (0,0)

Triangle: DEF: (5,0) (0,5) (0,0)

Triangles have an edge in common: (0,5) (0,0)

 

Triangle: ABC: (0,6) (5,0) (0,0)

Triangle: DEF: (0,5) (5,0) (0,0)

Triangles have an edge in common: (5,0) (0,0)

 

Triangle: ABC: (0,0) (0,5) (5,0)

Triangle: DEF: (0,0) (0,5) (6,0)

Triangles have an edge in common: (0,0) (0,5)

 

Triangle: ABC: (0,0) (0,5) (6,0)

Triangle: DEF: (0,0) (0,5) (5,0)

Triangles have an edge in common: (0,0) (0,5)

 

 

Triangle: ABC: (0,0) (0,5) (5,0)

Triangle: DEF: (0,0) (0,5) (5,0)

Triangles are identical

 

Triangle: ABC: (0,5) (5,0) (0,0)

Triangle: DEF: (0,5) (5,0) (0,0)

Triangles are identical

 

Triangle: ABC: (5,0) (0,5) (0,0)

Triangle: DEF: (5,0) (0,5) (0,0)

Triangles are identical

 

Triangle: ABC: (0,0) (5,0) (0,5)

Triangle: DEF: (0,0) (5,0) (0,5)

Triangles are identical

 

Triangle: ABC: (0,0) (5,0) (0,5)

Triangle: DEF: (0,0) (5,0) (0,5)

Triangles are identical

 

Triangles are identical

 

Triangle: ABC: (0,0) (5,0) (0,5)

Triangle: DEF: (-10,0) (-5,0) (-1,6)

(0,0) (5,0) (0,5) and (-10,0) (-5,0) (-1,6) don't overlap

 

Triangle: ABC: (6,-1) (0,-5) (0,-10)

Triangle: DEF: (5,0) (0,5) (0,0)

(6,-1) (0,-5) (0,-10) and (5,0) (0,5) (0,0) don't overlap

 

Triangle: ABC: (-1,6) (-5,0) (-10,0)

Triangle: DEF: (0,5) (5,0) (0,0)

(-1,6) (-5,0) (-10,0) and (0,5) (5,0) (0,0) don't overlap

 

Triangle: ABC: (0,0) (0,5) (5,0)

Triangle: DEF: (0,-10) (0,-5) (6,-1)

(0,0) (0,5) (5,0) and (0,-10) (0,-5) (6,-1) don't overlap

 

Triangle: ABC: (0,-10) (0,-5) (6,-1)

Triangle: DEF: (0,0) (0,5) (5,0)

(0,-10) (0,-5) (6,-1) and (0,0) (0,5) (5,0) don't overlap

 

 

Triangle: ABC: (0,0) (5,0) (2.5,5)

Triangle: DEF: (0,4) (2.5,-1) (5,4)

(0,0) (5,0) (2.5,5) and (0,4) (2.5,-1) (5,4) overlap

 

Triangle: ABC: (4,5) (-1,2.5) (4,0)

Triangle: DEF: (5,2.5) (0,5) (0,0)

(4,5) (-1,2.5) (4,0) and (5,2.5) (0,5) (0,0) overlap

 

Triangle: ABC: (5,4) (2.5,-1) (0,4)

Triangle: DEF: (2.5,5) (5,0) (0,0)

(5,4) (2.5,-1) (0,4) and (2.5,5) (5,0) (0,0) overlap

 

Triangle: ABC: (0,0) (0,5) (5,2.5)

Triangle: DEF: (4,0) (-1,2.5) (4,5)

(0,0) (0,5) (5,2.5) and (4,0) (-1,2.5) (4,5) overlap

 

Triangle: ABC: (4,0) (-1,2.5) (4,5)

Triangle: DEF: (0,0) (0,5) (5,2.5)

(4,0) (-1,2.5) (4,5) and (0,0) (0,5) (5,2.5) overlap

 

 

Triangle: ABC: (0,0) (1,1) (0,2)

Triangle: DEF: (2,1) (3,0) (3,2)

(0,0) (1,1) (0,2) and (2,1) (3,0) (3,2) don't overlap

 

Triangle: ABC: (2,3) (0,3) (1,2)

Triangle: DEF: (2,0) (1,1) (0,0)

(2,3) (0,3) (1,2) and (2,0) (1,1) (0,0) don't overlap

 

Triangle: ABC: (3,2) (3,0) (2,1)

Triangle: DEF: (0,2) (1,1) (0,0)

(3,2) (3,0) (2,1) and (0,2) (1,1) (0,0) don't overlap

 

Triangle: ABC: (0,0) (1,1) (2,0)

Triangle: DEF: (1,2) (0,3) (2,3)

(0,0) (1,1) (2,0) and (1,2) (0,3) (2,3) don't overlap

 

Triangle: ABC: (1,2) (0,3) (2,3)

Triangle: DEF: (0,0) (1,1) (2,0)

(1,2) (0,3) (2,3) and (0,0) (1,1) (2,0) don't overlap

 

 

Triangle: ABC: (0,0) (1,1) (0,2)

Triangle: DEF: (2,1) (3,-2) (3,4)

(0,0) (1,1) (0,2) and (2,1) (3,-2) (3,4) don't overlap

 

Triangle: ABC: (4,3) (-2,3) (1,2)

Triangle: DEF: (2,0) (1,1) (0,0)

(4,3) (-2,3) (1,2) and (2,0) (1,1) (0,0) don't overlap

 

Triangle: ABC: (3,4) (3,-2) (2,1)

Triangle: DEF: (0,2) (1,1) (0,0)

(3,4) (3,-2) (2,1) and (0,2) (1,1) (0,0) don't overlap

 

Triangle: ABC: (0,0) (1,1) (2,0)

Triangle: DEF: (1,2) (-2,3) (4,3)

(0,0) (1,1) (2,0) and (1,2) (-2,3) (4,3) don't overlap

 

Triangle: ABC: (1,2) (-2,3) (4,3)

Triangle: DEF: (0,0) (1,1) (2,0)

(1,2) (-2,3) (4,3) and (0,0) (1,1) (2,0) don't overlap

 

 

Triangle: ABC: (0,0) (1,0) (0,1)

Triangle: DEF: (1,0) (2,0) (1,1)

(0,0) (1,0) (0,1) and (1,0) (2,0) (1,1) don't overlap but touch on (1,0)

 

Triangle: ABC: (1,1) (0,2) (0,1)

Triangle: DEF: (1,0) (0,1) (0,0)

(1,1) (0,2) (0,1) and (1,0) (0,1) (0,0) don't overlap but touch on (0,1)

 

Triangle: ABC: (1,1) (2,0) (1,0)

Triangle: DEF: (0,1) (1,0) (0,0)

(1,1) (2,0) (1,0) and (0,1) (1,0) (0,0) overlap and touch on (1,0)

 

Triangle: ABC: (0,0) (0,1) (1,0)

Triangle: DEF: (0,1) (0,2) (1,1)

(0,0) (0,1) (1,0) and (0,1) (0,2) (1,1) don't overlap but touch on (0,1)

 

Triangle: ABC: (0,1) (0,2) (1,1)

Triangle: DEF: (0,0) (0,1) (1,0)

(0,1) (0,2) (1,1) and (0,0) (0,1) (1,0) don't overlap but touch on (0,1)

 

we analyze further

 

=={{header|Pascal}}==

A console application in Free Pascal, created with the Lazarus IDE. It recognizes three possible outcomes: disjoint, positive overlap, and borderline (overlap at a point or line segment).

program TrianglesOverlap;

{

If there's no separator, then the triangles have an overlap of positive area.

}

 

uses Math, SysUtils;

TestTrianglePair( 0,0,1,0,0,1, 1,0,2,0,1,1);

end.

{{out}}

<pre>

=={{header|Perl}}==

===Port of Lua===

use warnings;

 

@t1 = ({x=>0, y=>0}, {x=>1, y=>0}, {x=>0, y=>1});

@t2 = ({x=>1, y=>0}, {x=>2, y=>0}, {x=>1, y=>1});

{{out}}

<pre>Triangle: (0, 0), (5, 0), (0, 5) and

 

===More Idiomatic===

use warnings;

use feature 'say';

);

 

{{out}}

<pre> overlap: (0,0), (5,0), (0,5) and (0,0), (5,0), (0,6)

{{trans|zkl}}

Plus draw all eight pairs of triangles for visual confirmation.

 

=={{header|Python}}==

{{libheader|NumPy}}

Using numpy:

import numpy as np

 

t1 = [[0,0],[1,0],[0,1]]

t2 = [[1,0],[2,0],[1,1]]

 

{{out}}

{{libheader|Shapely}}

Using shapely:

from shapely.geometry import Polygon

 

t1 = [[0,0],[1,0],[0,1]]

t2 = [[1,0],[2,0],[1,1]]

 

{{out}}

 

=={{header|QB64}}==

DATA 0,0,5,0,0,5,0,0,5,0,0,6

DATA 0,0,0,5,5,0,0,0,0,5,5,0

p.y = (10 + p.y) * 30

END SUB

 

=={{header|Racket}}==

{{trans|Zkl}}

 

 

;; A triangle is a list of three pairs of points: '((x . y) (x . y) (x . y))

(check-true (tri-tri-2d? c1 c2 #:on-boundary? #t))

(check-false (tri-tri-2d? c1 c2 #:on-boundary? #f))))

 

No output &rarr; all tests passed

(formerly Perl 6)

First, check if any vertex is inside each other triangle (that should cover most overlapping cases including enclosures). Then see if an edge of triangle A intersects any of two edges of B (for shapes like Star of David [https://en.wikipedia.org/wiki/Star_of_David])

# https://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle

# https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

 

sub if-overlap ($triangle-pair) {

 

sub sign (\T) {

}

 

sub point-in-triangle (\pt, \Y --> Bool) {

 

 

}

 

sub orientation(\P, \Q, \R --> Int) {

 

}

 

sub onSegment(\P, \Q, \R --> Bool) {

}

 

sub intersect(\A,\B,\C,\D --> Bool) {

 

}

 

for ^3 {

}

 

unless $result {

intersect A.[0], A.[1], B.[0], B.[2]

}

 

}

 

];

 

[(0 0) (0 5) (5 0)] and [(0 0) (0 5) (5 0)] do overlap.

[(0 0) (5 0) (0 5)] and [(-10 0) (-5 0) (-1 6)] do NOT overlap.

[(0 0) (1 1) (0 2)] and [(2 1) (3 0) (3 2)] do NOT overlap.

[(0 0) (1 1) (0 2)] and [(2 1) (3 -2) (3 4)] do NOT overlap.

 

=={{header|REXX}}==

Note: The triangles must be real triangles (no edge of length 0)

Signal On Halt

Signal On Novalue

Nop

End

{{out}}

<pre>ABC: (0/0) (5/0) (0/5)

=={{header|Ruby}}==

{{trans|C}}

 

def det2D(p1, p2, p3)

end

 

{{out}}

<pre>Triangle: [Vector[0, 0], Vector[5, 0], Vector[0, 5]]

=={{header|Scala}}==

{{trans|Kotlin}}

type Point = (Double, Double)

 

println(if (triTri2D(t1, t2, onBoundary = false)) "overlap" else "do not overlap")

}

{{out}}

<pre>Triangle: (0.0,0.0), (5.0,0.0), (0.0,5.0) and

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Class Triangle

End Sub

 

{{out}}

<pre>Triangle: (0, 0), (5, 0), (0, 5) and

which have only a single corner in contact, if boundary points do not collide

do not overlap</pre>

 

=={{header|zkl}}==

{{trans|C++}}

 

fcn det2D(triangle){

}

True // The triangles collide

vm.arglist.apply("toFloat").pump(List,Void.Read)

}

c1,c2 := toTri(0,0, 1,0, 0,1), toTri(1,0, 2,0, 1,1);

println("Corner case (barely touching): ",triTri2D(c1,c2,0.0,False,True)); // True

{{out}}

<pre>