WaterIndexProcessor.h

Go to the documentation of this file.

#ifndef OSMSCOUT_IMPORT_WATERINDEXPROCESSOR_H
#define OSMSCOUT_IMPORT_WATERINDEXPROCESSOR_H

/*
  This source is part of the libosmscout library
  Copyright (C) 2017  Tim Teulings

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
*/

#include <fstream>
#include <list>
#include <map>
#include <set>
#include <memory>
#include <vector>

#include <osmscout/GeoCoord.h>
#include <osmscout/Pixel.h>

#include <osmscout/GroundTile.h>

#include <osmscout/util/FileWriter.h>
#include <osmscout/util/Geometry.h>
#include <osmscout/util/Progress.h>
#include <osmscout/util/Projection.h>
#include <osmscout/util/Transformation.h>

#include <osmscout/system/Compiler.h>

#include <osmscout/import/ImportImportExport.h>

namespace osmscout {

  template<typename InputIterator>
  void WriteGpx(InputIterator begin, InputIterator end, const std::string &name)
  {
    std::ofstream gpxFile;

    gpxFile.open(name.c_str());
    gpxFile.imbue(std::locale("C"));
    gpxFile.precision(100);

    gpxFile << "<?xml version=\"1.0\" encoding=\"utf-8\"?>\n";
    gpxFile << "<gpx creator=\"osmscout\" version=\"1.1\" xmlns=\"http://www.topografix.com/GPX/1/1\"";
    gpxFile << " xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\"";
    gpxFile << " xsi:schemaLocation=\"http://www.topografix.com/GPX/1/1 http://www.topografix.com/GPX/1/1/gpx.xsd\">\n";

    gpxFile << " <trk><trkseg>\n";
    for (InputIterator it=begin; it!=end;it++) {
      gpxFile << "<trkpt lat=\"" << it->GetLat() << "\" lon=\"" << it->GetLon() << "\"></trkpt>\n";
    }
    gpxFile << " </trkseg></trk>\n</gpx>";

    gpxFile.close();
  }

  extern void WriteGpx(const std::vector<Point> &path, const std::string& name);

  class OSMSCOUT_IMPORT_API WaterIndexProcessor CLASS_FINAL
  {
  public:
    enum class CoastState : uint8_t
    {
      undefined = 0, 
      land      = 1, 
      water     = 2, 
      unknown   = 3, 
    };

    struct OSMSCOUT_IMPORT_API Coast
    {
      OSMId              id;
      bool               isArea;
      double             sortCriteria;
      Id                 frontNodeId;
      Id                 backNodeId;
      std::vector<Point> coast;
      CoastState         left;
      CoastState         right;
    };

    using CoastRef = std::shared_ptr<Coast>;

    enum State : uint8_t
    {
      unknown = 0, 
      land    = 1, 
      water   = 2, 
      coast   = 3  
    };

    class OSMSCOUT_IMPORT_API StateMap
    {
    private:
      double               cellWidth;  
      double               cellHeight; 
      uint32_t             cellXStart; 
      uint32_t             cellXEnd;   
      uint32_t             cellYStart; 
      uint32_t             cellYEnd;   
      uint32_t             cellXCount; 
      uint32_t             cellYCount; 
      std::vector<uint8_t> area;       

    public:
      void SetBox(const GeoBox& boundingBox,
                  double cellWidth,
                  double cellHeight);

      inline double GetCellWidth() const
      {
        return cellWidth;
      }

      inline double GetCellHeight() const
      {
        return cellHeight;
      }

      inline uint32_t GetXStart() const
      {
        return cellXStart;
      }

      inline uint32_t GetYStart() const
      {
        return cellYStart;
      }

      inline uint32_t GetXEnd() const
      {
        return cellXEnd;
      }

      inline uint32_t GetYEnd() const
      {
        return cellYEnd;
      }

      inline uint32_t GetXCount() const
      {
        return cellXCount;
      }

      inline uint32_t GetYCount() const
      {
        return cellYCount;
      }

      inline bool IsInAbsolute(uint32_t x, uint32_t y) const
      {
        return x>=cellXStart &&
               x<=cellXEnd &&
               y>=cellYStart &&
               y<=cellYEnd;
      }

