• Main Page
  • Related Pages
  • Namespaces
  • Classes
  • Files
  • File List

BinaryOp.h

00001 /**********************************************************************
00002  * $Id: BinaryOp.h 2757 2009-12-01 15:39:41Z mloskot $
00003  *
00004  * GEOS - Geometry Engine Open Source
00005  * http://geos.refractions.net
00006  *
00007  * Copyright (C) 2006 Refractions Research Inc.
00008  *
00009  * This is free software; you can redistribute and/or modify it under
00010  * the terms of the GNU Lesser General Public Licence as published
00011  * by the Free Software Foundation. 
00012  * See the COPYING file for more information.
00013  *
00014  **********************************************************************
00015  *
00016  * Last port: ORIGINAL WORK
00017  *
00018  **********************************************************************
00019  *
00020  * This file provides a single templated function, taking two
00021  * const Geometry pointers, applying a binary operator to them
00022  * and returning a result Geometry in an auto_ptr<>.
00023  *
00024  * The binary operator is expected to take two const Geometry pointers
00025  * and return a newly allocated Geometry pointer, possibly throwing
00026  * a TopologyException to signal it couldn't succeed due to robustness
00027  * issues.
00028  *
00029  * This function will catch TopologyExceptions and try again with
00030  * slightly modified versions of the input. The following heuristic
00031  * is used:
00032  *
00033  *      - Try with original input.
00034  *      - Try removing common bits from input coordinate values
00035  *      - Try snaping input geometries to each other
00036  *      - Try snaping input coordinates to a increasing grid (size from 1/25 to 1)
00037  *      - Try simplifiying input with increasing tolerance (from 0.01 to 0.04)
00038  *
00039  * If none of the step succeeds the original exception is thrown.
00040  *
00041  * Note that you can skip Grid snapping, Geometry snapping and Simplify policies
00042  * by a compile-time define when building geos.
00043  * See USE_TP_SIMPLIFY_POLICY, USE_PRECISION_REDUCTION_POLICY and
00044  * USE_SNAPPING_POLICY macros below.
00045  *
00046  *
00047  **********************************************************************/
00048 
00049 #ifndef GEOS_GEOM_BINARYOP_H
00050 #define GEOS_GEOM_BINARYOP_H
00051 
00052 #include <geos/geom/Geometry.h>
00053 #include <geos/geom/PrecisionModel.h>
00054 #include <geos/precision/CommonBitsRemover.h>
00055 #include <geos/precision/SimpleGeometryPrecisionReducer.h>
00056 
00057 #include <geos/operation/overlay/snap/GeometrySnapper.h>
00058 
00059 #include <geos/simplify/TopologyPreservingSimplifier.h>
00060 #include <geos/operation/valid/IsValidOp.h>
00061 #include <geos/util/TopologyException.h>
00062 #include <geos/util.h>
00063 
00064 #include <memory> // for auto_ptr
00065 
00066 //#define GEOS_DEBUG_BINARYOP 1
00067 
00068 
00069 /*
00070  * Always try original input first
00071  */
00072 #ifndef USE_ORIGINAL_INPUT
00073 # define USE_ORIGINAL_INPUT 1
00074 #endif
00075 
00076 /*
00077  * Define this to use PrecisionReduction policy
00078  * in an attempt at by-passing binary operation
00079  * robustness problems (handles TopologyExceptions)
00080  */
00081 #ifndef USE_PRECISION_REDUCTION_POLICY
00082 //# define USE_PRECISION_REDUCTION_POLICY 1
00083 #endif
00084 
00085 /*
00086  * Define this to use TopologyPreserving simplification policy
00087  * in an attempt at by-passing binary operation
00088  * robustness problems (handles TopologyExceptions)
00089  */
00090 #ifndef USE_TP_SIMPLIFY_POLICY 
00091 //# define USE_TP_SIMPLIFY_POLICY 1
00092 #endif
00093 
00094 /*
00095  * Use common bits removal policy.
00096  * If enabled, this would be tried /before/
00097  * Geometry snapping.
00098  */
00099 #ifndef USE_COMMONBITS_POLICY
00100 # define USE_COMMONBITS_POLICY 1
00101 #endif
00102 
00103 /*
00104  * Use snapping policy
00105  */
00106 #ifndef USE_SNAPPING_POLICY
00107 # define USE_SNAPPING_POLICY 1
00108 #endif
00109 
00110 namespace geos {
00111 namespace geom { // geos::geom
00112 
00113 inline bool
00114 check_valid(const Geometry& g, const std::string& label)
00115 {
00116         operation::valid::IsValidOp ivo(&g);
00117         if ( ! ivo.isValid() )
00118         {
00119                 std::cerr << label << ": is invalid!"
00120                         << ivo.getValidationError()->toString() << std::endl;
00121                 return false;
00122         } 
00123         return true;
00124 }
00125 
00131 template <class BinOp>
00132 std::auto_ptr<Geometry>
00133 SnapOp(const Geometry* g0, const Geometry *g1, BinOp _Op)
00134 {
00135         typedef std::auto_ptr<Geometry> GeomPtr;
00136 
00137 #define CBR_BEFORE_SNAPPING 1
00138 
00139         //using geos::precision::GeometrySnapper;
00140         using geos::operation::overlay::snap::GeometrySnapper;
00141 
00142         // Snap tolerance must be computed on the original
00143         // (not commonbits-removed) geoms
00144         double snapTolerance = GeometrySnapper::computeOverlaySnapTolerance(*g0, *g1);
00145 #if GEOS_DEBUG_BINARYOP
00146         std::cerr<<"Computed snap tolerance: "<<snapTolerance<<std::endl;
00147 #endif
00148 
00149         geos::precision::CommonBitsRemover cbr;
00150 
00151 #if CBR_BEFORE_SNAPPING
00152         // Now remove common bits
00153         GeomPtr rG0( cbr.removeCommonBits(g0->clone()) );
00154         GeomPtr rG1( cbr.removeCommonBits(g1->clone()) );
00155 
00156 #if GEOS_DEBUG_BINARYOP
00157         check_valid(*rG0, "CBR: removed-bits geom 0");
00158         check_valid(*rG1, "CBR: removed-bits geom 1");
00159 #endif
00160 
00161         const Geometry& operand0 = *rG0;
00162         const Geometry& operand1 = *rG1;
00163 #else // don't CBR before snapping
00164         const Geometry& operand0 = *g0
00165         const Geometry& operand1 = *g1
00166 #endif
00167 
00168         GeometrySnapper snapper0( operand0 );
00169         GeomPtr snapG0( snapper0.snapTo(operand1, snapTolerance) );
00170 
00171         // NOTE: second geom is snapped on the snapped first one
00172         GeometrySnapper snapper1( operand1 );
00173         GeomPtr snapG1( snapper1.snapTo(*snapG0, snapTolerance) );
00174 
00175 #if GEOS_DEBUG_BINARYOP
00176         check_valid(*snapG0, "SNAP: snapped geom 0");
00177         check_valid(*snapG1, "SNAP: snapped geom 1");
00178 #endif
00179 
00180         // Run the binary op
00181         GeomPtr result( _Op(snapG0.get(), snapG1.get()) );
00182 
00183 #if GEOS_DEBUG_BINARYOP
00184         check_valid(*result, "Op result (before common-bits addition");
00185 #endif
00186 
00187 #if CBR_BEFORE_SNAPPING
00188         // Add common bits back in
00189         cbr.addCommonBits( result.get() );
00190 #endif
00191 
00192 #if GEOS_DEBUG_BINARYOP
00193         check_valid(*result, "Op result (after common-bits addition");
00194 #endif
00195 
00196         return result;
00197 }
00198 
00199 template <class BinOp>
00200 std::auto_ptr<Geometry>
00201 BinaryOp(const Geometry* g0, const Geometry *g1, BinOp _Op)
00202 {
00203         typedef std::auto_ptr<Geometry> GeomPtr;
00204 
00205         GeomPtr ret;
00206         util::TopologyException origException;
00207 
00208 #ifdef USE_ORIGINAL_INPUT
00209         // Try with original input
00210         try
00211         {
00212 #if GEOS_DEBUG_BINARYOP
00213                 std::cerr << "Trying with original input." << std::endl;
00214 #endif
00215                 ret.reset(_Op(g0, g1));
00216                 return ret;
00217         }
00218         catch (const util::TopologyException& ex)
00219         {
00220                 origException=ex;
00221 #if GEOS_DEBUG_BINARYOP
00222                 std::cerr << "Original exception: " << ex.what() << std::endl;
00223 #endif
00224         }
00225 #endif // USE_ORIGINAL_INPUT
00226 
00227 
00228 #ifdef USE_COMMONBITS_POLICY
00229         // Try removing common bits (possibly obsoleted by snapping below)
00230         try
00231         {
00232                 GeomPtr rG0;
00233                 GeomPtr rG1;
00234                 precision::CommonBitsRemover cbr;
00235 
00236 #if GEOS_DEBUG_BINARYOP
00237                 std::cerr << "Trying with Common bits remover." << std::endl;
00238 #endif
00239 
00240                 cbr.add(g0);
00241                 cbr.add(g1);
00242 
00243                 rG0.reset( cbr.removeCommonBits(g0->clone()) );
00244                 rG1.reset( cbr.removeCommonBits(g1->clone()) );
00245 
00246 #if GEOS_DEBUG_BINARYOP
00247                 if ( ! rG0->isValid() )
00248                 {
00249                         std::cerr << " CBR: geom 0 is invalid!" << std::endl;
00250                 }
00251 
00252                 if ( ! rG1->isValid() )
00253                 {
00254                         std::cerr << " CBR: geom 1 is invalid!" << std::endl;
00255                 }
00256 #endif
00257 
00258                 ret.reset( _Op(rG0.get(), rG1.get()) );
00259 
00260                 cbr.addCommonBits( ret.get() );
00261 
00262                 return ret;
00263         }
00264         catch (const util::TopologyException& ex)
00265         {
00266         ::geos::ignore_unused_variable_warning(ex);
00267 #if GEOS_DEBUG_BINARYOP
00268                 std::cerr << "CBR: " << ex.what() << std::endl;
00269 #endif
00270         }
00271 #endif
00272 
00273         // Try with snapping
00274         //
00275         // TODO: possible optimization would be reusing the
00276         //       already common-bit-removed inputs and just
00277         //       apply geometry snapping, whereas the current
00278         //       SnapOp function does both.
00279 // {
00280 #if USE_SNAPPING_POLICY
00281 
00282 #if GEOS_DEBUG_BINARYOP
00283         std::cerr << "Trying with snapping " << std::endl;
00284 #endif
00285 
00286         try {
00287                 ret = SnapOp(g0, g1, _Op);
00288 #if GEOS_DEBUG_BINARYOP
00289         std::cerr << "SnapOp succeeded" << std::endl;
00290 #endif
00291                 return ret;
00292                 
00293         }
00294         catch (const util::TopologyException& ex)
00295         {
00296         ::geos::ignore_unused_variable_warning(ex);
00297 #if GEOS_DEBUG_BINARYOP
00298                 std::cerr << "SNAP: " << ex.what() << std::endl;
00299 #endif
00300         }
00301 
00302 #endif // USE_SNAPPING_POLICY }
00303 
00304 
00305 
00306 // {
00307 #if USE_PRECISION_REDUCTION_POLICY
00308 
00309 
00310         // Try reducing precision
00311         try
00312         {
00313                 int maxPrecision=25;
00314 
00315                 for (int precision=maxPrecision; precision; --precision)
00316                 {
00317                         std::auto_ptr<PrecisionModel> pm(new PrecisionModel(precision));
00318 #if GEOS_DEBUG_BINARYOP
00319                         std::cerr << "Trying with precision " << precision << std::endl;
00320 #endif
00321 
00322                         precision::SimpleGeometryPrecisionReducer reducer( pm.get() );
00323                         GeomPtr rG0( reducer.reduce(g0) );
00324                         GeomPtr rG1( reducer.reduce(g1) );
00325 
00326                         try
00327                         {
00328                                 ret.reset( _Op(rG0.get(), rG1.get()) );
00329                                 return ret;
00330                         }
00331                         catch (const util::TopologyException& ex)
00332                         {
00333                                 if ( precision == 1 ) throw ex;
00334 #if GEOS_DEBUG_BINARYOP
00335                                 std::cerr << "Reduced with precision (" << precision << "): "
00336                                           << ex.what() << std::endl;
00337 #endif
00338                         }
00339 
00340                 }
00341 
00342         }
00343         catch (const util::TopologyException& ex)
00344         {
00345 #if GEOS_DEBUG_BINARYOP
00346                 std::cerr << "Reduced: " << ex.what() << std::endl;
00347 #endif
00348         }
00349 
00350 #endif
00351 // USE_PRECISION_REDUCTION_POLICY }
00352 
00353 // {
00354 #if USE_TP_SIMPLIFY_POLICY 
00355 
00356         // Try simplifying
00357         try
00358         {
00359 
00360                 double maxTolerance = 0.04;
00361                 double minTolerance = 0.01;
00362                 double tolStep = 0.01;
00363 
00364                 for (double tol = minTolerance; tol <= maxTolerance; tol += tolStep)
00365                 {
00366 #if GEOS_DEBUG_BINARYOP
00367                         std::cerr << "Trying simplifying with tolerance " << tol << std::endl;
00368 #endif
00369 
00370                         GeomPtr rG0( simplify::TopologyPreservingSimplifier::simplify(g0, tol) );
00371                         GeomPtr rG1( simplify::TopologyPreservingSimplifier::simplify(g1, tol) );
00372 
00373                         try
00374                         {
00375                                 ret.reset( _Op(rG0.get(), rG1.get()) );
00376                                 return ret;
00377                         }
00378                         catch (const util::TopologyException& ex)
00379                         {
00380                                 if ( tol >= maxTolerance ) throw ex;
00381 #if GEOS_DEBUG_BINARYOP
00382                                 std::cerr << "Simplified with tolerance (" << tol << "): "
00383                                           << ex.what() << std::endl;
00384 #endif
00385                         }
00386 
00387                 }
00388 
00389                 return ret;
00390 
00391         }
00392         catch (const util::TopologyException& ex)
00393         {
00394 #if GEOS_DEBUG_BINARYOP
00395                 std::cerr << "Simplified: " << ex.what() << std::endl;
00396 #endif
00397         }
00398 
00399 #endif
00400 // USE_TP_SIMPLIFY_POLICY }
00401 
00402         throw origException;
00403 }
00404 
00405 
00406 } // namespace geos::geom
00407 } // namespace geos
00408 
00409 #endif // GEOS_GEOM_BINARYOP_H

Generated on Thu Jul 22 2010 for GEOS by  doxygen 1.7.1