Check if a polygon overlaps with a rectangle: Difference between revisions

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

Basically the same as the Algol 68 sample for the [[Check if two polygons overlap]] task, with added rectangle handling and using the same test cases as the Wren and other samples.

The Algol 68 Check if two polygons overlap sample was based on that task's Go sample.

<syntaxhighlight lang="algol68">

BEGIN # test whether a 2D polygon overlaps a rectangle #

# - based on a translation 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 #

# most of this is verbatim from the check if two polygons overlap task #

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 polygons 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 # ;

# begin additional code for this task #

# a rectangle is represented by its lower left corner, width and height #

MODE RECTANGLE = STRUCT( POINT corner, REAL width, height );

# returns a POLYGON equivalent to the RECTANGLE r #

OP TOPOLYGON = ( RECTANGLE r )POLYGON:

( corner OF r

, ( x OF corner OF r, y OF corner OF r + height OF r )

, ( x OF corner OF r + width OF r, y OF corner OF r + height OF r )

, ( x OF corner OF r + width OF r, y OF corner OF r )

);

# returns TRUE if the POLYGON poly and RECTANGLE rect overlap, #

# FALSE otherrwise #

OP OVERLAPS = ( POLYGON poly, RECTANGLE rect )BOOL: poly OVERLAPS TOPOLYGON rect;

# returns a string representation of the rectangle r #

OP TOSTRING = ( RECTANGLE r )STRING:

"( " + TOSTRING corner OF r + ", " + TOSTRING width OF r + ", " + TOSTRING height OF r + " )";

# end additional code for this task #

# test cases #

POLYGON poly1 = ( ( 0, 0 ), ( 0, 2 ), ( 1, 4 ), ( 2, 2 ), ( 2, 0 ) );

RECTANGLE rect1 = ( ( 4, 0 ), 2, 2), rect2 = ( ( 1, 0 ), 8, 2);

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

print( ( "rect1 = ", TOSTRING rect1, " => ", TOSTRING TOPOLYGON rect1, newline ) );

print( ( "rect2 = ", TOSTRING rect2, " => ", TOSTRING TOPOLYGON rect2, newline ) );

print( ( newline ) );

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

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

END

</syntaxhighlight>

{{out}}

<pre>

poly1 = ( ( 0, 0 ), ( 0, 2 ), ( 1, 4 ), ( 2, 2 ), ( 2, 0 ) )

rect1 = ( ( 4, 0 ), 2, 2 ) => ( ( 4, 0 ), ( 4, 2 ), ( 6, 2 ), ( 6, 0 ) )

rect2 = ( ( 1, 0 ), 8, 2 ) => ( ( 1, 0 ), ( 1, 2 ), ( 9, 2 ), ( 9, 0 ) )

poly1 and rect1 overlap? no

poly1 and rect2 overlap? yes

</pre>