Polygon Transformations

Scope
This lab exemplifies practical applications of various transformations of polygons.

All algorithms were prototyped into a software implementation, using the Perl language (http://www.perl.com/), and the various functions will be explained throughout this exercise. Although the implementation level may be language specific, the underlying algorithms are common geometric formulas, which can be applied to any software / programming integrated development environment.

Answers to questions are outlined in bold
Code examples are outlined in courier

Software Setup

The nature of this software implementation was as follows:

Library of geometric functions: This consists of a generic implementation of the geometric formulas, which, as a software library, can be reused by subsequent application developers. We have named this geomath.pm in this context.
Implementation level interface script: This script contains the specific information pertaining to the exercise, and passes this information to the geometric functions as arguments. We have named this mathex2.pl in this context.

Constants

We have defined the following constants in our library:

use constant pi => 3.14159;
use constant earthRadius => 6371;

Generic Functions

The following generic functions were implemented as general purpose routines.

sub deg2rad { # degrees to radians
  my $degreeNum = $_[0];
  my $radianNum = $degreeNum * ($pi / 180);
  return $radianNum;
}

sub rad2deg { # radians to degrees
  my $radianNum = $_[0];
  my $degreeNum = $radianNum * (180 / $pi);
  return $degreeNum;
}

sub dd2dms { # decimal degrees to degrees minutes seconds
  my ($D, $d) = split /\./, $_[0];
  $d = "." . $d;
  my $Mm = $d * 60;
  my @tmp = split /\./, $Mm;
  my $S = $1 if ($tmp[1] * 60) =~ /^(\d{2})/;
  return "$D $tmp[0] $S";
}

sub dms2dd { # degrees minutes seconds to decimal degrees
  my ($d, $m, $s) = split / /, $_[0];
  my $dd = $d + ($m / 60) + ($s / 3600);
  return $dd;
}

sub getMaxVal { # returns greater of two numbers
  my $val1 = $_[0];
  my $val2 = $_[1];

  if ($val1 > $val2) {
    return $val1;
  }
  if ($val1 < $val2) {
    return $val2;
  }
  if ($val1 == $val2) {
    return $val1;
  }
}

sub getMinVal { # returns lesser of two numbers
  my $val1 = $_[0];
  my $val2 = $_[1];

  if ($val1 < $val2) {
    return $val1;
  }
  if ($val1 > $val2) {
    return $val2;
  }
  if ($val1 == $val2) {
    return $val1;
  }
}

Polygon Definition

The polygon we will perform calculations on is defined as follows:

We define the polygon as arrays in Perl:

my @xList = (2, 1, 3, 6, 5, 2);
my @yList = (1, 5, 6, 5, 1, 1);

my $arrLength = scalar(@xList);

Scaling

The following code was implemented to scale an XY point:

sub scaleXY {
  my $theX        = $_[0];
  my $theY        = $_[1];
  my $scaleFactor = $_[2];

  my $newX = $theX * $scaleFactor;
  my $newY = $theY * $scaleFactor;
  return "$newX,$newY";
}

..and is called from our implementation script as follows:

for(my $i = 0; $i < $arrLength; $i++) {
  print scaleXY($xList[$i], $yList[$i], 0.7) . "\n";
}

..which produces the following result.

Polygon scaled using a factor of 0.7:
1.4,0.7
0.7,3.5
2.1,4.2
4.2,3.5
3.5,0.7
1.4,0.7

Coordinate Shifting

Shifting coordinates were implemented as a function as per the library below:

sub translateXY {
  my $theX   = $_[0];
  my $theY   = $_[1];
  my $shiftX = $_[2];
  my $shiftY = $_[3];

  my $newX = $theX + $shiftX;
  my $newY = $theY + $shiftY;
  return "$newX,$newY";
}

Here's the implementation level source code:

for(my $i = 0; $i < $arrLength; $i++) {
  print translateXY($xList[$i], $yList[$i], -3, -2) . "\n";
}

..producing the following results:

Polygon translated using a shift of -3, -2
-1,-1
-2, 3
 0, 4
 3, 3
 2,-1
-1,-1

Coordinate Rotation

The rotation of an XY point is defined below; varying calculations are used depending on the rotation origin given:

sub rotateXY {
  my $theX            = $_[0];
  my $theY            = $_[1];
  my $rotationTheta   = $_[2];
  my $rotationOriginX = $_[3];
  my $rotationOriginY = $_[4];

  my $newX;
  my $newY;

  if ($rotationOriginX == 0 && $rotationOriginY == 0) {
    $newX = $theX * cos(deg2rad($rotationTheta)) - sin(deg2rad($rotationTheta)) * $theY;
    $newY = $theX * sin(deg2rad($rotationTheta)) + cos(deg2rad($rotationTheta)) * $theY;
  }
  else {
    $newX = ($theX - $rotationOriginX) * cos(deg2rad($rotationTheta)) - ($theY - $rotationOriginY) * sin($r
otationTheta) + $rotationOriginX;
    $newY = ($theX - $rotationOriginX) * sin(deg2rad($rotationTheta)) + ($theY - $rotationOriginY) * cos($r
otationTheta) + $rotationOriginY;
  }
  return "$newX,$newY";
}

..along with the implementation of the function to work on our polygon:

for(my $i = 0; $i < $arrLength; $i++) {
  print rotateXY($xList[$i], $yList[$i], 90, 0, 0) . "\n";
}

Polygon rotated 90 degress clockwise about the 0, 0 origin:

-0.999997346409326, 2.00000132679314
-4.9999986732007,   1.0000066339736
-5.99999601961003,  3.00000796076674
-4.99999203922622,  6.0000066339692
-0.999993366024636, 5.0000013267905
-0.999997346409326, 2.00000132679314

The following calculations provide an example of a non 0,0 origin when rotating:

for(my $i = 0; $i < $arrLength; $i++) {
  print rotateXY($xList[$i], $yList[$i], -30, 2, 2) . "\n";
}

Polygon rotated 30 degrees clockwise about the point 2, 2:

2.98803162409286,  1.84574855011242
-1.83012049719542, 2.96275396665001
-1.08610087145461, 2.11700618256308
2.50000762738876,  0.462755881713729
5.58610849884337,  0.345749699150649
2.98803162409286,  1.84574855011242

Polygon Transformations: Scaling, Shifting, Rotating Variations

The function library proves useful for reusing the code in a wide variety of applications and calculations. Here we use the various functions within our library to perform combinations of calculations on our polygon.

To transform the polygon using a scale factor of 0.5 and a translation shift of 3, 2:
Implementation:

for(my $i = 0; $i < $arrLength; $i++) {
  my @tmpVal = split /,/, scaleXY($xList[$i], $yList[$i], 0.5);
  print translateXY($tmpVal[0], $tmpVal[1], 3, 2) . "\n";
}

Results:


4,2.5
3.5,4.5
4.5,5
6,4.5
5.5,2.5
4,2.5

To transform the polygon using rotation of 15 degrees clockwise and a translation shift of 3, 4:
Implementation:

for(my $i = 0; $i < $arrLength; $i++) {
  my @tmpVal = split /,/, rotateXY($xList[$i], $yList[$i], 15, 0, 0);
  print translateXY($tmpVal[0], $tmpVal[1], 3, 4) . "\n";
}

Results:


4.67303293553975,  5.48356354653222
2.67183172599765,  9.08844824911665
4.3448646615374,  10.5720117956489
7.50146114360937, 10.3825424066413
7.57081058610678,  6.26002004104703
4.67303293553975,  5.48356354653222

To transform a polygon using a scale factor of 0.5, a counterclockwise rotation of 15 degrees, and translation shift of -1, 2.
Implementation:

for(my $i = 0; $i < $arrLength; $i++) {
  my @tmpVal  = split /,/, scaleXY($xList[$i], $yList[$i], 0.5);
  my @tmpVal2 = split /,/, rotateXY($tmpVal[0], $tmpVal[1], -15, 0, 0);
  print translateXY($tmpVal2[0], $tmpVal2[1], -1, 2) . "\n";
}

Results:


0.09533529927481,2.22414411025623
0.13001002052352,4.28540529305339
1.22534531979833,4.50954940330962
2.54482472932937,3.63835821429104
1.54422412455833,1.83591586299883
0.09533529927481,2.22414411025623

Testing and Observations

When we attempt to apply a scale factor of -1 to our polygon vertices, we produce the following results:


-2,-1
-1,-5
-3,-6
-6,-5
-5,-1
-2,-1

..which, when applying a rotation angle of 180 degrees clockwise, garners the same results.

When applying rotations to XY points in degrees, one can always derive the opposite direction rotation angle by generating the difference of the first angle with 360. For example, a rotation of -340 degrees produces the following results:


1.53735695953148,   1.6237406132077
-0.770433360429789, 5.04047938564745
0.766923599101692,  6.66421999885515
3.92802117184087,   6.75060365253137
4.35642967889388,   2.64981517333805
1.53735695953148,   1.6237406132077

This is the same as rotating the polygon by 20 degrees (as a positive rotation angle).

When applying a scale factor of 0, this causes all coordinates to be set to the value 0.

Considerations when Performing Complex Transformations

One must take into account various considerations when applying complex, multi-level coordinate calculations, such as the calculations described earlier. The first consideration, for any calculation is to be aware that some functions (sin, cos, tan) work with numbers as radians. Hence, we applied the deg2rad function to the appropriate functions as needed.

In addition, it is also important to be aware of the order of operations. Shifting then scaling produces different results than that of scaling then shifting. This occurs because the subsequent operations on the point data are calculated using the derived values of the previous operation.

For example, the following two implementations were written to illustrate the variation:

for(my $i = 0; $i < $arrLength; $i++) {
  my @tmpVal = split /,/, translateXY($xList[$i], $yList[$i], 3, 4);
  print scaleXY($tmpVal[0], $tmpVal[1], 2) . "\n";
}

Results of shift, then scale:


10,10
8,18
12,20
18,18
16,10
10,10


for(my $i = 0; $i < $arrLength; $i++) {
  my @tmpVal = split /,/, scaleXY($xList[$i], $yList[$i], 2);
  print translateXY($tmpVal[0], $tmpVal[1], 3, 4) . "\n";
}

Results of scale, then shift:


7,6
5,14
9,16
15,14
13,6
7,6

As a result, even if the same operations are being performed on coordinate data, much caution should be exercised in the order of operations, and that the method of order be consistent (and documented!) accordingly.

The entire implementation program is available for download from:
mathex2.pl

The library is available for download from:
geomath.pm

Analytical and Computer Cartography Home