src/Geo/GeoClip.cpp

   1 /*
   2 Copyright_License {
   3
   4   XCSoar Glide Computer - http://www.xcsoar.org/
   5   Copyright (C) 2000-2013 The XCSoar Project
   6   A detailed list of copyright holders can be found in the file "AUTHORS".
   7
   8   This program is free software; you can redistribute it and/or
   9   modify it under the terms of the GNU General Public License
  10   as published by the Free Software Foundation; either version 2
  11   of the License, or (at your option) any later version.
  12
  13   This program is distributed in the hope that it will be useful,
  14   but WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16   GNU General Public License for more details.
  17
  18   You should have received a copy of the GNU General Public License
  19   along with this program; if not, write to the Free Software
  20   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  21 }
  22 */
  23
  24 #include "Geo/GeoClip.hpp"
  25 #include "Compiler.h"
  26
  27 #include <assert.h>
  28
  29 gcc_const
  30 static GeoPoint
  31 clip_longitude(const GeoPoint origin, const GeoPoint pt, Angle at)
  32 {
  33   Angle dx = pt.longitude - origin.longitude;
  34   Angle dy = pt.latitude - origin.latitude;
  35
  36   Angle ex = at - origin.longitude;
  37   Angle ey = ex * (dy.Native() / dx.Native());
  38
  39   return GeoPoint(at, origin.latitude + ey);
  40 }
  41
  42 gcc_const
  43 static GeoPoint
  44 clip_latitude(const GeoPoint origin, const GeoPoint pt, Angle at)
  45 {
  46   Angle dx = pt.longitude - origin.longitude;
  47   Angle dy = pt.latitude - origin.latitude;
  48
  49   Angle ey = at - origin.latitude;
  50   Angle ex = ey * (dx.Native() / dy.Native());
  51
  52   return GeoPoint(origin.longitude + ex, at);
  53 }
  54
  55 bool
  56 GeoClip::ClipPoint(const GeoPoint &origin, GeoPoint &pt) const
  57 {
  58   const Angle zero = Angle::Zero();
  59
  60   if (pt.longitude < zero) {
  61     if (origin.longitude <= zero)
  62       return false;
  63
  64     pt = clip_longitude(origin, pt, zero);
  65   } else if (pt.longitude > width) {
  66     if (origin.longitude >= width)
  67       return false;
  68
  69     pt = clip_longitude(origin, pt, width);
  70   }
  71
  72   if (pt.latitude < GetSouth()) {
  73     if (origin.latitude <= GetSouth())
  74       return false;
  75
  76     pt = clip_latitude(origin, pt, GetSouth());
  77   } else if (pt.latitude > GetNorth()) {
  78     if (origin.latitude >= GetNorth())
  79       return false;
  80
  81     pt = clip_latitude(origin, pt, GetNorth());
  82   }
  83
  84   return true;
  85 }
  86
  87 bool
  88 GeoClip::ClipLine(GeoPoint &a, GeoPoint &b) const
  89 {
  90   GeoPoint a2 = ImportPoint(a);
  91   GeoPoint b2 = ImportPoint(b);
  92
  93   if (!ClipPoint(a2, b2) || !ClipPoint(b2, a2))
  94     return false;
  95
  96   a = ExportPoint(a2);
  97   b = ExportPoint(b2);
  98   return true;
  99 }
 100
 101 static unsigned
 102 ClipVertexLongitude(const Angle west, const Angle east,
 103                     const GeoPoint &prev, GeoPoint &pt, GeoPoint &insert,
 104                     const GeoPoint &next)
 105 {
 106   unsigned num_insert = 0;
 107
 108   if (pt.longitude < west) {
 109     if (prev.longitude <= west) {
 110       if (next.longitude <= west)
 111         /* all three outside, middle one can be deleted */
 112         return 0;
 113
 114       pt = clip_longitude(next, pt, west);
 115     } else {
 116       if (next.longitude > west) {
 117         /* both neighbours are inside, clip both lines and insert a
 118            new vertex */
 119         insert = clip_longitude(next, pt, west);
 120         ++num_insert;
 121       }
 122
 123       pt = clip_longitude(prev, pt, west);
 124     }
 125   } else if (pt.longitude > east) {
 126     if (prev.longitude >= east) {
 127       if (next.longitude >= east)
 128         /* all three outside, middle one can be deleted */
 129         return 0;
 130
 131       pt = clip_longitude(next, pt, east);
 132     } else {
 133       if (next.longitude < east) {
 134         /* both neighbours are inside, clip both lines and insert a
 135            new vertex */
 136         insert = clip_longitude(next, pt, east);
 137         ++num_insert;
 138       }
 139
 140       pt = clip_longitude(prev, pt, east);
 141     }
 142   }
 143
 144   return 1 + num_insert;
 145 }
 146
 147 static unsigned
 148 ClipVertex_latitude(const Angle south, const Angle north,
 149                     const GeoPoint &prev, GeoPoint &pt, GeoPoint &insert,
 150                     const GeoPoint &next)
 151 {
 152   unsigned num_insert = 0;
 153
 154   if (pt.latitude < south) {
 155     if (prev.latitude <= south) {
 156       if (next.latitude <= south)
 157         /* all three outside, middle one can be deleted */
 158         return 0;
 159
 160       pt = clip_latitude(next, pt, south);
 161     } else {
 162       if (next.latitude > south) {
 163         /* both neighbours are inside, clip both lines and insert a
 164            new vertex */
 165         insert = clip_latitude(next, pt, south);
 166         ++num_insert;
 167       }
 168
 169       pt = clip_latitude(prev, pt, south);
 170     }
 171   } else if (pt.latitude > north) {
 172     if (prev.latitude >= north) {
 173       if (next.latitude >= north)
 174         /* all three outside, middle one can be deleted */
 175         return 0;
 176
 177       pt = clip_latitude(next, pt, north);
 178     } else {
 179       if (next.latitude < north) {
 180         /* both neighbours are inside, clip both lines and insert a
 181            new vertex */
 182         insert = clip_latitude(next, pt, north);
 183         ++num_insert;
 184       }
 185
 186       pt = clip_latitude(prev, pt, north);
 187     }
 188   }
 189
 190   return 1 + num_insert;
 191 }
 192
 193 static unsigned
 194 ClipPolygonLongitude(const Angle west, const Angle east, GeoPoint *dest,
 195                      const GeoPoint *src, unsigned src_length)
 196 {
 197   /* this array always holds the current vertex and its two neighbors;
 198      it is filled in advance with the last two points, because that
 199      avoids range checking inside the loop */
 200   GeoPoint three[3];
 201   three[0] = src[src_length - 2];
 202   three[1] = src[src_length - 1];
 203
 204   unsigned dest_length = 0;
 205   for (unsigned i = 0; i < src_length; ++i) {
 206     if (i < src_length - 1)
 207       three[2] = src[i];
 208     else {
 209       /* the last vertex may have been removed in the first iteration,
 210          so use the first element of the "dest" buffer instead */
 211
 212       if (dest_length == 0)
 213         return 0;
 214
 215       three[2] = dest[0];
 216     }
 217
 218     GeoPoint insert;
 219     unsigned n = ClipVertexLongitude(west, east,
 220                                      three[0], three[1], insert, three[2]);
 221     assert(n <= 2);
 222
 223     if (n == 0) {
 224       /* thee points outside, the middle one can be deleted */
 225       three[1] = three[2];
 226     } else if (n == 1) {
 227       /* no change in vertex count, but the current vertex may have
 228          been edited */
 229       dest[dest_length++] = three[1];
 230       three[0] = three[1];
 231       three[1] = three[2];
 232     } else if (n == 2) {
 233       /* one vertex has been inserted */
 234       dest[dest_length++] = three[1];
 235       three[0] = three[1];
 236       three[1] = insert;
 237
 238       /* backtrack, inspect inserted vertex in the next iteration */
 239       --i;
 240     }
 241   }
 242
 243   return dest_length;
 244 }
 245
 246 static unsigned
 247 ClipPolygonLatitude(const Angle south, const Angle north, GeoPoint *dest,
 248                     const GeoPoint *src, unsigned src_length)
 249 {
 250   /* this array always holds the current vertex and its two neighbors;
 251      it is filled in advance with the last two points, because that
 252      avoids range checking inside the loop */
 253   GeoPoint three[3];
 254   three[0] = src[src_length - 2];
 255   three[1] = src[src_length - 1];
 256
 257   unsigned dest_length = 0;
 258   for (unsigned i = 0; i < src_length; ++i) {
 259     if (i < src_length - 1)
 260       three[2] = src[i];
 261     else {
 262       /* the last vertex may have been removed in the first iteration,
 263          so use the first element of the "dest" buffer instead */
 264
 265       if (dest_length == 0)
 266         return 0;
 267
 268       three[2] = dest[0];
 269     }
 270
 271     GeoPoint insert;
 272     unsigned n = ClipVertex_latitude(south, north,
 273                                      three[0], three[1], insert, three[2]);
 274     assert(n <= 2);
 275
 276     if (n == 0) {
 277       /* thee points outside, the middle one can be deleted */
 278       three[1] = three[2];
 279     } else if (n == 1) {
 280       /* no change in vertex count, but the current vertex may have
 281          been edited */
 282       dest[dest_length++] = three[1];
 283       three[0] = three[1];
 284       three[1] = three[2];
 285     } else if (n == 2) {
 286       /* one vertex has been inserted */
 287       dest[dest_length++] = three[1];
 288       three[0] = three[1];
 289       three[1] = insert;
 290
 291       /* backtrack, inspect inserted vertex in the next iteration */
 292       --i;
 293     }
 294   }
 295
 296   return dest_length;
 297 }
 298
 299 unsigned
 300 GeoClip::ClipPolygon(GeoPoint *dest,
 301                      const GeoPoint *src, unsigned src_length) const
 302 {
 303   if (src_length < 3)
 304     return 0;
 305
 306   GeoPoint *imported = dest + src_length * 2;
 307   for (unsigned i = 0; i < src_length; ++i)
 308     imported[i] = ImportPoint(src[i]);
 309
 310   GeoPoint *first_stage = dest + src_length;
 311   unsigned n = ClipPolygonLongitude(Angle::Zero(), width,
 312                                     first_stage, imported, src_length);
 313   if (n < 3)
 314     return 0;
 315
 316   n = ClipPolygonLatitude(GetSouth(), GetNorth(), dest, first_stage, n);
 317   if (n < 3)
 318     return 0;
 319
 320   for (unsigned i = 0; i < n; ++i)
 321     dest[i] = ExportPoint(dest[i]);
 322   return n;
 323 }