      State GetState(uint32_t x, uint32_t y) const;
      inline State GetStateAbsolute(uint32_t x, uint32_t y) const
      {
        return GetState(x-cellXStart,
                        y-cellYStart);
      }

      void SetState(uint32_t x, uint32_t y, State state);
      inline void SetStateAbsolute(uint32_t x, uint32_t y, State state)
      {
        SetState(x-cellXStart,
                 y-cellYStart,
                 state);
      }
    };

    struct OSMSCOUT_IMPORT_API Level
    {
      // Transient
      uint32_t             level;            
      FileOffset           indexEntryOffset; 

      // Persistent
      bool                 hasCellData;      
      uint8_t              dataOffsetBytes;  
      State                defaultCellData;  
      FileOffset           indexDataOffset;  

      StateMap             stateMap;         

      void SetBox(const GeoBox& boundingBox,
                  double cellWidth,
                  double cellHeight);
    };

    enum Direction : int8_t
    {
      out   = -1,
      touch = 0,
      in    = 1
    };

    struct OSMSCOUT_IMPORT_API Intersection
    {
      size_t        coastline;          
      size_t        prevWayPointIndex;  
      GeoCoord      prevPoint;          
      GeoCoord      point;              
      double        distanceSquare;     
      Direction     direction;          
      uint8_t       borderIndex;        
    };

    using IntersectionRef = std::shared_ptr<Intersection>;

    struct OSMSCOUT_IMPORT_API CoastlineData
    {
      Id                                         id;                 
      bool                                       isArea;             
      bool                                       isCompletelyInCell; 
      GeoBox                                     boundingBox;        
      Pixel                                      cell;               
      std::vector<GeoCoord>                      points;             
      std::map<Pixel,std::list<IntersectionRef>> cellIntersections;  
      CoastState                                 left;
      CoastState                                 right;
    };

    using CoastlineDataRef = std::shared_ptr<CoastlineData>;

    struct OSMSCOUT_IMPORT_API Data
    {
      std::vector<CoastlineDataRef>     coastlines;            
      std::map<Pixel,std::list<size_t>> cellCoastlines;        
      std::map<Pixel,std::list<size_t>> cellCoveredCoastlines; 
    };

  private:

    struct IntersectionByPathComparator
    {
      inline bool operator()(const IntersectionRef& a, const IntersectionRef& b) const
      {
        if (a->prevWayPointIndex==b->prevWayPointIndex) {
          return a->distanceSquare<b->distanceSquare;
        }

        return a->prevWayPointIndex<b->prevWayPointIndex;
      }
    };

    struct IntersectionCWComparator
    {
      inline bool operator()(const IntersectionRef& a, const IntersectionRef& b) const
      {
        if (a->borderIndex==b->borderIndex) {
          switch (a->borderIndex) {
          case 0:
            if (a->point.GetLon()==b->point.GetLon()){
              return a->prevPoint.GetLon()<b->prevPoint.GetLon();
            }
            return a->point.GetLon()<b->point.GetLon();

          case 1:
            if (a->point.GetLat()==b->point.GetLat()){
              return a->prevPoint.GetLat()>b->prevPoint.GetLat();
            }
            return a->point.GetLat()>b->point.GetLat();

          case 2:
            if (a->point.GetLon()==b->point.GetLon()){
              return a->prevPoint.GetLon()>b->prevPoint.GetLon();
            }
            return a->point.GetLon()>b->point.GetLon();

          default: /* 3 */
            if (a->point.GetLat()==b->point.GetLat()){
              return a->prevPoint.GetLat()<b->prevPoint.GetLat();
            }
            return a->point.GetLat()<b->point.GetLat();
          }
        }
        else {
          return a->borderIndex<b->borderIndex;
        }
      }
    };

    struct CellBoundaries
    {
      double lonMin;
      double lonMax;
      double latMin;
      double latMax;

      using BorderCoords = std::array<GroundTile::Coord, 4>;
      using BorderPoints = std::array<GeoCoord, 4>;
      BorderCoords borderCoords;
      BorderPoints borderPoints;

