Line data    Source code

       1             : /******************************************************************************
       2             :  *
       3             :  * Project:  Marching square algorithm
       4             :  * Purpose:  Core algorithm implementation for contour line generation.
       5             :  * Author:   Oslandia <infos at oslandia dot com>
       6             :  *
       7             :  ******************************************************************************
       8             :  * Copyright (c) 2018, Oslandia <infos at oslandia dot com>
       9             :  *
      10             :  * Permission is hereby granted, free of charge, to any person obtaining a
      11             :  * copy of this software and associated documentation files (the "Software"),
      12             :  * to deal in the Software without restriction, including without limitation
      13             :  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
      14             :  * and/or sell copies of the Software, and to permit persons to whom the
      15             :  * Software is furnished to do so, subject to the following conditions:
      16             :  *
      17             :  * The above copyright notice and this permission notice shall be included
      18             :  * in all copies or substantial portions of the Software.
      19             :  *
      20             :  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
      21             :  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
      22             :  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
      23             :  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
      24             :  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
      25             :  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
      26             :  * DEALINGS IN THE SOFTWARE.
      27             :  ****************************************************************************/
      28             : 
      29             : #ifndef MARCHING_SQUARE_POINT_H
      30             : #define MARCHING_SQUARE_POINT_H
      31             : 
      32             : #include "utility.h"
      33             : #include <ostream>
      34             : #include <algorithm>
      35             : #include <cmath>
      36             : #include <list>
      37             : 
      38             : namespace marching_squares
      39             : {
      40             : 
      41             : // regular point
      42             : struct Point
      43             : {
      44      503610 :     Point() : x(NaN), y(NaN)
      45             :     {
      46      503610 :     }  // just to be able to make an uninitialized list
      47             : 
      48      193646 :     Point(double x_, double y_) : x(x_), y(y_)
      49             :     {
      50      193646 :     }
      51             : 
      52             :     double x;
      53             :     double y;
      54             : };
      55             : 
      56     1250618 : inline bool operator==(const Point &lhs, const Point &rhs)
      57             : {
      58     1250618 :     return (lhs.x == rhs.x) && (lhs.y == rhs.y);
      59             : }
      60             : 
      61           0 : inline std::ostream &operator<<(std::ostream &o, const Point &p)
      62             : {
      63           0 :     o << p.x << " " << p.y;
      64           0 :     return o;
      65             : }
      66             : 
      67             : // Test if a point is to the left or right of an infinite line.
      68             : // Returns true if it is to the left and right otherwise
      69             : // 0 if p2 is on the line and less than if p2 is to the right of the line
      70          58 : inline bool isLeft(const Point &p0, const Point &p1, const Point &p2)
      71             : {
      72          58 :     return ((p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y)) > 0;
      73             : }
      74             : 
      75             : // LineString type
      76             : typedef std::list<Point> LineString;
      77             : 
      78             : inline std::ostream &operator<<(std::ostream &o, const LineString &ls)
      79             : {
      80             :     o << "{";
      81             :     for (const auto &p : ls)
      82             :     {
      83             :         o << p << ", ";
      84             :     }
      85             :     o << "}";
      86             :     return o;
      87             : }
      88             : 
      89             : // Point with a value
      90             : struct ValuedPoint
      91             : {
      92     1652523 :     ValuedPoint(double x_, double y_, double value_)
      93     1652523 :         : x(x_), y(y_), value(value_)
      94             :     {
      95     1652523 :     }
      96             : 
      97             :     const double x;
      98             :     const double y;
      99             :     const double value;
     100             : };
     101             : 
     102             : }  // namespace marching_squares
     103             : 
     104             : #endif