Check if two polygons overlap: Difference between revisions

=={{header|ALGOL 68}}==

{{Trans|Go|but using operators instead of functions}}

<syntaxhighlight lang="algol68">

BEGIN # test for overlapping 2D polygons #

# - translation Go which is a translation of Wren #

MODE VECTORTWO = STRUCT( REAL x, y );

MODE PROJECTION = STRUCT( REAL min, max );

PRIO DOT = 3;

OP DOT = ( VECTORTWO v, other )REAL:

( x OFv * x OF other ) + ( y OF v * y OF other );

# returns a VECTORTWO containing the two elements of v #

OP TOVECTORTWO = ( []REAL v )VECTORTWO: VECTORTWO( v[ LWB v ], v[ LWB v + 1 ] );

# returns the axes of the polygon defined by poly #

# In the following a polygon is represented as a row of vertices #

# and a vertex by a pair of x, y coordinates in the plane, so the bounds #

# of each vertex must be m : m + 1 for some m, e.g.: 1 : 2. #

OP AXES = ( [,]REAL poly )[]VECTORTWO:

BEGIN

[ LWB poly : UPB poly ]VECTORTWO result;

FOR i FROM LWB poly TO UPB poly DO

INT j = IF i = UPB poly THEN LWB poly ELSE i + 1 FI;

[]REAL vertex1 = poly[ i, : ];

[]REAL vertex2 = poly[ j, : ];

VECTORTWO vector1 = TOVECTORTWO vertex1;

VECTORTWO vector2 = TOVECTORTWO vertex2;

VECTORTWO edge = ( x OF vector1 - x OF vector2, y OF vector1 - y OF vector2 );

result[ i ] := ( - y OF edge, x OF edge )

OD;

result

END # AXES # ;

# returns the projection of poly onto axis - the bounds of poly must be: #

# a : b, m : m + 1 #

PRIO PROJECTONTO = 3;

OP PROJECTONTO = ( [,]REAL poly, VECTORTWO axis )PROJECTION:

BEGIN

REAL min := axis DOT TOVECTORTWO poly[ LWB poly, : ];

REAL max := min;

FOR i FROM LWB poly + 1 TO UPB poly DO

REAL p = axis DOT TOVECTORTWO 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 = ( [,]REAL poly1, poly2 )BOOL:

BEGIN

[]VECTORTWO 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 values of p #

OP TOSTRING = ( []REAL 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 # ;

# returns a string representation of the values of p #

OP TOSTRING = ( [,]REAL 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 # ;

# test cases #

[,]REAL poly1 = ( ( 0, 0 ), ( 0, 2 ), ( 1, 4 ), ( 2, 2 ), ( 2, 0 ) )

, poly2 = ( ( 4, 0 ), ( 4, 2 ), ( 5, 4 ), ( 6, 2 ), ( 6, 0 ) )

, poly3 = ( ( 1, 0 ), ( 1, 2 ), ( 5, 4 ), ( 9, 2 ), ( 9, 0 ) )

;

print( ( "poly1 = ", TOSTRING poly2, newline ) );

print( ( "poly2 = ", TOSTRING poly2, newline ) );

print( ( "poly3 = ", TOSTRING poly3, newline ) );

print( ( newline ) );

print( ( "poly1 and poly2 overlap? ", IF poly1 OVERLAPS poly2 THEN "yes" ELSE "no" FI, newline ) );

print( ( "poly1 and poly3 overlap? ", IF poly1 OVERLAPS poly3 THEN "yes" ELSE "no" FI, newline ) );

print( ( "poly2 and poly3 overlap? ", IF poly2 OVERLAPS poly3 THEN "yes" ELSE "no" FI, newline ) )

END

</syntaxhighlight>

{{out}}

<pre>

poly1 = ( ( 4, 0 ), ( 4, 2 ), ( 5, 4 ), ( 6, 2 ), ( 6, 0 ) )

poly2 = ( ( 4, 0 ), ( 4, 2 ), ( 5, 4 ), ( 6, 2 ), ( 6, 0 ) )

poly3 = ( ( 1, 0 ), ( 1, 2 ), ( 5, 4 ), ( 9, 2 ), ( 9, 0 ) )

poly1 and poly2 overlap? no

poly1 and poly3 overlap? yes

poly2 and poly3 overlap? yes

</pre>