GEOS
3.2.3
|
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