include/geos/algorithm/CentralEndpointIntersector.h

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.osgeo.org
   5  *
   6  * Copyright (C) 2006 Refractions Research Inc.
   7  *
   8  * This is free software; you can redistribute and/or modify it under
   9  * the terms of the GNU Lesser General Public Licence as published
  10  * by the Free Software Foundation.
  11  * See the COPYING file for more information.
  12  *
  13  **********************************************************************
  14  *
  15  * Last port: algorithm/CentralEndpointIntersector.java rev. 1.1
  16  *
  17  **********************************************************************/
  18
  19 #ifndef GEOS_ALGORITHM_CENTRALENDPOINTINTERSECTOR_H
  20 #define GEOS_ALGORITHM_CENTRALENDPOINTINTERSECTOR_H
  21
  22 #include <geos/export.h>
  23 #include <geos/geom/Coordinate.h>
  24
  25 #include <string>
  26 #include <limits>
  27
  28 #ifdef _MSC_VER
  29 #pragma warning(push)
  30 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class
  31 #endif
  32
  33 // Forward declarations
  34 namespace geos {
  35         namespace geom {
  36                 //class PrecisionModel;
  37         }
  38 }
  39
  40 namespace geos {
  41 namespace algorithm { // geos::algorithm
  42
  43 /** \brief
  44  * Computes an approximate intersection of two line segments
  45  * by taking the most central of the endpoints of the segments.
  46  *
  47  * This is effective in cases where the segments are nearly parallel
  48  * and should intersect at an endpoint.
  49  * It is also a reasonable strategy for cases where the
  50  * endpoint of one segment lies on or almost on the interior of another one.
  51  * Taking the most central endpoint ensures that the computed intersection
  52  * point lies in the envelope of the segments.
  53  * Also, by always returning one of the input points, this should result
  54  * in reducing segment fragmentation.
  55  * Intended to be used as a last resort for
  56  * computing ill-conditioned intersection situations which
  57  * cause other methods to fail.
  58  *
  59  * @author Martin Davis
  60  * @version 1.8
  61  */
  62 class GEOS_DLL CentralEndpointIntersector {
  63
  64 public:
  65
  66         static const geom::Coordinate& getIntersection(const geom::Coordinate& p00,
  67                         const geom::Coordinate& p01, const geom::Coordinate& p10,
  68                         const geom::Coordinate& p11)
  69         {
  70                 CentralEndpointIntersector intor(p00, p01, p10, p11);
  71                 return intor.getIntersection();
  72         }
  73
  74         CentralEndpointIntersector(const geom::Coordinate& p00,
  75                         const geom::Coordinate& p01,
  76                         const geom::Coordinate& p10,
  77                         const geom::Coordinate& p11)
  78                 :
  79                 _pts(4)
  80         {
  81                 _pts[0]=p00;
  82                 _pts[1]=p01;
  83                 _pts[2]=p10;
  84                 _pts[3]=p11;
  85                 compute();
  86         }
  87
  88         const geom::Coordinate& getIntersection() const
  89         {
  90                 return _intPt;
  91         }
  92
  93
  94 private:
  95
  96         // This is likely overkill.. we'll be allocating heap
  97         // memory at every call !
  98         std::vector<geom::Coordinate> _pts;
  99
 100         geom::Coordinate _intPt;
 101
 102         void compute()
 103         {
 104                 geom::Coordinate centroid = average(_pts);
 105                 _intPt = findNearestPoint(centroid, _pts);
 106         }
 107
 108         static geom::Coordinate average(
 109                         const std::vector<geom::Coordinate>& pts)
 110         {
 111                 geom::Coordinate avg(0, 0);
 112                 size_t n = pts.size();
 113                 if ( ! n ) return avg;
 114                 for (std::size_t i=0; i<n; ++i)
 115                 {
 116                         avg.x += pts[i].x;
 117                         avg.y += pts[i].y;
 118                 }
 119                 avg.x /= n;
 120                 avg.y /= n;
 121                 return avg;
 122         }
 123
 124         /**
 125          * Determines a point closest to the given point.
 126          *
 127          * @param p the point to compare against
 128          * @param p1 a potential result point
 129          * @param p2 a potential result point
 130          * @param q1 a potential result point
 131          * @param q2 a potential result point
 132          * @return the point closest to the input point p
 133          */
 134         geom::Coordinate findNearestPoint(const geom::Coordinate& p,
 135                         const std::vector<geom::Coordinate>& pts) const
 136         {
 137                 double minDist = std::numeric_limits<double>::max();
 138                 geom::Coordinate result = geom::Coordinate::getNull();
 139                 for (std::size_t i = 0, n=pts.size(); i < n; ++i) {
 140                         double dist = p.distance(pts[i]);
 141                         if (dist < minDist) {
 142                                 minDist = dist;
 143                                 result = pts[i];
 144                         }
 145                 }
 146                 return result;
 147         }
 148 };
 149
 150 } // namespace geos::algorithm
 151 } // namespace geos
 152
 153 #ifdef _MSC_VER
 154 #pragma warning(pop)
 155 #endif
 156
 157 #endif // GEOS_ALGORITHM_CENTRALENDPOINTINTERSECTOR_H
 158
 159 /**********************************************************************
 160  * $Log$
 161  **********************************************************************/
 162