      inline CellBoundaries(const StateMap &stateMap, const Pixel &cell)
      {
        lonMin=(stateMap.GetXStart()+cell.x)*stateMap.GetCellWidth()-180.0;
        lonMax=(stateMap.GetXStart()+cell.x+1)*stateMap.GetCellWidth()-180.0;
        latMin=(stateMap.GetYStart()+cell.y)*stateMap.GetCellHeight()-90.0;
        latMax=(stateMap.GetYStart()+cell.y+1)*stateMap.GetCellHeight()-90.0;

        borderPoints[0]=GeoCoord(latMax,lonMin); // top left
        borderPoints[1]=GeoCoord(latMax,lonMax); // top right
        borderPoints[2]=GeoCoord(latMin,lonMax); // bottom right
        borderPoints[3]=GeoCoord(latMin,lonMin); // bottom left

        borderCoords[0].Set(0,GroundTile::Coord::CELL_MAX,false);                           // top left
        borderCoords[1].Set(GroundTile::Coord::CELL_MAX,GroundTile::Coord::CELL_MAX,false); // top right
        borderCoords[2].Set(GroundTile::Coord::CELL_MAX,0,false);                           // bottom right
        borderCoords[3].Set(0,0,false);                                                     // bottom left
      }
    };

  private:
    std::string StateToString(State state) const;
    std::string TypeToString(GroundTile::Type type) const;

    GroundTile::Coord Transform(const GeoCoord& point,
                                const StateMap& stateMap,
                                double cellMinLat,
                                double cellMinLon,
                                bool coast);

    void GetCells(const StateMap& stateMap,
                  const GeoCoord& a,
                  const GeoCoord& b,
                  std::set<Pixel>& cellIntersections) const;

    void GetCellIntersections(const StateMap& stateMap,
                              const std::vector<GeoCoord>& points,
                              size_t coastline,
                              std::map<Pixel,std::list<IntersectionRef>>& cellIntersections);

    bool IsCellInBoundingPolygon(const CellBoundaries& cellBoundary,
                                 const std::list<CoastRef>& boundingPolygons);

    bool ContainsCoord(const std::list<GroundTile> &tiles,
                       const GroundTile::Coord &coord,
                       GroundTile::Type type);

    bool ContainsCoord(const std::list<GroundTile> &tiles,
                       const GroundTile::Coord &coord);

    bool ContainsWater(const Pixel &coord,
                       const StateMap &stateMap,
                       const std::map<Pixel,std::list<GroundTile>>& cellGroundTileMap,
                       const GroundTile::Coord &testCoord1,
                       const GroundTile::Coord &testCoord2);

    void WalkBorderCW(GroundTile& groundTile,
                      const StateMap& stateMap,
                      double cellMinLat,
                      double cellMinLon,
                      const IntersectionRef& incoming,
                      const IntersectionRef& outgoing,
                      const CellBoundaries::BorderCoords &borderCoords);

    IntersectionRef GetNextCW(const std::list<IntersectionRef>& intersectionsCW,
                              const IntersectionRef& current) const;

    void WalkPathBack(GroundTile& groundTile,
                      const StateMap& stateMap,
                      double cellMinLat,
                      double cellMinLon,
                      const IntersectionRef& pathStart,
                      const IntersectionRef& pathEnd,
                      const std::vector<GeoCoord>& points,
                      bool isArea);

    void WalkPathForward(GroundTile& groundTile,
                         const StateMap& stateMap,
                         double cellMinLat,
                         double cellMinLon,
                         const IntersectionRef& pathStart,
                         const IntersectionRef& pathEnd,
                         const std::vector<GeoCoord>& points,
                         bool isArea);

    IntersectionRef FindSiblingIntersection(const IntersectionRef &intersection,
                                            const std::list<IntersectionRef> &intersectionsCW,
                                            bool isArea);

    bool WalkFromTripoint(GroundTile &groundTile,
                          const StateMap& stateMap,
                          const CellBoundaries &cellBoundaries,
                          IntersectionRef &pathStart,
                          IntersectionRef &pathEnd,
                          Data &data,
                          const std::list<IntersectionRef> &intersectionsCW,
                          const std::vector<size_t> &containingPaths);

    void WalkPath(GroundTile &groundTile,
                  const StateMap& stateMap,
                  const CellBoundaries &cellBoundaries,
                  const IntersectionRef pathStart,
                  const IntersectionRef pathEnd,
                  CoastlineDataRef coastline);

