Determine if two triangles overlap: Difference between revisions
Content added Content deleted
m (added related tasks) |
(Added Algol 68 using the Check if two polygons overlap code.) |
||
Line 219: | Line 219: | ||
false |
false |
||
true |
true |
||
</pre> |
|||
=={{header|ALGOL 68}}== |
|||
Uses the code from the Algol 68 sample for the [[Check if two polygons overlap]] task.<br> |
|||
Triangles with a single point in contact are considerfed to overlap. |
|||
<syntaxhighlight lang="algol68"> |
|||
BEGIN # test for overlapping 2D triangles - using the code from the Algol 68 # |
|||
# sample for the Check if two polygons overlap task, the code of which # |
|||
# is based on a translation of that tasks' Go which is a translation # |
|||
# of Wren # |
|||
# In the following a polygon is represented as a row of vertices # |
|||
# and a vertex ( POINT ) by a pair of x, y coordinates in the plane # |
|||
MODE POINT = STRUCT( REAL x, y ); |
|||
MODE PROJECTION = STRUCT( REAL min, max ); |
|||
MODE POLYGON = FLEX[ 1 : 0 ]POINT; |
|||
PRIO DOT = 3; |
|||
OP DOT = ( POINT v, other )REAL: |
|||
( x OF v * x OF other ) + ( y OF v * y OF other ); |
|||
# returns the axes of the polygon defined by poly # |
|||
OP AXES = ( POLYGON poly )[]POINT: |
|||
BEGIN |
|||
[ LWB poly : UPB poly ]POINT result; |
|||
FOR i FROM LWB poly TO UPB poly DO |
|||
INT j = IF i = UPB poly THEN LWB poly ELSE i + 1 FI; |
|||
POINT vertex1 = poly[ i ]; |
|||
POINT vertex2 = poly[ j ]; |
|||
POINT edge = ( x OF vertex1 - x OF vertex2, y OF vertex1 - y OF vertex2 ); |
|||
result[ i ] := ( - y OF edge, x OF edge ) |
|||
OD; |
|||
result |
|||
END # AXES # ; |
|||
# returns the projection of poly onto axis # |
|||
PRIO PROJECTONTO = 3; |
|||
OP PROJECTONTO = ( POLYGON poly, POINT axis )PROJECTION: |
|||
BEGIN |
|||
REAL min := axis DOT poly[ LWB poly ]; |
|||
REAL max := min; |
|||
FOR i FROM LWB poly + 1 TO UPB poly DO |
|||
REAL p = axis DOT poly[ i ]; |
|||
IF p < min THEN |
|||
min := p |
|||
ELIF p > max THEN |
|||
max := p |
|||
FI |
|||
OD; |
|||
PROJECTION( min, max ) |
|||
END # PROJECTONTO # ; |
|||
PRIO OVERLAPS = 5; |
|||
# returns TRUE if the projections proj1 and proj2 overlap, # |
|||
# FALSE otherrwise # |
|||
OP OVERLAPS = ( PROJECTION proj1, proj2 )BOOL: |
|||
IF max OF proj1 < min OF proj2 THEN FALSE |
|||
ELIF max OF proj2 < min OF proj1 THEN FALSE |
|||
ELSE TRUE |
|||
FI # OVERLAPS # ; |
|||
# returns TRUE if the ppolygons poly1 and poly2 overlap, # |
|||
# FALSE otherrwise # |
|||
OP OVERLAPS = ( POLYGON poly1, poly2 )BOOL: |
|||
BEGIN |
|||
[]POINT axes1 = AXES poly1, axes2 = AXES poly2; |
|||
BOOL does overlap := TRUE; |
|||
FOR a FROM LWB axes1 TO UPB axes1 WHILE does overlap DO |
|||
does overlap := ( poly1 PROJECTONTO axes1[ a ] ) |
|||
OVERLAPS ( poly2 PROJECTONTO axes1[ a ] ) |
|||
OD; |
|||
FOR a FROM LWB axes2 TO UPB axes2 WHILE does overlap DO |
|||
does overlap := ( poly1 PROJECTONTO axes2[ a ] ) |
|||
OVERLAPS ( poly2 PROJECTONTO axes2[ a ] ) |
|||
OD; |
|||
does overlap |
|||
END # OVERLAPS # ; |
|||
# returns x as a string without trailing 0 decoimals # |
|||
OP TOSTRING = ( REAL x )STRING: |
|||
BEGIN |
|||
STRING v := fixed( x, -14, 11 ); |
|||
INT end pos := UPB v; |
|||
WHILE IF end pos < LWB v THEN FALSE ELSE v[ end pos ] = "0" FI DO |
|||
end pos -:= 1 |
|||
OD; |
|||
IF end pos >= LWB v THEN |
|||
IF v[ end pos ] = "." THEN end pos -:= 1 FI |
|||
FI; |
|||
INT start pos := LWB v; |
|||
WHILE IF start pos > end pos THEN FALSE ELSE v[ start pos ] = " " FI DO |
|||
start pos +:= 1 |
|||
OD; |
|||
IF end pos < start pos THEN "0" ELSE v[ start pos : end pos ] FI |
|||
END # TOSTRING # ; |
|||
# returns a string representation of the POINT p # |
|||
OP TOSTRING = ( POINT p )STRING: "( " + TOSTRING x OF p + ", " + TOSTRING y OF p + " )"; |
|||
# returns a string representation of the points of p # |
|||
OP TOSTRING = ( POLYGON p )STRING: |
|||
BEGIN |
|||
STRING result := "(", separator := ""; |
|||
FOR i FROM LWB p TO UPB p DO |
|||
result +:= separator + " " + TOSTRING p[ i ]; |
|||
separator := "," |
|||
OD; |
|||
result + " )" |
|||
END # TOSTRING # ; |
|||
# code specific to thius task # |
|||
# test cases - using the general POLYGON MODE to represent triangles # |
|||
[,]POLYGON triangle pairs |
|||
= ( ( ( ( 0, 0 ), ( 5, 0 ), ( 0, 5 ) ), ( ( 0, 0 ), ( 5, 0 ), ( 0, 6 ) ) ) |
|||
, ( ( ( 0, 0 ), ( 0, 5 ), ( 5, 0 ) ), ( ( 0, 0 ), ( 0, 5 ), ( 5, 0 ) ) ) |
|||
, ( ( ( 0, 0 ), ( 5, 0 ), ( 0, 5 ) ), ( (-10, 0 ), ( -5, 0 ), ( -1, 6 ) ) ) |
|||
, ( ( ( 0, 0 ), ( 5, 0 ), ( 2.5, 5 ) ), ( ( 0, 4 ), ( 2.5, -1 ), ( 5, 4 ) ) ) |
|||
, ( ( ( 0, 0 ), ( 1, 1 ), ( 0, 2 ) ), ( ( 2, 1 ), ( 3, 0 ), ( 3, 2 ) ) ) |
|||
, ( ( ( 0, 0 ), ( 1, 1 ), ( 0, 2 ) ), ( ( 2, 1 ), ( 3, -2 ), ( 3, 4 ) ) ) |
|||
, ( ( ( 0, 0 ), ( 1, 0 ), ( 0, 1 ) ), ( ( 1, 0 ), ( 2, 0 ), ( 1, 1 ) ) ) |
|||
); |
|||
FOR t pos FROM LWB triangle pairs TO UPB triangle pairs DO |
|||
[]POLYGON tpair = triangle pairs[ t pos, : ]; |
|||
POLYGON t1 = tpair[ LWB tpair ]; |
|||
POLYGON t2 = tpair[ UPB tpair ]; |
|||
print( ( TOSTRING t1 |
|||
, IF t1 OVERLAPS t2 THEN " overlaps " ELSE " does not overlap " FI |
|||
, TOSTRING t2 |
|||
, newline |
|||
) |
|||
) |
|||
OD |
|||
END |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
( ( 0, 0 ), ( 5, 0 ), ( 0, 5 ) ) overlaps ( ( 0, 0 ), ( 5, 0 ), ( 0, 6 ) ) |
|||
( ( 0, 0 ), ( 0, 5 ), ( 5, 0 ) ) overlaps ( ( 0, 0 ), ( 0, 5 ), ( 5, 0 ) ) |
|||
( ( 0, 0 ), ( 5, 0 ), ( 0, 5 ) ) does not overlap ( ( -10, 0 ), ( -5, 0 ), ( -1, 6 ) ) |
|||
( ( 0, 0 ), ( 5, 0 ), ( 2.5, 5 ) ) overlaps ( ( 0, 4 ), ( 2.5, -1 ), ( 5, 4 ) ) |
|||
( ( 0, 0 ), ( 1, 1 ), ( 0, 2 ) ) does not overlap ( ( 2, 1 ), ( 3, 0 ), ( 3, 2 ) ) |
|||
( ( 0, 0 ), ( 1, 1 ), ( 0, 2 ) ) does not overlap ( ( 2, 1 ), ( 3, -2 ), ( 3, 4 ) ) |
|||
( ( 0, 0 ), ( 1, 0 ), ( 0, 1 ) ) overlaps ( ( 1, 0 ), ( 2, 0 ), ( 1, 1 ) ) |
|||
</pre> |
</pre> |
||