test/src/TestGeoClip.cpp

   1 /* Copyright_License {
   2
   3   XCSoar Glide Computer - http://www.xcsoar.org/
   4   Copyright (C) 2000-2013 The XCSoar Project
   5   A detailed list of copyright holders can be found in the file "AUTHORS".
   6
   7   This program is free software; you can redistribute it and/or
   8   modify it under the terms of the GNU General Public License
   9   as published by the Free Software Foundation; either version 2
  10   of the License, or (at your option) any later version.
  11
  12   This program is distributed in the hope that it will be useful,
  13   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15   GNU General Public License for more details.
  16
  17   You should have received a copy of the GNU General Public License
  18   along with this program; if not, write to the Free Software
  19   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  20 }
  21 */
  22
  23 #include "Geo/GeoClip.hpp"
  24 #include "TestUtil.hpp"
  25
  26 #include <stdio.h>
  27
  28 static inline GeoPoint
  29 make_geo_point(int longitude, int latitude)
  30 {
  31   return GeoPoint(Angle::Degrees(longitude),
  32                   Angle::Degrees(latitude));
  33 }
  34
  35 static void
  36 test_ClipLine(const GeoClip &clip, GeoPoint a, GeoPoint b,
  37                const GeoPoint a2, const GeoPoint b2)
  38 {
  39   clip.ClipLine(a, b);
  40   ok1(equals(a, a2));
  41   ok1(equals(b, b2));
  42 }
  43
  44 static void
  45 test_clip_line()
  46 {
  47   GeoClip clip(GeoBounds(make_geo_point(2, 5), make_geo_point(6, 1)));
  48
  49   /* no clipping */
  50   test_ClipLine(clip, make_geo_point(2, 5), make_geo_point(6, 1),
  51                 make_geo_point(2, 5), make_geo_point(6, 1));
  52
  53   /* clipping at east border */
  54   test_ClipLine(clip, make_geo_point(2, 4), make_geo_point(7, 4),
  55                 make_geo_point(2, 4), make_geo_point(6, 4));
  56
  57   /* clipping east & west */
  58   test_ClipLine(clip, make_geo_point(1, 4), make_geo_point(7, 4),
  59                 make_geo_point(2, 4), make_geo_point(6, 4));
  60
  61   /* clipping north */
  62   test_ClipLine(clip, make_geo_point(3, 7), make_geo_point(3, 2),
  63                 make_geo_point(3, 5), make_geo_point(3, 2));
  64
  65   /* clipping north & south */
  66   test_ClipLine(clip, make_geo_point(3, 7), make_geo_point(3, -1000),
  67                 make_geo_point(3, 5), make_geo_point(3, 1));
  68
  69   /* clipping southwest */
  70   test_ClipLine(clip, make_geo_point(5, 2), make_geo_point(7, 0),
  71                 make_geo_point(5, 2), make_geo_point(6, 1));
  72
  73   /* clipping northwest & southeast */
  74   test_ClipLine(clip, make_geo_point(0, 9), make_geo_point(9, -3),
  75                 make_geo_point(3, 5), make_geo_point(6, 1));
  76 }
  77
  78 static int
  79 find(const GeoPoint *haystack, unsigned size, const GeoPoint needle)
  80 {
  81   for (unsigned i = 0; i < size; ++i)
  82     if (equals(haystack[i], needle))
  83       return i;
  84   return -1;
  85 }
  86
  87 static bool
  88 equals(const GeoPoint *a, unsigned a_size, const GeoPoint *b, unsigned b_size)
  89 {
  90   if (a_size != b_size)
  91     return false;
  92
  93   if (a_size == 0)
  94     return true;
  95
  96   int offset = find(b, b_size, *a);
  97   if (offset < 0)
  98     return false;
  99
 100   for (unsigned i = 0; i < a_size; ++i) {
 101     unsigned j = (i + offset) % a_size;
 102     if (!equals(a[i], b[j]))
 103       return false;
 104   }
 105
 106   return true;
 107 }
 108
 109 static void
 110 test_clip_polygon(const GeoClip &clip, const GeoPoint *src, unsigned src_size,
 111                   const GeoPoint *result, unsigned result_size)
 112 {
 113   GeoPoint dest[64];
 114   unsigned dest_size = clip.ClipPolygon(dest, src, src_size);
 115   ok1(equals(result, result_size, dest, dest_size));
 116 }
 117
 118 static void
 119 test_clip_polygon()
 120 {
 121   GeoClip clip(GeoBounds(make_geo_point(2, 5), make_geo_point(6, 1)));
 122
 123   /* invalid polygon */
 124   const GeoPoint src1[2] = {
 125     make_geo_point(0, 0),
 126     make_geo_point(1, 1),
 127   };
 128
 129   test_clip_polygon(clip, src1, 0, NULL, 0);
 130   test_clip_polygon(clip, src1, 1, NULL, 0);
 131   test_clip_polygon(clip, src1, 2, NULL, 0);
 132
 133   /* no clipping */
 134   const GeoPoint src2[3] = {
 135     make_geo_point(3, 4),
 136     make_geo_point(5, 4),
 137     make_geo_point(3, 2),
 138   };
 139   test_clip_polygon(clip, src2, 3, src2, 3);
 140
 141   /* one vertex clipped */
 142   const GeoPoint src3[3] = {
 143     make_geo_point(3, 4),
 144     make_geo_point(9, 4),
 145     make_geo_point(3, 2),
 146   };
 147   const GeoPoint result3[4] = {
 148     make_geo_point(3, 4),
 149     make_geo_point(6, 4),
 150     make_geo_point(6, 3),
 151     make_geo_point(3, 2),
 152   };
 153   test_clip_polygon(clip, src3, 3, result3, 4);
 154
 155   /* two vertices clipped */
 156   const GeoPoint src4[3] = {
 157     make_geo_point(1, 4),
 158     make_geo_point(9, 4),
 159     make_geo_point(3, 2),
 160   };
 161   const GeoPoint result4[5] = {
 162     make_geo_point(2, 3),
 163     make_geo_point(2, 4),
 164     make_geo_point(6, 4),
 165     make_geo_point(6, 3),
 166     make_geo_point(3, 2),
 167   };
 168   test_clip_polygon(clip, src4, 3, result4, 5);
 169
 170   /* clipping a secant */
 171   const GeoPoint src5[3] = {
 172     make_geo_point(1, 2),
 173     make_geo_point(3, 2),
 174     make_geo_point(3, 0),
 175   };
 176   const GeoPoint result5[4] = {
 177     make_geo_point(2, 1),
 178     make_geo_point(2, 2),
 179     make_geo_point(3, 2),
 180     make_geo_point(3, 1),
 181   };
 182   test_clip_polygon(clip, src5, 3, result5, 4);
 183
 184   /* all four vertices clipped */
 185   const GeoPoint src6[4] = {
 186     make_geo_point(1, 3),
 187     make_geo_point(4, 6),
 188     make_geo_point(7, 3),
 189     make_geo_point(4, 0),
 190   };
 191   const GeoPoint result6[8] = {
 192     make_geo_point(2, 4),
 193     make_geo_point(3, 5),
 194     make_geo_point(5, 5),
 195     make_geo_point(6, 4),
 196     make_geo_point(6, 2),
 197     make_geo_point(5, 1),
 198     make_geo_point(3, 1),
 199     make_geo_point(2, 2),
 200   };
 201   test_clip_polygon(clip, src6, 4, result6, 8);
 202
 203   /* rectangle full clip */
 204   const GeoPoint src7[4] = {
 205     make_geo_point(-10, -10),
 206     make_geo_point(-10, 10),
 207     make_geo_point(10, 10),
 208     make_geo_point(10, -10),
 209   };
 210   const GeoPoint result7[4] = {
 211     make_geo_point(2, 1),
 212     make_geo_point(2, 5),
 213     make_geo_point(6, 5),
 214     make_geo_point(6, 1),
 215   };
 216   test_clip_polygon(clip, src7, 4, result7, 4);
 217
 218   /* triangle full clip */
 219   const GeoPoint src8[3] = {
 220     make_geo_point(-10, 50),
 221     make_geo_point(50, 5),
 222     make_geo_point(-5, -50),
 223   };
 224   test_clip_polygon(clip, src8, 3, result7, 4);
 225 }
 226
 227 int main(int argc, char **argv)
 228 {
 229   plan_tests(24);
 230
 231   test_clip_line();
 232   test_clip_polygon();
 233
 234   return exit_status();
 235 }