    bool WalkBoundaryCW(GroundTile &groundTile,
                        const StateMap &stateMap,
                        const IntersectionRef outIntersection,
                        const std::list<IntersectionRef> &intersectionsCW,
                        std::set<IntersectionRef> &visitedIntersections,
                        const CellBoundaries &cellBoundaries,
                        Data& data,
                        const std::vector<size_t> &containingPaths);

    void SynthesizeCoastlines2(Progress& progress,
                               const std::list<CoastRef>& boundingPolygons,
                               const std::list<CoastRef>& coastlines,
                               std::list<CoastRef>& synthesized);

    void HandleCoastlineCell(Progress& progress,
                             const Pixel &cell,
                             const std::list<size_t>& intersectCoastlines,
                             const StateMap& stateMap,
                             std::map<Pixel,std::list<GroundTile> >& cellGroundTileMap,
                             Data& data);

    void TransformCoastlines(Progress& progress,
                             TransPolygon::OptimizeMethod optimizationMethod,
                             double tolerance,
                             double minObjectDimension,
                             const Projection& projection,
                             const std::list<CoastRef>& coastlines,
                             std::vector<CoastlineDataRef> &transformedCoastlines);

    void FilterIntersectCoastlines(Progress& progress,
                                   std::vector<CoastlineDataRef> &transformedCoastlines);

    void FilterEncapsulatedCoastlines(Progress& progress,
                                      std::vector<CoastlineDataRef> &transformedCoastlines);

    void ComputeCoveredTiles(Progress& progress,
                           const StateMap& stateMap,
                           Data& data,
                           std::vector<CoastlineDataRef> &transformedCoastlines);

    static bool CoastlineGeoSizeSorter(const CoastlineDataRef &a, const CoastlineDataRef &b);

public:
    void MergeCoastlines(Progress& progress,
                         std::list<WaterIndexProcessor::CoastRef>& coastlines);

    void GetCells(const StateMap& stateMap,
                  const std::vector<GeoCoord>& points,
                  std::set<Pixel>& cellIntersections) const;

    void GetCells(const StateMap& stateMap,
                  const std::vector<Point>& points,
                  std::set<Pixel>& cellIntersections) const;

    void SynthesizeCoastlines(Progress& progress,
                              std::list<CoastRef>& coastlines,
                              std::list<CoastRef>& boundingPolygons);

    void CalculateCoastlineData(Progress& progress,
                                TransPolygon::OptimizeMethod optimizationMethod,
                                double tolerance,
                                double minObjectDimension,
                                const Projection& projection,
                                const StateMap& stateMap,
                                const std::list<CoastRef>& coastlines,
                                Data& data);

    void MarkCoastlineCells(Progress& progress,
                            StateMap& stateMap,
                            const Data& data);

    void HandleAreaCoastlinesCompletelyInACell(Progress& progress,
                                               const StateMap& stateMap,
                                               Data& data,
                                               std::map<Pixel,std::list<GroundTile> >& cellGroundTileMap);

    void HandleCoastlinesPartiallyInACell(Progress& progress,
                                          const StateMap& stateMap,
                                          std::map<Pixel,std::list<GroundTile> >& cellGroundTileMap,
                                          Data& data);

    void CalculateCoastEnvironment(Progress& progress,
                                   StateMap& stateMap,
                                   const std::map<Pixel,std::list<GroundTile> >& cellGroundTileMap);

    void FillWaterAroundIsland(Progress& progress,
                               StateMap& stateMap,
                               std::map<Pixel,std::list<GroundTile> >& cellGroundTileMap,
                               const std::list<CoastRef>& boundingPolygons);

    void FillWater(Progress& progress,
                   Level& level,
                   size_t tileCount,
                   const std::list<CoastRef>& boundingPolygons);

    void FillLand(Progress& progress,
                  StateMap& stateMap);

    void CalculateHasCellData(Level& level,
                              const std::map<Pixel,std::list<GroundTile> >& cellGroundTileMap) const;

    void DumpIndexHeader(FileWriter& writer,
                         std::vector<Level>& levels);

    void WriteTiles(Progress& progress,
                    const std::map<Pixel,std::list<GroundTile>>& cellGroundTileMap,
                    Level& level,
                    FileWriter& writer);
  };
}

#endif