<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>psimpl: D:/Code/Projects/psimpl/trunk/lib/psimpl.h Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript">
$(document).ready(initResizable);
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.7.4 -->
<div id="top">
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">psimpl <span id="projectnumber">7</span></div>
</td>
</tr>
</tbody>
</table>
</div>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
<li><a href="dirs.html"><span>Directories</span></a></li>
</ul>
</div>
<div id="navrow2" class="tabs2">
<ul class="tablist">
<li><a href="files.html"><span>File List</span></a></li>
</ul>
</div>
</div>
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
initNavTree('psimpl_8h.html','');
</script>
<div id="doc-content">
<div class="header">
<div class="headertitle">
<div class="title">psimpl.h</div> </div>
</div>
<div class="contents">
<a href="psimpl_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/* ***** BEGIN LICENSE BLOCK *****</span>
<a name="l00002"></a>00002 <span class="comment"> * Version: MPL 1.1</span>
<a name="l00003"></a>00003 <span class="comment"> *</span>
<a name="l00004"></a>00004 <span class="comment"> * The contents of this file are subject to the Mozilla Public License Version</span>
<a name="l00005"></a>00005 <span class="comment"> * 1.1 (the "License"); you may not use this file except in compliance with</span>
<a name="l00006"></a>00006 <span class="comment"> * the License. You may obtain a copy of the License at</span>
<a name="l00007"></a>00007 <span class="comment"> * http://www.mozilla.org/MPL/</span>
<a name="l00008"></a>00008 <span class="comment"> *</span>
<a name="l00009"></a>00009 <span class="comment"> * Software distributed under the License is distributed on an "AS IS" basis,</span>
<a name="l00010"></a>00010 <span class="comment"> * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License</span>
<a name="l00011"></a>00011 <span class="comment"> * for the specific language governing rights and limitations under the</span>
<a name="l00012"></a>00012 <span class="comment"> * License.</span>
<a name="l00013"></a>00013 <span class="comment"> *</span>
<a name="l00014"></a>00014 <span class="comment"> * The Original Code is</span>
<a name="l00015"></a>00015 <span class="comment"> * 'psimpl - generic n-dimensional polyline simplification'.</span>
<a name="l00016"></a>00016 <span class="comment"> *</span>
<a name="l00017"></a>00017 <span class="comment"> * The Initial Developer of the Original Code is</span>
<a name="l00018"></a>00018 <span class="comment"> * Elmar de Koning.</span>
<a name="l00019"></a>00019 <span class="comment"> * Portions created by the Initial Developer are Copyright (C) 2010-2011</span>
<a name="l00020"></a>00020 <span class="comment"> * the Initial Developer. All Rights Reserved.</span>
<a name="l00021"></a>00021 <span class="comment"> *</span>
<a name="l00022"></a>00022 <span class="comment"> * Contributor(s):</span>
<a name="l00023"></a>00023 <span class="comment"> *</span>
<a name="l00024"></a>00024 <span class="comment"> * ***** END LICENSE BLOCK ***** */</span>
<a name="l00025"></a>00025
<a name="l00026"></a>00026 <span class="comment">/*</span>
<a name="l00027"></a>00027 <span class="comment"> psimpl - generic n-dimensional polyline simplification</span>
<a name="l00028"></a>00028 <span class="comment"> Copyright (C) 2010-2011 Elmar de Koning, edekoning@gmail.com</span>
<a name="l00029"></a>00029 <span class="comment"></span>
<a name="l00030"></a>00030 <span class="comment"> This file is part of psimpl, and is hosted at SourceForge:</span>
<a name="l00031"></a>00031 <span class="comment"> http://sourceforge.net/projects/psimpl/</span>
<a name="l00032"></a>00032 <span class="comment">*/</span>
<a name="l00033"></a>00033
<a name="l00092"></a>00092 <span class="preprocessor">#ifndef PSIMPL_GENERIC</span>
<a name="l00093"></a>00093 <span class="preprocessor"></span><span class="preprocessor">#define PSIMPL_GENERIC</span>
<a name="l00094"></a>00094 <span class="preprocessor"></span>
<a name="l00095"></a>00095
<a name="l00096"></a>00096 <span class="preprocessor">#include <queue></span>
<a name="l00097"></a>00097 <span class="preprocessor">#include <stack></span>
<a name="l00098"></a>00098 <span class="preprocessor">#include <numeric></span>
<a name="l00099"></a>00099 <span class="preprocessor">#include <algorithm></span>
<a name="l00100"></a>00100 <span class="preprocessor">#include <cmath></span>
<a name="l00101"></a>00101
<a name="l00102"></a>00102
<a name="l00106"></a><a class="code" href="namespacepsimpl.html">00106</a> <span class="keyword">namespace </span>psimpl
<a name="l00107"></a>00107 {
<a name="l00111"></a><a class="code" href="namespacepsimpl_1_1util.html">00111</a> <span class="keyword">namespace </span>util
<a name="l00112"></a>00112 {
<a name="l00118"></a>00118 <span class="keyword">template</span> <<span class="keyword">typename</span> T>
<a name="l00119"></a><a class="code" href="classpsimpl_1_1util_1_1scoped__array.html">00119</a> <span class="keyword">class </span><a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">scoped_array</a>
<a name="l00120"></a>00120 {
<a name="l00121"></a>00121 <span class="keyword">public</span>:
<a name="l00122"></a><a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7ca257c64e882a9a5973146de5c8055f">00122</a> <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7ca257c64e882a9a5973146de5c8055f">scoped_array</a> (<span class="keywordtype">unsigned</span> n) {
<a name="l00123"></a>00123 <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a804949986114cac19e44e959ed55202a">array</a> = <span class="keyword">new</span> T [n];
<a name="l00124"></a>00124 }
<a name="l00125"></a>00125
<a name="l00126"></a><a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#abc7ca2793c23699c0ba855856af436e8">00126</a> <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#abc7ca2793c23699c0ba855856af436e8">~scoped_array</a> () {
<a name="l00127"></a>00127 <span class="keyword">delete</span> [] <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a804949986114cac19e44e959ed55202a">array</a>;
<a name="l00128"></a>00128 }
<a name="l00129"></a>00129
<a name="l00130"></a><a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a5fe6ffe5f442f5d8c5c24ef010b276d7">00130</a> T& <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a5fe6ffe5f442f5d8c5c24ef010b276d7">operator [] </a>(<span class="keywordtype">int</span> offset) {
<a name="l00131"></a>00131 <span class="keywordflow">return</span> <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a804949986114cac19e44e959ed55202a">array</a> [offset];
<a name="l00132"></a>00132 }
<a name="l00133"></a>00133
<a name="l00134"></a><a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#aa60ac752fe4ebe0a19b9b3e5fd02051c">00134</a> <span class="keyword">const</span> T& <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a5fe6ffe5f442f5d8c5c24ef010b276d7">operator [] </a>(<span class="keywordtype">int</span> offset)<span class="keyword"> const </span>{
<a name="l00135"></a>00135 <span class="keywordflow">return</span> <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a804949986114cac19e44e959ed55202a">array</a> [offset];
<a name="l00136"></a>00136 }
<a name="l00137"></a>00137
<a name="l00138"></a><a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">00138</a> T* <span class="keyword">get</span> () <span class="keyword">const</span> {
<a name="l00139"></a>00139 <span class="keywordflow">return</span> <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a804949986114cac19e44e959ed55202a">array</a>;
<a name="l00140"></a>00140 }
<a name="l00141"></a>00141
<a name="l00142"></a><a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#ac97beeefa4563f9b9096df6fac32ce39">00142</a> <span class="keywordtype">void</span> <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#ac97beeefa4563f9b9096df6fac32ce39">swap</a> (<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">scoped_array</a>& b) {
<a name="l00143"></a>00143 T* tmp = b.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a804949986114cac19e44e959ed55202a">array</a>;
<a name="l00144"></a>00144 b.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a804949986114cac19e44e959ed55202a">array</a> = <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a804949986114cac19e44e959ed55202a">array</a>;
<a name="l00145"></a>00145 <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a804949986114cac19e44e959ed55202a">array</a> = tmp;
<a name="l00146"></a>00146 }
<a name="l00147"></a>00147
<a name="l00148"></a>00148 <span class="keyword">private</span>:
<a name="l00149"></a>00149 <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7ca257c64e882a9a5973146de5c8055f">scoped_array</a> (<span class="keyword">const</span> <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">scoped_array</a>&);
<a name="l00150"></a>00150 <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">scoped_array</a>& <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a9d2203f20dd342720a9a26fd329e6266">operator= </a>(<span class="keyword">const</span> <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">scoped_array</a>&);
<a name="l00151"></a>00151
<a name="l00152"></a>00152 <span class="keyword">private</span>:
<a name="l00153"></a><a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a804949986114cac19e44e959ed55202a">00153</a> T* <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a804949986114cac19e44e959ed55202a">array</a>;
<a name="l00154"></a>00154 };
<a name="l00155"></a>00155
<a name="l00156"></a><a class="code" href="namespacepsimpl_1_1util.html#ae99d4ca12dc7025d6a31185463d7606d">00156</a> <span class="keyword">template</span> <<span class="keyword">typename</span> T> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="namespacepsimpl_1_1util.html#ae99d4ca12dc7025d6a31185463d7606d">swap</a> (<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">scoped_array <T></a>& a, <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">scoped_array <T></a>& b) {
<a name="l00157"></a>00157 a.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#ac97beeefa4563f9b9096df6fac32ce39">swap</a> (b);
<a name="l00158"></a>00158 }
<a name="l00159"></a>00159 }
<a name="l00160"></a>00160
<a name="l00164"></a><a class="code" href="namespacepsimpl_1_1math.html">00164</a> <span class="keyword">namespace </span>math
<a name="l00165"></a>00165 {
<a name="l00169"></a><a class="code" href="structpsimpl_1_1math_1_1_statistics.html">00169</a> <span class="keyword">struct </span><a class="code" href="structpsimpl_1_1math_1_1_statistics.html" title="POD structure for storing several statistical values.">Statistics</a>
<a name="l00170"></a>00170 {
<a name="l00171"></a><a class="code" href="structpsimpl_1_1math_1_1_statistics.html#acc29e12d945e80f6c36702c3d03c5d45">00171</a> <a class="code" href="structpsimpl_1_1math_1_1_statistics.html#acc29e12d945e80f6c36702c3d03c5d45">Statistics</a> () :
<a name="l00172"></a>00172 <a class="code" href="structpsimpl_1_1math_1_1_statistics.html#ae9f672e092297b56fc28de70802b4fcb">max</a> (0),
<a name="l00173"></a>00173 <a class="code" href="structpsimpl_1_1math_1_1_statistics.html#a7fe8b670f8f9b110303fb797dc900c85">sum</a> (0),
<a name="l00174"></a>00174 <a class="code" href="structpsimpl_1_1math_1_1_statistics.html#a5ec6444e6cb5bbf0b5f2820a5ba45f40">mean</a> (0),
<a name="l00175"></a>00175 <a class="code" href="structpsimpl_1_1math_1_1_statistics.html#af2f6f43cb05903f393c454bf87221f36">std</a> (0)
<a name="l00176"></a>00176 {}
<a name="l00177"></a>00177
<a name="l00178"></a><a class="code" href="structpsimpl_1_1math_1_1_statistics.html#ae9f672e092297b56fc28de70802b4fcb">00178</a> <span class="keywordtype">double</span> <a class="code" href="structpsimpl_1_1math_1_1_statistics.html#ae9f672e092297b56fc28de70802b4fcb">max</a>;
<a name="l00179"></a><a class="code" href="structpsimpl_1_1math_1_1_statistics.html#a7fe8b670f8f9b110303fb797dc900c85">00179</a> <span class="keywordtype">double</span> <a class="code" href="structpsimpl_1_1math_1_1_statistics.html#a7fe8b670f8f9b110303fb797dc900c85">sum</a>;
<a name="l00180"></a><a class="code" href="structpsimpl_1_1math_1_1_statistics.html#a5ec6444e6cb5bbf0b5f2820a5ba45f40">00180</a> <span class="keywordtype">double</span> <a class="code" href="structpsimpl_1_1math_1_1_statistics.html#a5ec6444e6cb5bbf0b5f2820a5ba45f40">mean</a>;
<a name="l00181"></a><a class="code" href="structpsimpl_1_1math_1_1_statistics.html#af2f6f43cb05903f393c454bf87221f36">00181</a> <span class="keywordtype">double</span> <a class="code" href="structpsimpl_1_1math_1_1_statistics.html#af2f6f43cb05903f393c454bf87221f36">std</a>;
<a name="l00182"></a>00182 };
<a name="l00183"></a>00183
<a name="l00191"></a>00191 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> InputIterator>
<a name="l00192"></a><a class="code" href="namespacepsimpl_1_1math.html#a6b293d2459ba597c933d6fdb68e91b2c">00192</a> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="namespacepsimpl_1_1math.html#a6b293d2459ba597c933d6fdb68e91b2c" title="Determines if two points have the exact same coordinates.">equal</a> (
<a name="l00193"></a>00193 InputIterator p1,
<a name="l00194"></a>00194 InputIterator p2)
<a name="l00195"></a>00195 {
<a name="l00196"></a>00196 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> d = 0; d < DIM; ++d) {
<a name="l00197"></a>00197 <span class="keywordflow">if</span> (*p1 != *p2) {
<a name="l00198"></a>00198 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00199"></a>00199 }
<a name="l00200"></a>00200 ++p1;
<a name="l00201"></a>00201 ++p2;
<a name="l00202"></a>00202 }
<a name="l00203"></a>00203 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00204"></a>00204 }
<a name="l00205"></a>00205
<a name="l00214"></a>00214 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> InputIterator, <span class="keyword">class</span> OutputIterator>
<a name="l00215"></a><a class="code" href="namespacepsimpl_1_1math.html#a10bb3d3d87fa1038d43eee6e5f3fcdda">00215</a> <span class="keyword">inline</span> OutputIterator <a class="code" href="namespacepsimpl_1_1math.html#a10bb3d3d87fa1038d43eee6e5f3fcdda" title="Creates a vector from two points.">make_vector</a> (
<a name="l00216"></a>00216 InputIterator p1,
<a name="l00217"></a>00217 InputIterator p2,
<a name="l00218"></a>00218 OutputIterator result)
<a name="l00219"></a>00219 {
<a name="l00220"></a>00220 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> d = 0; d < DIM; ++d) {
<a name="l00221"></a>00221 *result = *p2 - *p1;
<a name="l00222"></a>00222 ++result;
<a name="l00223"></a>00223 ++p1;
<a name="l00224"></a>00224 ++p2;
<a name="l00225"></a>00225 }
<a name="l00226"></a>00226 <span class="keywordflow">return</span> result;
<a name="l00227"></a>00227 }
<a name="l00228"></a>00228
<a name="l00236"></a>00236 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> InputIterator>
<a name="l00237"></a><a class="code" href="namespacepsimpl_1_1math.html#a26bb15089fdfcfc4560b5a318317bbc4">00237</a> <span class="keyword">inline</span> <span class="keyword">typename</span> std::iterator_traits <InputIterator>::value_type <a class="code" href="namespacepsimpl_1_1math.html#a26bb15089fdfcfc4560b5a318317bbc4" title="Computes the dot product of two vectors.">dot</a> (
<a name="l00238"></a>00238 InputIterator v1,
<a name="l00239"></a>00239 InputIterator v2)
<a name="l00240"></a>00240 {
<a name="l00241"></a>00241 <span class="keyword">typename</span> std::iterator_traits <InputIterator>::value_type result = 0;
<a name="l00242"></a>00242 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> d = 0; d < DIM; ++d) {
<a name="l00243"></a>00243 result += (*v1) * (*v2);
<a name="l00244"></a>00244 ++v1;
<a name="l00245"></a>00245 ++v2;
<a name="l00246"></a>00246 }
<a name="l00247"></a>00247 <span class="keywordflow">return</span> result;
<a name="l00248"></a>00248 }
<a name="l00249"></a>00249
<a name="l00259"></a>00259 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> InputIterator, <span class="keyword">class</span> OutputIterator>
<a name="l00260"></a><a class="code" href="namespacepsimpl_1_1math.html#a87a753961c7742b6c48b4f66a0fea697">00260</a> <span class="keyword">inline</span> OutputIterator <a class="code" href="namespacepsimpl_1_1math.html#a87a753961c7742b6c48b4f66a0fea697" title="Peforms linear interpolation between two points.">interpolate</a> (
<a name="l00261"></a>00261 InputIterator p1,
<a name="l00262"></a>00262 InputIterator p2,
<a name="l00263"></a>00263 <span class="keywordtype">float</span> fraction,
<a name="l00264"></a>00264 OutputIterator result)
<a name="l00265"></a>00265 {
<a name="l00266"></a>00266 <span class="keyword">typedef</span> <span class="keyword">typename</span> std::iterator_traits <InputIterator>::value_type value_type;
<a name="l00267"></a>00267
<a name="l00268"></a>00268 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> d = 0; d < DIM; ++d) {
<a name="l00269"></a>00269 *result = *p1 + static_cast <value_type> (fraction * (*p2 - *p1));
<a name="l00270"></a>00270 ++result;
<a name="l00271"></a>00271 ++p1;
<a name="l00272"></a>00272 ++p2;
<a name="l00273"></a>00273 }
<a name="l00274"></a>00274 <span class="keywordflow">return</span> result;
<a name="l00275"></a>00275 }
<a name="l00276"></a>00276
<a name="l00284"></a>00284 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> InputIterator1, <span class="keyword">class</span> InputIterator2>
<a name="l00285"></a><a class="code" href="namespacepsimpl_1_1math.html#ab995b6d68caf4d43172a0de6ee363eb0">00285</a> <span class="keyword">inline</span> <span class="keyword">typename</span> std::iterator_traits <InputIterator1>::value_type <a class="code" href="namespacepsimpl_1_1math.html#ab995b6d68caf4d43172a0de6ee363eb0" title="Computes the squared distance of two points.">point_distance2</a> (
<a name="l00286"></a>00286 InputIterator1 p1,
<a name="l00287"></a>00287 InputIterator2 p2)
<a name="l00288"></a>00288 {
<a name="l00289"></a>00289 <span class="keyword">typename</span> std::iterator_traits <InputIterator1>::value_type result = 0;
<a name="l00290"></a>00290 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> d = 0; d < DIM; ++d) {
<a name="l00291"></a>00291 result += (*p1 - *p2) * (*p1 - *p2);
<a name="l00292"></a>00292 ++p1;
<a name="l00293"></a>00293 ++p2;
<a name="l00294"></a>00294 }
<a name="l00295"></a>00295 <span class="keywordflow">return</span> result;
<a name="l00296"></a>00296 }
<a name="l00297"></a>00297
<a name="l00306"></a>00306 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> InputIterator>
<a name="l00307"></a><a class="code" href="namespacepsimpl_1_1math.html#ace5d8a6b9ca11eeadd9d13e451651996">00307</a> <span class="keyword">inline</span> <span class="keyword">typename</span> std::iterator_traits <InputIterator>::value_type <a class="code" href="namespacepsimpl_1_1math.html#ace5d8a6b9ca11eeadd9d13e451651996" title="Computes the squared distance between an infinite line (l1, l2) and a point p.">line_distance2</a> (
<a name="l00308"></a>00308 InputIterator l1,
<a name="l00309"></a>00309 InputIterator l2,
<a name="l00310"></a>00310 InputIterator p)
<a name="l00311"></a>00311 {
<a name="l00312"></a>00312 <span class="keyword">typedef</span> <span class="keyword">typename</span> std::iterator_traits <InputIterator>::value_type value_type;
<a name="l00313"></a>00313
<a name="l00314"></a>00314 value_type v [DIM]; <span class="comment">// vector l1 --> l2</span>
<a name="l00315"></a>00315 value_type w [DIM]; <span class="comment">// vector l1 --> p</span>
<a name="l00316"></a>00316
<a name="l00317"></a>00317 make_vector <DIM> (l1, l2, v);
<a name="l00318"></a>00318 make_vector <DIM> (l1, p, w);
<a name="l00319"></a>00319
<a name="l00320"></a>00320 value_type cv = dot <DIM> (v, v); <span class="comment">// squared length of v</span>
<a name="l00321"></a>00321 value_type cw = dot <DIM> (w, v); <span class="comment">// project w onto v</span>
<a name="l00322"></a>00322
<a name="l00323"></a>00323 <span class="comment">// avoid problems with divisions when value_type is an integer type</span>
<a name="l00324"></a>00324 <span class="keywordtype">float</span> fraction = cv == 0 ? 0 : static_cast <<span class="keywordtype">float</span>> (cw) / static_cast <float> (cv);
<a name="l00325"></a>00325
<a name="l00326"></a>00326 value_type proj [DIM]; <span class="comment">// p projected onto line (l1, l2)</span>
<a name="l00327"></a>00327 interpolate <DIM> (l1, l2, fraction, proj);
<a name="l00328"></a>00328
<a name="l00329"></a>00329 <span class="keywordflow">return</span> point_distance2 <DIM> (p, proj);
<a name="l00330"></a>00330 }
<a name="l00331"></a>00331
<a name="l00340"></a>00340 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> InputIterator>
<a name="l00341"></a><a class="code" href="namespacepsimpl_1_1math.html#a4f3ff418f290d1125622c2388ab976d0">00341</a> <span class="keyword">inline</span> <span class="keyword">typename</span> std::iterator_traits <InputIterator>::value_type <a class="code" href="namespacepsimpl_1_1math.html#a4f3ff418f290d1125622c2388ab976d0" title="Computes the squared distance between a line segment (s1, s2) and a point p.">segment_distance2</a> (
<a name="l00342"></a>00342 InputIterator s1,
<a name="l00343"></a>00343 InputIterator s2,
<a name="l00344"></a>00344 InputIterator p)
<a name="l00345"></a>00345 {
<a name="l00346"></a>00346 <span class="keyword">typedef</span> <span class="keyword">typename</span> std::iterator_traits <InputIterator>::value_type value_type;
<a name="l00347"></a>00347
<a name="l00348"></a>00348 value_type v [DIM]; <span class="comment">// vector s1 --> s2</span>
<a name="l00349"></a>00349 value_type w [DIM]; <span class="comment">// vector s1 --> p</span>
<a name="l00350"></a>00350
<a name="l00351"></a>00351 make_vector <DIM> (s1, s2, v);
<a name="l00352"></a>00352 make_vector <DIM> (s1, p, w);
<a name="l00353"></a>00353
<a name="l00354"></a>00354 value_type cw = dot <DIM> (w, v); <span class="comment">// project w onto v</span>
<a name="l00355"></a>00355 <span class="keywordflow">if</span> (cw <= 0) {
<a name="l00356"></a>00356 <span class="comment">// projection of w lies to the left of s1</span>
<a name="l00357"></a>00357 <span class="keywordflow">return</span> point_distance2 <DIM> (p, s1);
<a name="l00358"></a>00358 }
<a name="l00359"></a>00359
<a name="l00360"></a>00360 value_type cv = dot <DIM> (v, v); <span class="comment">// squared length of v</span>
<a name="l00361"></a>00361 <span class="keywordflow">if</span> (cv <= cw) {
<a name="l00362"></a>00362 <span class="comment">// projection of w lies to the right of s2</span>
<a name="l00363"></a>00363 <span class="keywordflow">return</span> point_distance2 <DIM> (p, s2);
<a name="l00364"></a>00364 }
<a name="l00365"></a>00365
<a name="l00366"></a>00366 <span class="comment">// avoid problems with divisions when value_type is an integer type</span>
<a name="l00367"></a>00367 <span class="keywordtype">float</span> fraction = cv == 0 ? 0 : static_cast <<span class="keywordtype">float</span>> (cw) / static_cast <float> (cv);
<a name="l00368"></a>00368
<a name="l00369"></a>00369 value_type proj [DIM]; <span class="comment">// p projected onto segement (s1, s2)</span>
<a name="l00370"></a>00370 interpolate <DIM> (s1, s2, fraction, proj);
<a name="l00371"></a>00371
<a name="l00372"></a>00372 <span class="keywordflow">return</span> point_distance2 <DIM> (p, proj);
<a name="l00373"></a>00373 }
<a name="l00374"></a>00374
<a name="l00383"></a>00383 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> InputIterator>
<a name="l00384"></a><a class="code" href="namespacepsimpl_1_1math.html#a4b9426204b9964b859b059cc7fbce61a">00384</a> <span class="keyword">inline</span> <span class="keyword">typename</span> std::iterator_traits <InputIterator>::value_type <a class="code" href="namespacepsimpl_1_1math.html#a4b9426204b9964b859b059cc7fbce61a" title="Computes the squared distance between a ray (r1, r2) and a point p.">ray_distance2</a> (
<a name="l00385"></a>00385 InputIterator r1,
<a name="l00386"></a>00386 InputIterator r2,
<a name="l00387"></a>00387 InputIterator p)
<a name="l00388"></a>00388 {
<a name="l00389"></a>00389 <span class="keyword">typedef</span> <span class="keyword">typename</span> std::iterator_traits <InputIterator>::value_type value_type;
<a name="l00390"></a>00390
<a name="l00391"></a>00391 value_type v [DIM]; <span class="comment">// vector r1 --> r2</span>
<a name="l00392"></a>00392 value_type w [DIM]; <span class="comment">// vector r1 --> p</span>
<a name="l00393"></a>00393
<a name="l00394"></a>00394 make_vector <DIM> (r1, r2, v);
<a name="l00395"></a>00395 make_vector <DIM> (r1, p, w);
<a name="l00396"></a>00396
<a name="l00397"></a>00397 value_type cv = dot <DIM> (v, v); <span class="comment">// squared length of v</span>
<a name="l00398"></a>00398 value_type cw = dot <DIM> (w, v); <span class="comment">// project w onto v</span>
<a name="l00399"></a>00399
<a name="l00400"></a>00400 <span class="keywordflow">if</span> (cw <= 0) {
<a name="l00401"></a>00401 <span class="comment">// projection of w lies to the left of r1 (not on the ray)</span>
<a name="l00402"></a>00402 <span class="keywordflow">return</span> point_distance2 <DIM> (p, r1);
<a name="l00403"></a>00403 }
<a name="l00404"></a>00404
<a name="l00405"></a>00405 <span class="comment">// avoid problems with divisions when value_type is an integer type</span>
<a name="l00406"></a>00406 <span class="keywordtype">float</span> fraction = cv == 0 ? 0 : static_cast <<span class="keywordtype">float</span>> (cw) / static_cast <float> (cv);
<a name="l00407"></a>00407
<a name="l00408"></a>00408 value_type proj [DIM]; <span class="comment">// p projected onto ray (r1, r2)</span>
<a name="l00409"></a>00409 interpolate <DIM> (r1, r2, fraction, proj);
<a name="l00410"></a>00410
<a name="l00411"></a>00411 <span class="keywordflow">return</span> point_distance2 <DIM> (p, proj);
<a name="l00412"></a>00412 }
<a name="l00413"></a>00413
<a name="l00421"></a>00421 <span class="keyword">template</span> <<span class="keyword">class</span> InputIterator>
<a name="l00422"></a><a class="code" href="namespacepsimpl_1_1math.html#ab162cc6f5efcf619c7327b45c793c969">00422</a> <span class="keyword">inline</span> <a class="code" href="structpsimpl_1_1math_1_1_statistics.html" title="POD structure for storing several statistical values.">Statistics</a> <a class="code" href="namespacepsimpl_1_1math.html#ab162cc6f5efcf619c7327b45c793c969" title="Computes various statistics for the range [first, last)">compute_statistics</a> (
<a name="l00423"></a>00423 InputIterator first,
<a name="l00424"></a>00424 InputIterator last)
<a name="l00425"></a>00425 {
<a name="l00426"></a>00426 <span class="keyword">typedef</span> <span class="keyword">typename</span> std::iterator_traits <InputIterator>::value_type value_type;
<a name="l00427"></a>00427 <span class="keyword">typedef</span> <span class="keyword">typename</span> std::iterator_traits <InputIterator>::difference_type diff_type;
<a name="l00428"></a>00428
<a name="l00429"></a>00429 <a class="code" href="structpsimpl_1_1math_1_1_statistics.html" title="POD structure for storing several statistical values.">Statistics</a> stats;
<a name="l00430"></a>00430
<a name="l00431"></a>00431 diff_type count = std::distance (first, last);
<a name="l00432"></a>00432 <span class="keywordflow">if</span> (count == 0) {
<a name="l00433"></a>00433 <span class="keywordflow">return</span> stats;
<a name="l00434"></a>00434 }
<a name="l00435"></a>00435
<a name="l00436"></a>00436 value_type init = 0;
<a name="l00437"></a>00437 stats.<a class="code" href="structpsimpl_1_1math_1_1_statistics.html#ae9f672e092297b56fc28de70802b4fcb">max</a> = static_cast <<span class="keywordtype">double</span>> (*std::max_element (first, last));
<a name="l00438"></a>00438 stats.<a class="code" href="structpsimpl_1_1math_1_1_statistics.html#a7fe8b670f8f9b110303fb797dc900c85">sum</a> = static_cast <<span class="keywordtype">double</span>> (std::accumulate (first, last, init));
<a name="l00439"></a>00439 stats.<a class="code" href="structpsimpl_1_1math_1_1_statistics.html#a5ec6444e6cb5bbf0b5f2820a5ba45f40">mean</a> = stats.<a class="code" href="structpsimpl_1_1math_1_1_statistics.html#a7fe8b670f8f9b110303fb797dc900c85">sum</a> / count;
<a name="l00440"></a>00440 std::transform (first, last, first, std::bind2nd (std::minus <value_type> (), stats.<a class="code" href="structpsimpl_1_1math_1_1_statistics.html#a5ec6444e6cb5bbf0b5f2820a5ba45f40">mean</a>));
<a name="l00441"></a>00441 stats.<a class="code" href="structpsimpl_1_1math_1_1_statistics.html#af2f6f43cb05903f393c454bf87221f36">std</a> = std::sqrt (static_cast <double> (std::inner_product (first, last, first, init)) / count);
<a name="l00442"></a>00442 <span class="keywordflow">return</span> stats;
<a name="l00443"></a>00443 }
<a name="l00444"></a>00444 }
<a name="l00445"></a>00445
<a name="l00453"></a>00453 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> InputIterator, <span class="keyword">class</span> OutputIterator>
<a name="l00454"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html">00454</a> <span class="keyword">class </span><a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification</a>
<a name="l00455"></a>00455 {
<a name="l00456"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">00456</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> std::iterator_traits <InputIterator>::difference_type <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a>;
<a name="l00457"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">00457</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> std::iterator_traits <InputIterator>::value_type <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a>;
<a name="l00458"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">00458</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> std::iterator_traits <const value_type*>::difference_type <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a>;
<a name="l00459"></a>00459
<a name="l00460"></a>00460 <span class="keyword">public</span>:
<a name="l00492"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#ace21c52fe251f03dc87d17e2627f83ed">00492</a> OutputIterator <a class="code" href="classpsimpl_1_1_polyline_simplification.html#ace21c52fe251f03dc87d17e2627f83ed" title="Performs the nth point routine (NP).">NthPoint</a> (
<a name="l00493"></a>00493 InputIterator first,
<a name="l00494"></a>00494 InputIterator last,
<a name="l00495"></a>00495 <span class="keywordtype">unsigned</span> n,
<a name="l00496"></a>00496 OutputIterator result)
<a name="l00497"></a>00497 {
<a name="l00498"></a>00498 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> coordCount = std::distance (first, last);
<a name="l00499"></a>00499 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> pointCount = DIM <span class="comment">// protect against zero DIM</span>
<a name="l00500"></a>00500 ? coordCount / DIM
<a name="l00501"></a>00501 : 0;
<a name="l00502"></a>00502
<a name="l00503"></a>00503 <span class="comment">// validate input and check if simplification required</span>
<a name="l00504"></a>00504 <span class="keywordflow">if</span> (coordCount % DIM || pointCount < 3 || n < 2) {
<a name="l00505"></a>00505 <span class="keywordflow">return</span> std::copy (first, last, result);
<a name="l00506"></a>00506 }
<a name="l00507"></a>00507
<a name="l00508"></a>00508 <span class="keywordtype">unsigned</span> remaining = pointCount - 1; <span class="comment">// the number of points remaining after key</span>
<a name="l00509"></a>00509 InputIterator key = first; <span class="comment">// indicates the current key</span>
<a name="l00510"></a>00510
<a name="l00511"></a>00511 <span class="comment">// the first point is always part of the simplification</span>
<a name="l00512"></a>00512 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (key, result);
<a name="l00513"></a>00513
<a name="l00514"></a>00514 <span class="comment">// copy each nth point</span>
<a name="l00515"></a>00515 <span class="keywordflow">while</span> (<a class="code" href="classpsimpl_1_1_polyline_simplification.html#ab371de18bbb855cbd2912ceea5260519" title="Increments the iterator by n points if possible.">Forward</a> (key, n, remaining)) {
<a name="l00516"></a>00516 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (key, result);
<a name="l00517"></a>00517 }
<a name="l00518"></a>00518
<a name="l00519"></a>00519 <span class="keywordflow">return</span> result;
<a name="l00520"></a>00520 }
<a name="l00521"></a>00521
<a name="l00554"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#aa9f3491a3aa88e3b795705045053a649">00554</a> OutputIterator <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aa9f3491a3aa88e3b795705045053a649" title="Performs the (radial) distance between points routine (RD).">RadialDistance</a> (
<a name="l00555"></a>00555 InputIterator first,
<a name="l00556"></a>00556 InputIterator last,
<a name="l00557"></a>00557 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol,
<a name="l00558"></a>00558 OutputIterator result)
<a name="l00559"></a>00559 {
<a name="l00560"></a>00560 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> coordCount = std::distance (first, last);
<a name="l00561"></a>00561 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> pointCount = DIM <span class="comment">// protect against zero DIM</span>
<a name="l00562"></a>00562 ? coordCount / DIM
<a name="l00563"></a>00563 : 0;
<a name="l00564"></a>00564 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol2 = tol * tol; <span class="comment">// squared distance tolerance</span>
<a name="l00565"></a>00565
<a name="l00566"></a>00566 <span class="comment">// validate input and check if simplification required</span>
<a name="l00567"></a>00567 <span class="keywordflow">if</span> (coordCount % DIM || pointCount < 3 || tol2 == 0) {
<a name="l00568"></a>00568 <span class="keywordflow">return</span> std::copy (first, last, result);
<a name="l00569"></a>00569 }
<a name="l00570"></a>00570
<a name="l00571"></a>00571 InputIterator current = first; <span class="comment">// indicates the current key</span>
<a name="l00572"></a>00572 InputIterator next = first; <span class="comment">// used to find the next key</span>
<a name="l00573"></a>00573
<a name="l00574"></a>00574 <span class="comment">// the first point is always part of the simplification</span>
<a name="l00575"></a>00575 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#acd517bb1803b28ad69aa9012ac2577e5" title="Copies the key to the output destination, and increments the iterator.">CopyKeyAdvance</a> (next, result);
<a name="l00576"></a>00576
<a name="l00577"></a>00577 <span class="comment">// Skip first and last point, because they are always part of the simplification</span>
<a name="l00578"></a>00578 <span class="keywordflow">for</span> (<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> index = 1; index < pointCount - 1; ++index) {
<a name="l00579"></a>00579 <span class="keywordflow">if</span> (math::point_distance2 <DIM> (current, next) < tol2) {
<a name="l00580"></a>00580 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19" title="Increments the iterator by n points.">Advance</a> (next);
<a name="l00581"></a>00581 <span class="keywordflow">continue</span>;
<a name="l00582"></a>00582 }
<a name="l00583"></a>00583 current = next;
<a name="l00584"></a>00584 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#acd517bb1803b28ad69aa9012ac2577e5" title="Copies the key to the output destination, and increments the iterator.">CopyKeyAdvance</a> (next, result);
<a name="l00585"></a>00585 }
<a name="l00586"></a>00586 <span class="comment">// the last point is always part of the simplification</span>
<a name="l00587"></a>00587 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#acd517bb1803b28ad69aa9012ac2577e5" title="Copies the key to the output destination, and increments the iterator.">CopyKeyAdvance</a> (next, result);
<a name="l00588"></a>00588
<a name="l00589"></a>00589 <span class="keywordflow">return</span> result;
<a name="l00590"></a>00590 }
<a name="l00591"></a>00591
<a name="l00608"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#a2b10f2aeaec1cb48eb053b2b9f632c9c">00608</a> OutputIterator <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a2b10f2aeaec1cb48eb053b2b9f632c9c" title="Repeatedly performs the perpendicular distance routine (PD).">PerpendicularDistance</a> (
<a name="l00609"></a>00609 InputIterator first,
<a name="l00610"></a>00610 InputIterator last,
<a name="l00611"></a>00611 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol,
<a name="l00612"></a>00612 <span class="keywordtype">unsigned</span> repeat,
<a name="l00613"></a>00613 OutputIterator result)
<a name="l00614"></a>00614 {
<a name="l00615"></a>00615 <span class="keywordflow">if</span> (repeat == 1) {
<a name="l00616"></a>00616 <span class="comment">// single pass</span>
<a name="l00617"></a>00617 <span class="keywordflow">return</span> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a2b10f2aeaec1cb48eb053b2b9f632c9c" title="Repeatedly performs the perpendicular distance routine (PD).">PerpendicularDistance</a> (first, last, tol, result);
<a name="l00618"></a>00618 }
<a name="l00619"></a>00619 <span class="comment">// only validate repeat; other input is validated by simplify_perpendicular_distance</span>
<a name="l00620"></a>00620 <span class="keywordflow">if</span> (repeat < 1) {
<a name="l00621"></a>00621 <span class="keywordflow">return</span> std::copy (first, last, result);
<a name="l00622"></a>00622 }
<a name="l00623"></a>00623 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> coordCount = std::distance (first, last);
<a name="l00624"></a>00624
<a name="l00625"></a>00625 <span class="comment">// first pass: [first, last) --> temporary array 'tempPoly'</span>
<a name="l00626"></a>00626 <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">util::scoped_array <value_type></a> tempPoly (coordCount);
<a name="l00627"></a>00627 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, InputIterator, value_type*></a> psimpl_to_array;
<a name="l00628"></a>00628 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> tempCoordCount = std::distance (tempPoly.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (),
<a name="l00629"></a>00629 psimpl_to_array.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a2b10f2aeaec1cb48eb053b2b9f632c9c" title="Repeatedly performs the perpendicular distance routine (PD).">PerpendicularDistance</a> (first, last, tol, tempPoly.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> ()));
<a name="l00630"></a>00630
<a name="l00631"></a>00631 <span class="comment">// check if simplification did not improved</span>
<a name="l00632"></a>00632 <span class="keywordflow">if</span> (coordCount == tempCoordCount) {
<a name="l00633"></a>00633 <span class="keywordflow">return</span> std::copy (tempPoly.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (), tempPoly.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> () + coordCount, result);
<a name="l00634"></a>00634 }
<a name="l00635"></a>00635 <a class="code" href="namespacepsimpl_1_1util.html#ae99d4ca12dc7025d6a31185463d7606d">std::swap</a> (coordCount, tempCoordCount);
<a name="l00636"></a>00636 --repeat;
<a name="l00637"></a>00637
<a name="l00638"></a>00638 <span class="comment">// intermediate passes: temporary array 'tempPoly' --> temporary array 'tempResult'</span>
<a name="l00639"></a>00639 <span class="keywordflow">if</span> (1 < repeat) {
<a name="l00640"></a>00640 <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">util::scoped_array <value_type></a> tempResult (coordCount);
<a name="l00641"></a>00641 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, value_type*, value_type*></a> psimpl_arrays;
<a name="l00642"></a>00642
<a name="l00643"></a>00643 <span class="keywordflow">while</span> (--repeat) {
<a name="l00644"></a>00644 tempCoordCount = std::distance (tempResult.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (),
<a name="l00645"></a>00645 psimpl_arrays.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a2b10f2aeaec1cb48eb053b2b9f632c9c" title="Repeatedly performs the perpendicular distance routine (PD).">PerpendicularDistance</a> (
<a name="l00646"></a>00646 tempPoly.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (), tempPoly.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> () + coordCount, tol, tempResult.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> ()));
<a name="l00647"></a>00647
<a name="l00648"></a>00648 <span class="comment">// check if simplification did not improved</span>
<a name="l00649"></a>00649 <span class="keywordflow">if</span> (coordCount == tempCoordCount) {
<a name="l00650"></a>00650 <span class="keywordflow">return</span> std::copy (tempPoly.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (), tempPoly.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> () + coordCount, result);
<a name="l00651"></a>00651 }
<a name="l00652"></a>00652 <a class="code" href="namespacepsimpl_1_1util.html#ae99d4ca12dc7025d6a31185463d7606d">util::swap</a> (tempPoly, tempResult);
<a name="l00653"></a>00653 <a class="code" href="namespacepsimpl_1_1util.html#ae99d4ca12dc7025d6a31185463d7606d">std::swap</a> (coordCount, tempCoordCount);
<a name="l00654"></a>00654 }
<a name="l00655"></a>00655 }
<a name="l00656"></a>00656
<a name="l00657"></a>00657 <span class="comment">// final pass: temporary array 'tempPoly' --> result</span>
<a name="l00658"></a>00658 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, value_type*, OutputIterator></a> psimpl_from_array;
<a name="l00659"></a>00659 <span class="keywordflow">return</span> psimpl_from_array.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a2b10f2aeaec1cb48eb053b2b9f632c9c" title="Repeatedly performs the perpendicular distance routine (PD).">PerpendicularDistance</a> (
<a name="l00660"></a>00660 tempPoly.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (), tempPoly.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> () + coordCount, tol, result);
<a name="l00661"></a>00661 }
<a name="l00662"></a>00662
<a name="l00697"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#a54fec7f2139b6ec1b82ca884fc402f2f">00697</a> OutputIterator <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a2b10f2aeaec1cb48eb053b2b9f632c9c" title="Repeatedly performs the perpendicular distance routine (PD).">PerpendicularDistance</a> (
<a name="l00698"></a>00698 InputIterator first,
<a name="l00699"></a>00699 InputIterator last,
<a name="l00700"></a>00700 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol,
<a name="l00701"></a>00701 OutputIterator result)
<a name="l00702"></a>00702 {
<a name="l00703"></a>00703 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> coordCount = std::distance (first, last);
<a name="l00704"></a>00704 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> pointCount = DIM <span class="comment">// protect against zero DIM</span>
<a name="l00705"></a>00705 ? coordCount / DIM
<a name="l00706"></a>00706 : 0;
<a name="l00707"></a>00707 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol2 = tol * tol; <span class="comment">// squared distance tolerance</span>
<a name="l00708"></a>00708
<a name="l00709"></a>00709 <span class="comment">// validate input and check if simplification required</span>
<a name="l00710"></a>00710 <span class="keywordflow">if</span> (coordCount % DIM || pointCount < 3 || tol2 == 0) {
<a name="l00711"></a>00711 <span class="keywordflow">return</span> std::copy (first, last, result);
<a name="l00712"></a>00712 }
<a name="l00713"></a>00713
<a name="l00714"></a>00714 InputIterator p0 = first;
<a name="l00715"></a>00715 InputIterator p1 = <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a9c2510b3c8466f2080b924629e8ce2e6" title="Increments a copy of the iterator by n points.">AdvanceCopy</a>(p0);
<a name="l00716"></a>00716 InputIterator p2 = <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a9c2510b3c8466f2080b924629e8ce2e6" title="Increments a copy of the iterator by n points.">AdvanceCopy</a>(p1);
<a name="l00717"></a>00717
<a name="l00718"></a>00718 <span class="comment">// the first point is always part of the simplification</span>
<a name="l00719"></a>00719 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (p0, result);
<a name="l00720"></a>00720
<a name="l00721"></a>00721 <span class="keywordflow">while</span> (p2 != last) {
<a name="l00722"></a>00722 <span class="comment">// test p1 against line segment S(p0, p2)</span>
<a name="l00723"></a>00723 <span class="keywordflow">if</span> (math::segment_distance2 <DIM> (p0, p2, p1) < tol2) {
<a name="l00724"></a>00724 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (p2, result);
<a name="l00725"></a>00725 <span class="comment">// move up by two points</span>
<a name="l00726"></a>00726 p0 = p2;
<a name="l00727"></a>00727 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19" title="Increments the iterator by n points.">Advance</a> (p1, 2);
<a name="l00728"></a>00728 <span class="keywordflow">if</span> (p1 == last) {
<a name="l00729"></a>00729 <span class="comment">// protect against advancing p2 beyond last</span>
<a name="l00730"></a>00730 <span class="keywordflow">break</span>;
<a name="l00731"></a>00731 }
<a name="l00732"></a>00732 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19" title="Increments the iterator by n points.">Advance</a> (p2, 2);
<a name="l00733"></a>00733 }
<a name="l00734"></a>00734 <span class="keywordflow">else</span> {
<a name="l00735"></a>00735 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (p1, result);
<a name="l00736"></a>00736 <span class="comment">// move up by one point</span>
<a name="l00737"></a>00737 p0 = p1;
<a name="l00738"></a>00738 p1 = p2;
<a name="l00739"></a>00739 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19" title="Increments the iterator by n points.">Advance</a> (p2);
<a name="l00740"></a>00740 }
<a name="l00741"></a>00741 }
<a name="l00742"></a>00742 <span class="comment">// make sure the last point is part of the simplification</span>
<a name="l00743"></a>00743 <span class="keywordflow">if</span> (p1 != last) {
<a name="l00744"></a>00744 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (p1, result);
<a name="l00745"></a>00745 }
<a name="l00746"></a>00746 <span class="keywordflow">return</span> result;
<a name="l00747"></a>00747 }
<a name="l00748"></a>00748
<a name="l00783"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#ae938c132f029b4e8e828f5e6c7ee4b16">00783</a> OutputIterator <a class="code" href="classpsimpl_1_1_polyline_simplification.html#ae938c132f029b4e8e828f5e6c7ee4b16" title="Performs Reumann-Witkam approximation (RW).">ReumannWitkam</a> (
<a name="l00784"></a>00784 InputIterator first,
<a name="l00785"></a>00785 InputIterator last,
<a name="l00786"></a>00786 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol,
<a name="l00787"></a>00787 OutputIterator result)
<a name="l00788"></a>00788 {
<a name="l00789"></a>00789 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> coordCount = std::distance (first, last);
<a name="l00790"></a>00790 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> pointCount = DIM <span class="comment">// protect against zero DIM</span>
<a name="l00791"></a>00791 ? coordCount / DIM
<a name="l00792"></a>00792 : 0;
<a name="l00793"></a>00793 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol2 = tol * tol; <span class="comment">// squared distance tolerance</span>
<a name="l00794"></a>00794
<a name="l00795"></a>00795 <span class="comment">// validate input and check if simplification required</span>
<a name="l00796"></a>00796 <span class="keywordflow">if</span> (coordCount % DIM || pointCount < 3 || tol2 == 0) {
<a name="l00797"></a>00797 <span class="keywordflow">return</span> std::copy (first, last, result);
<a name="l00798"></a>00798 }
<a name="l00799"></a>00799
<a name="l00800"></a>00800 <span class="comment">// define the line L(p0, p1)</span>
<a name="l00801"></a>00801 InputIterator p0 = first; <span class="comment">// indicates the current key</span>
<a name="l00802"></a>00802 InputIterator p1 = <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a9c2510b3c8466f2080b924629e8ce2e6" title="Increments a copy of the iterator by n points.">AdvanceCopy</a> (first); <span class="comment">// indicates the next point after p0</span>
<a name="l00803"></a>00803
<a name="l00804"></a>00804 <span class="comment">// keep track of two test points</span>
<a name="l00805"></a>00805 InputIterator pi = p1; <span class="comment">// the previous test point</span>
<a name="l00806"></a>00806 InputIterator pj = p1; <span class="comment">// the current test point (pi+1)</span>
<a name="l00807"></a>00807
<a name="l00808"></a>00808 <span class="comment">// the first point is always part of the simplification</span>
<a name="l00809"></a>00809 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (p0, result);
<a name="l00810"></a>00810
<a name="l00811"></a>00811 <span class="comment">// check each point pj against L(p0, p1)</span>
<a name="l00812"></a>00812 <span class="keywordflow">for</span> (<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> j = 2; j < pointCount; ++j) {
<a name="l00813"></a>00813 pi = pj;
<a name="l00814"></a>00814 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19" title="Increments the iterator by n points.">Advance</a> (pj);
<a name="l00815"></a>00815
<a name="l00816"></a>00816 <span class="keywordflow">if</span> (math::line_distance2 <DIM> (p0, p1, pj) < tol2) {
<a name="l00817"></a>00817 <span class="keywordflow">continue</span>;
<a name="l00818"></a>00818 }
<a name="l00819"></a>00819 <span class="comment">// found the next key at pi</span>
<a name="l00820"></a>00820 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (pi, result);
<a name="l00821"></a>00821 <span class="comment">// define new line L(pi, pj)</span>
<a name="l00822"></a>00822 p0 = pi;
<a name="l00823"></a>00823 p1 = pj;
<a name="l00824"></a>00824 }
<a name="l00825"></a>00825 <span class="comment">// the last point is always part of the simplification</span>
<a name="l00826"></a>00826 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (pj, result);
<a name="l00827"></a>00827
<a name="l00828"></a>00828 <span class="keywordflow">return</span> result;
<a name="l00829"></a>00829 }
<a name="l00830"></a>00830
<a name="l00872"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#a0b9bf4a27ef12a4eb103266f50c6eb7e">00872</a> OutputIterator <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a0b9bf4a27ef12a4eb103266f50c6eb7e" title="Performs Opheim approximation (OP).">Opheim</a> (
<a name="l00873"></a>00873 InputIterator first,
<a name="l00874"></a>00874 InputIterator last,
<a name="l00875"></a>00875 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> min_tol,
<a name="l00876"></a>00876 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> max_tol,
<a name="l00877"></a>00877 OutputIterator result)
<a name="l00878"></a>00878 {
<a name="l00879"></a>00879 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> coordCount = std::distance (first, last);
<a name="l00880"></a>00880 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> pointCount = DIM <span class="comment">// protect against zero DIM</span>
<a name="l00881"></a>00881 ? coordCount / DIM
<a name="l00882"></a>00882 : 0;
<a name="l00883"></a>00883 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> min_tol2 = min_tol * min_tol; <span class="comment">// squared minimum distance tolerance</span>
<a name="l00884"></a>00884 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> max_tol2 = max_tol * max_tol; <span class="comment">// squared maximum distance tolerance</span>
<a name="l00885"></a>00885
<a name="l00886"></a>00886 <span class="comment">// validate input and check if simplification required</span>
<a name="l00887"></a>00887 <span class="keywordflow">if</span> (coordCount % DIM || pointCount < 3 || min_tol2 == 0 || max_tol2 == 0) {
<a name="l00888"></a>00888 <span class="keywordflow">return</span> std::copy (first, last, result);
<a name="l00889"></a>00889 }
<a name="l00890"></a>00890
<a name="l00891"></a>00891 <span class="comment">// define the ray R(r0, r1)</span>
<a name="l00892"></a>00892 InputIterator r0 = first; <span class="comment">// indicates the current key and start of the ray</span>
<a name="l00893"></a>00893 InputIterator r1 = first; <span class="comment">// indicates a point on the ray</span>
<a name="l00894"></a>00894 <span class="keywordtype">bool</span> rayDefined = <span class="keyword">false</span>;
<a name="l00895"></a>00895
<a name="l00896"></a>00896 <span class="comment">// keep track of two test points</span>
<a name="l00897"></a>00897 InputIterator pi = r0; <span class="comment">// the previous test point</span>
<a name="l00898"></a>00898 InputIterator pj = <span class="comment">// the current test point (pi+1)</span>
<a name="l00899"></a>00899 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a9c2510b3c8466f2080b924629e8ce2e6" title="Increments a copy of the iterator by n points.">AdvanceCopy</a> (pi);
<a name="l00900"></a>00900
<a name="l00901"></a>00901 <span class="comment">// the first point is always part of the simplification</span>
<a name="l00902"></a>00902 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (r0, result);
<a name="l00903"></a>00903
<a name="l00904"></a>00904 <span class="keywordflow">for</span> (<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> j = 2; j < pointCount; ++j) {
<a name="l00905"></a>00905 pi = pj;
<a name="l00906"></a>00906 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19" title="Increments the iterator by n points.">Advance</a> (pj);
<a name="l00907"></a>00907
<a name="l00908"></a>00908 <span class="keywordflow">if</span> (!rayDefined) {
<a name="l00909"></a>00909 <span class="comment">// discard each point within minimum tolerance</span>
<a name="l00910"></a>00910 <span class="keywordflow">if</span> (math::point_distance2 <DIM> (r0, pj) < min_tol2) {
<a name="l00911"></a>00911 <span class="keywordflow">continue</span>;
<a name="l00912"></a>00912 }
<a name="l00913"></a>00913 <span class="comment">// the last point within minimum tolerance pi defines the ray R(r0, r1)</span>
<a name="l00914"></a>00914 r1 = pi;
<a name="l00915"></a>00915 rayDefined = <span class="keyword">true</span>;
<a name="l00916"></a>00916 }
<a name="l00917"></a>00917
<a name="l00918"></a>00918 <span class="comment">// check each point pj against R(r0, r1)</span>
<a name="l00919"></a>00919 <span class="keywordflow">if</span> (math::point_distance2 <DIM> (r0, pj) < max_tol2 &&
<a name="l00920"></a>00920 math::ray_distance2 <DIM> (r0, r1, pj) < min_tol2)
<a name="l00921"></a>00921 {
<a name="l00922"></a>00922 <span class="keywordflow">continue</span>;
<a name="l00923"></a>00923 }
<a name="l00924"></a>00924 <span class="comment">// found the next key at pi</span>
<a name="l00925"></a>00925 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (pi, result);
<a name="l00926"></a>00926 <span class="comment">// define new ray R(pi, pj)</span>
<a name="l00927"></a>00927 r0 = pi;
<a name="l00928"></a>00928 rayDefined = <span class="keyword">false</span>;
<a name="l00929"></a>00929 }
<a name="l00930"></a>00930 <span class="comment">// the last point is always part of the simplification</span>
<a name="l00931"></a>00931 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (pj, result);
<a name="l00932"></a>00932
<a name="l00933"></a>00933 <span class="keywordflow">return</span> result;
<a name="l00934"></a>00934 }
<a name="l00935"></a>00935
<a name="l00978"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#a34f6cdc9223e0e99c671e07a15086e3e">00978</a> OutputIterator <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a34f6cdc9223e0e99c671e07a15086e3e" title="Performs Lang approximation (LA).">Lang</a> (
<a name="l00979"></a>00979 InputIterator first,
<a name="l00980"></a>00980 InputIterator last,
<a name="l00981"></a>00981 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol,
<a name="l00982"></a>00982 <span class="keywordtype">unsigned</span> look_ahead,
<a name="l00983"></a>00983 OutputIterator result)
<a name="l00984"></a>00984 {
<a name="l00985"></a>00985 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> coordCount = std::distance (first, last);
<a name="l00986"></a>00986 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> pointCount = DIM <span class="comment">// protect against zero DIM</span>
<a name="l00987"></a>00987 ? coordCount / DIM
<a name="l00988"></a>00988 : 0;
<a name="l00989"></a>00989 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol2 = tol * tol; <span class="comment">// squared minimum distance tolerance</span>
<a name="l00990"></a>00990
<a name="l00991"></a>00991 <span class="comment">// validate input and check if simplification required</span>
<a name="l00992"></a>00992 <span class="keywordflow">if</span> (coordCount % DIM || pointCount < 3 || look_ahead < 2 || tol2 == 0) {
<a name="l00993"></a>00993 <span class="keywordflow">return</span> std::copy (first, last, result);
<a name="l00994"></a>00994 }
<a name="l00995"></a>00995
<a name="l00996"></a>00996 InputIterator current = first; <span class="comment">// indicates the current key</span>
<a name="l00997"></a>00997 InputIterator next = first; <span class="comment">// used to find the next key</span>
<a name="l00998"></a>00998
<a name="l00999"></a>00999 <span class="keywordtype">unsigned</span> remaining = pointCount - 1; <span class="comment">// the number of points remaining after current</span>
<a name="l01000"></a>01000 <span class="keywordtype">unsigned</span> moved = <a class="code" href="classpsimpl_1_1_polyline_simplification.html#ab371de18bbb855cbd2912ceea5260519" title="Increments the iterator by n points if possible.">Forward</a> (next, look_ahead, remaining);
<a name="l01001"></a>01001
<a name="l01002"></a>01002 <span class="comment">// the first point is always part of the simplification</span>
<a name="l01003"></a>01003 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (current, result);
<a name="l01004"></a>01004
<a name="l01005"></a>01005 <span class="keywordflow">while</span> (moved) {
<a name="l01006"></a>01006 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> d2 = 0;
<a name="l01007"></a>01007 InputIterator p = <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a9c2510b3c8466f2080b924629e8ce2e6" title="Increments a copy of the iterator by n points.">AdvanceCopy</a> (current);
<a name="l01008"></a>01008
<a name="l01009"></a>01009 <span class="keywordflow">while</span> (p != next) {
<a name="l01010"></a>01010 d2 = std::max (d2, math::segment_distance2 <DIM> (current, next, p));
<a name="l01011"></a>01011 <span class="keywordflow">if</span> (tol2 < d2) {
<a name="l01012"></a>01012 <span class="keywordflow">break</span>;
<a name="l01013"></a>01013 }
<a name="l01014"></a>01014 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19" title="Increments the iterator by n points.">Advance</a> (p);
<a name="l01015"></a>01015 }
<a name="l01016"></a>01016 <span class="keywordflow">if</span> (d2 < tol2) {
<a name="l01017"></a>01017 current = next;
<a name="l01018"></a>01018 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (current, result);
<a name="l01019"></a>01019 moved = <a class="code" href="classpsimpl_1_1_polyline_simplification.html#ab371de18bbb855cbd2912ceea5260519" title="Increments the iterator by n points if possible.">Forward</a> (next, look_ahead, remaining);
<a name="l01020"></a>01020 }
<a name="l01021"></a>01021 <span class="keywordflow">else</span> {
<a name="l01022"></a>01022 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5af6938c7d84c84f20c4981a51228865" title="Decrements the iterator by 1 point.">Backward</a> (next, remaining);
<a name="l01023"></a>01023 }
<a name="l01024"></a>01024 }
<a name="l01025"></a>01025 <span class="keywordflow">return</span> result;
<a name="l01026"></a>01026 }
<a name="l01027"></a>01027
<a name="l01070"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#a75954f25bc0d99e0a756611ffa2b5fda">01070</a> OutputIterator <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a75954f25bc0d99e0a756611ffa2b5fda" title="Performs Douglas-Peucker approximation (DP).">DouglasPeucker</a> (
<a name="l01071"></a>01071 InputIterator first,
<a name="l01072"></a>01072 InputIterator last,
<a name="l01073"></a>01073 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol,
<a name="l01074"></a>01074 OutputIterator result)
<a name="l01075"></a>01075 {
<a name="l01076"></a>01076 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> coordCount = std::distance (first, last);
<a name="l01077"></a>01077 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> pointCount = DIM <span class="comment">// protect against zero DIM</span>
<a name="l01078"></a>01078 ? coordCount / DIM
<a name="l01079"></a>01079 : 0;
<a name="l01080"></a>01080 <span class="comment">// validate input and check if simplification required</span>
<a name="l01081"></a>01081 <span class="keywordflow">if</span> (coordCount % DIM || pointCount < 3 || tol == 0) {
<a name="l01082"></a>01082 <span class="keywordflow">return</span> std::copy (first, last, result);
<a name="l01083"></a>01083 }
<a name="l01084"></a>01084 <span class="comment">// radial distance routine as preprocessing</span>
<a name="l01085"></a>01085 <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">util::scoped_array <value_type></a> reduced (coordCount); <span class="comment">// radial distance results</span>
<a name="l01086"></a>01086 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, InputIterator, value_type*></a> psimpl_to_array;
<a name="l01087"></a>01087 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> reducedCoordCount = std::distance (reduced.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (),
<a name="l01088"></a>01088 psimpl_to_array.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#aa9f3491a3aa88e3b795705045053a649" title="Performs the (radial) distance between points routine (RD).">RadialDistance</a> (first, last, tol, reduced.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> ()));
<a name="l01089"></a>01089 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> reducedPointCount = reducedCoordCount / DIM;
<a name="l01090"></a>01090
<a name="l01091"></a>01091 <span class="comment">// douglas-peucker approximation</span>
<a name="l01092"></a>01092 <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">util::scoped_array <unsigned char></a> keys (pointCount); <span class="comment">// douglas-peucker results</span>
<a name="l01093"></a>01093 <a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html#a19ef5bd5a4ff343e4defbe3765215c28" title="Performs Douglas-Peucker approximation.">DPHelper::Approximate</a> (reduced.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (), reducedCoordCount, tol, keys.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> ());
<a name="l01094"></a>01094
<a name="l01095"></a>01095 <span class="comment">// copy all keys</span>
<a name="l01096"></a>01096 <span class="keyword">const</span> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a>* current = reduced.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> ();
<a name="l01097"></a>01097 <span class="keywordflow">for</span> (<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> p=0; p<reducedPointCount; ++p, current += DIM) {
<a name="l01098"></a>01098 <span class="keywordflow">if</span> (keys [p]) {
<a name="l01099"></a>01099 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> d = 0; d < DIM; ++d) {
<a name="l01100"></a>01100 *result = current [d];
<a name="l01101"></a>01101 ++result;
<a name="l01102"></a>01102 }
<a name="l01103"></a>01103 }
<a name="l01104"></a>01104 }
<a name="l01105"></a>01105 <span class="keywordflow">return</span> result;
<a name="l01106"></a>01106 }
<a name="l01107"></a>01107
<a name="l01147"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#ae309320bd688e6752c8d1e70ff58e4c1">01147</a> OutputIterator <a class="code" href="classpsimpl_1_1_polyline_simplification.html#ae309320bd688e6752c8d1e70ff58e4c1" title="Performs a Douglas-Peucker approximation variant (DPn).">DouglasPeuckerN</a> (
<a name="l01148"></a>01148 InputIterator first,
<a name="l01149"></a>01149 InputIterator last,
<a name="l01150"></a>01150 <span class="keywordtype">unsigned</span> count,
<a name="l01151"></a>01151 OutputIterator result)
<a name="l01152"></a>01152 {
<a name="l01153"></a>01153 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> coordCount = std::distance (first, last);
<a name="l01154"></a>01154 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> pointCount = DIM <span class="comment">// protect against zero DIM</span>
<a name="l01155"></a>01155 ? coordCount / DIM
<a name="l01156"></a>01156 : 0;
<a name="l01157"></a>01157 <span class="comment">// validate input and check if simplification required</span>
<a name="l01158"></a>01158 <span class="keywordflow">if</span> (coordCount % DIM || pointCount <= static_cast <diff_type> (count) || count < 2) {
<a name="l01159"></a>01159 <span class="keywordflow">return</span> std::copy (first, last, result);
<a name="l01160"></a>01160 }
<a name="l01161"></a>01161
<a name="l01162"></a>01162 <span class="comment">// copy coords</span>
<a name="l01163"></a>01163 <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">util::scoped_array <value_type></a> coords (coordCount);
<a name="l01164"></a>01164 <span class="keywordflow">for</span> (<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> c=0; c<coordCount; ++c) {
<a name="l01165"></a>01165 coords [c] = *first;
<a name="l01166"></a>01166 ++first;
<a name="l01167"></a>01167 }
<a name="l01168"></a>01168
<a name="l01169"></a>01169 <span class="comment">// douglas-peucker approximation</span>
<a name="l01170"></a>01170 <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">util::scoped_array <unsigned char></a> keys (pointCount);
<a name="l01171"></a>01171 <a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html#afd49bef5d20db1ef171f9dcfc297e953" title="Performs Douglas-Peucker approximation.">DPHelper::ApproximateN</a> (coords.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (), coordCount, count, keys.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> ());
<a name="l01172"></a>01172
<a name="l01173"></a>01173 <span class="comment">// copy keys</span>
<a name="l01174"></a>01174 <span class="keyword">const</span> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a>* current = coords.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> ();
<a name="l01175"></a>01175 <span class="keywordflow">for</span> (<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> p=0; p<pointCount; ++p, current += DIM) {
<a name="l01176"></a>01176 <span class="keywordflow">if</span> (keys [p]) {
<a name="l01177"></a>01177 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> d = 0; d < DIM; ++d) {
<a name="l01178"></a>01178 *result = current [d];
<a name="l01179"></a>01179 ++result;
<a name="l01180"></a>01180 }
<a name="l01181"></a>01181 }
<a name="l01182"></a>01182 }
<a name="l01183"></a>01183 <span class="keywordflow">return</span> result;
<a name="l01184"></a>01184 }
<a name="l01185"></a>01185
<a name="l01224"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#a6b3ed5157f5bf51ef7be179896cd2903">01224</a> OutputIterator <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a6b3ed5157f5bf51ef7be179896cd2903" title="Computes the squared positional error between a polyline and its simplification.">ComputePositionalErrors2</a> (
<a name="l01225"></a>01225 InputIterator original_first,
<a name="l01226"></a>01226 InputIterator original_last,
<a name="l01227"></a>01227 InputIterator simplified_first,
<a name="l01228"></a>01228 InputIterator simplified_last,
<a name="l01229"></a>01229 OutputIterator result,
<a name="l01230"></a>01230 <span class="keywordtype">bool</span>* valid=0)
<a name="l01231"></a>01231 {
<a name="l01232"></a>01232 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> original_coordCount = std::distance (original_first, original_last);
<a name="l01233"></a>01233 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> original_pointCount = DIM <span class="comment">// protect against zero DIM</span>
<a name="l01234"></a>01234 ? original_coordCount / DIM
<a name="l01235"></a>01235 : 0;
<a name="l01236"></a>01236
<a name="l01237"></a>01237 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> simplified_coordCount = std::distance (simplified_first, simplified_last);
<a name="l01238"></a>01238 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> simplified_pointCount = DIM <span class="comment">// protect against zero DIM</span>
<a name="l01239"></a>01239 ? simplified_coordCount / DIM
<a name="l01240"></a>01240 : 0;
<a name="l01241"></a>01241
<a name="l01242"></a>01242 <span class="comment">// validate input</span>
<a name="l01243"></a>01243 <span class="keywordflow">if</span> (original_coordCount % DIM || original_pointCount < 2 ||
<a name="l01244"></a>01244 simplified_coordCount % DIM || simplified_pointCount < 2 ||
<a name="l01245"></a>01245 original_pointCount < simplified_pointCount ||
<a name="l01246"></a>01246 !math::equal <DIM> (original_first, simplified_first))
<a name="l01247"></a>01247 {
<a name="l01248"></a>01248 <span class="keywordflow">if</span> (valid) {
<a name="l01249"></a>01249 *valid = <span class="keyword">false</span>;
<a name="l01250"></a>01250 }
<a name="l01251"></a>01251 <span class="keywordflow">return</span> result;
<a name="l01252"></a>01252 }
<a name="l01253"></a>01253
<a name="l01254"></a>01254 <span class="comment">// define (simplified) line segment S(simplified_prev, simplified_first)</span>
<a name="l01255"></a>01255 InputIterator simplified_prev = simplified_first;
<a name="l01256"></a>01256 std::advance (simplified_first, DIM);
<a name="l01257"></a>01257
<a name="l01258"></a>01258 <span class="comment">// process each simplified line segment</span>
<a name="l01259"></a>01259 <span class="keywordflow">while</span> (simplified_first != simplified_last) {
<a name="l01260"></a>01260 <span class="comment">// process each original point until it equals the end of the line segment</span>
<a name="l01261"></a>01261 <span class="keywordflow">while</span> (original_first != original_last &&
<a name="l01262"></a>01262 !math::equal <DIM> (original_first, simplified_first))
<a name="l01263"></a>01263 {
<a name="l01264"></a>01264 *result = math::segment_distance2 <DIM> (simplified_prev, simplified_first,
<a name="l01265"></a>01265 original_first);
<a name="l01266"></a>01266 ++result;
<a name="l01267"></a>01267 std::advance (original_first, DIM);
<a name="l01268"></a>01268 }
<a name="l01269"></a>01269 <span class="comment">// update line segment S</span>
<a name="l01270"></a>01270 simplified_prev = simplified_first;
<a name="l01271"></a>01271 std::advance (simplified_first, DIM);
<a name="l01272"></a>01272 }
<a name="l01273"></a>01273 <span class="comment">// check if last original point matched</span>
<a name="l01274"></a>01274 <span class="keywordflow">if</span> (original_first != original_last) {
<a name="l01275"></a>01275 *result = 0;
<a name="l01276"></a>01276 ++result;
<a name="l01277"></a>01277 }
<a name="l01278"></a>01278
<a name="l01279"></a>01279 <span class="keywordflow">if</span> (valid) {
<a name="l01280"></a>01280 *valid = original_first != original_last;
<a name="l01281"></a>01281 }
<a name="l01282"></a>01282 <span class="keywordflow">return</span> result;
<a name="l01283"></a>01283 }
<a name="l01284"></a>01284
<a name="l01317"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#a10af204d445105a8a4cbc81bd0563cb1">01317</a> <a class="code" href="structpsimpl_1_1math_1_1_statistics.html" title="POD structure for storing several statistical values.">math::Statistics</a> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a10af204d445105a8a4cbc81bd0563cb1" title="Computes statistics for the positional errors between a polyline and its simplification.">ComputePositionalErrorStatistics</a> (
<a name="l01318"></a>01318 InputIterator original_first,
<a name="l01319"></a>01319 InputIterator original_last,
<a name="l01320"></a>01320 InputIterator simplified_first,
<a name="l01321"></a>01321 InputIterator simplified_last,
<a name="l01322"></a>01322 <span class="keywordtype">bool</span>* valid=0)
<a name="l01323"></a>01323 {
<a name="l01324"></a>01324 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> pointCount = std::distance (original_first, original_last) / DIM;
<a name="l01325"></a>01325 <a class="code" href="classpsimpl_1_1util_1_1scoped__array.html" title="A smart pointer for holding a dynamically allocated array.">util::scoped_array <double></a> errors (pointCount);
<a name="l01326"></a>01326 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, InputIterator, double*></a> ps;
<a name="l01327"></a>01327
<a name="l01328"></a>01328 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> errorCount =
<a name="l01329"></a>01329 std::distance (
<a name="l01330"></a>01330 errors.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (),
<a name="l01331"></a>01331 ps.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a6b3ed5157f5bf51ef7be179896cd2903" title="Computes the squared positional error between a polyline and its simplification.">ComputePositionalErrors2</a> (original_first, original_last,
<a name="l01332"></a>01332 simplified_first, simplified_last,
<a name="l01333"></a>01333 errors.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (), valid));
<a name="l01334"></a>01334
<a name="l01335"></a>01335 std::transform (errors.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (), errors.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> () + errorCount,
<a name="l01336"></a>01336 errors.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (),
<a name="l01337"></a>01337 std::ptr_fun <double, double> (std::sqrt));
<a name="l01338"></a>01338
<a name="l01339"></a>01339 <span class="keywordflow">return</span> <a class="code" href="namespacepsimpl_1_1math.html#ab162cc6f5efcf619c7327b45c793c969" title="Computes various statistics for the range [first, last)">math::compute_statistics</a> (errors.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> (), errors.<a class="code" href="classpsimpl_1_1util_1_1scoped__array.html#a7a4c3a0d4593dd10ddf6d695f2086e67">get</a> () + errorCount);
<a name="l01340"></a>01340 }
<a name="l01341"></a>01341
<a name="l01342"></a>01342 <span class="keyword">private</span>:
<a name="l01351"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#acd517bb1803b28ad69aa9012ac2577e5">01351</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#acd517bb1803b28ad69aa9012ac2577e5" title="Copies the key to the output destination, and increments the iterator.">CopyKeyAdvance</a> (
<a name="l01352"></a>01352 InputIterator& key,
<a name="l01353"></a>01353 OutputIterator& result)
<a name="l01354"></a>01354 {
<a name="l01355"></a>01355 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> d = 0; d < DIM; ++d) {
<a name="l01356"></a>01356 *result = *key;
<a name="l01357"></a>01357 ++result;
<a name="l01358"></a>01358 ++key;
<a name="l01359"></a>01359 }
<a name="l01360"></a>01360 }
<a name="l01361"></a>01361
<a name="l01370"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a">01370</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a> (
<a name="l01371"></a>01371 InputIterator key,
<a name="l01372"></a>01372 OutputIterator& result)
<a name="l01373"></a>01373 {
<a name="l01374"></a>01374 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#acd517bb1803b28ad69aa9012ac2577e5" title="Copies the key to the output destination, and increments the iterator.">CopyKeyAdvance</a> (key, result);
<a name="l01375"></a>01375 }
<a name="l01376"></a>01376
<a name="l01385"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19">01385</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19" title="Increments the iterator by n points.">Advance</a> (
<a name="l01386"></a>01386 InputIterator& it,
<a name="l01387"></a>01387 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> n = 1)
<a name="l01388"></a>01388 {
<a name="l01389"></a>01389 std::advance (it, n * static_cast <diff_type> (DIM));
<a name="l01390"></a>01390 }
<a name="l01391"></a>01391
<a name="l01401"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#a9c2510b3c8466f2080b924629e8ce2e6">01401</a> <span class="keyword">inline</span> InputIterator <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a9c2510b3c8466f2080b924629e8ce2e6" title="Increments a copy of the iterator by n points.">AdvanceCopy</a> (
<a name="l01402"></a>01402 InputIterator it,
<a name="l01403"></a>01403 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> n = 1)
<a name="l01404"></a>01404 {
<a name="l01405"></a>01405 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19" title="Increments the iterator by n points.">Advance</a> (it, n);
<a name="l01406"></a>01406 <span class="keywordflow">return</span> it;
<a name="l01407"></a>01407 }
<a name="l01408"></a>01408
<a name="l01422"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#ab371de18bbb855cbd2912ceea5260519">01422</a> <span class="keyword">inline</span> <span class="keywordtype">unsigned</span> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#ab371de18bbb855cbd2912ceea5260519" title="Increments the iterator by n points if possible.">Forward</a> (
<a name="l01423"></a>01423 InputIterator& it,
<a name="l01424"></a>01424 <span class="keywordtype">unsigned</span> n,
<a name="l01425"></a>01425 <span class="keywordtype">unsigned</span>& remaining)
<a name="l01426"></a>01426 {
<a name="l01427"></a>01427 n = std::min (n, remaining);
<a name="l01428"></a>01428 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19" title="Increments the iterator by n points.">Advance</a> (it, n);
<a name="l01429"></a>01429 remaining -= n;
<a name="l01430"></a>01430 <span class="keywordflow">return</span> n;
<a name="l01431"></a>01431 }
<a name="l01432"></a>01432
<a name="l01441"></a><a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5af6938c7d84c84f20c4981a51228865">01441</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a5af6938c7d84c84f20c4981a51228865" title="Decrements the iterator by 1 point.">Backward</a> (
<a name="l01442"></a>01442 InputIterator& it,
<a name="l01443"></a>01443 <span class="keywordtype">unsigned</span>& remaining)
<a name="l01444"></a>01444 {
<a name="l01445"></a>01445 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19" title="Increments the iterator by n points.">Advance</a> (it, -1);
<a name="l01446"></a>01446 ++remaining;
<a name="l01447"></a>01447 }
<a name="l01448"></a>01448
<a name="l01449"></a>01449 <span class="keyword">private</span>:
<a name="l01457"></a><a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html">01457</a> <span class="keyword">class </span><a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html" title="Douglas-Peucker approximation helper class.">DPHelper</a>
<a name="l01458"></a>01458 {
<a name="l01460"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html">01460</a> <span class="keyword">struct </span><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html" title="Defines a sub polyline.">SubPoly</a> {
<a name="l01461"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a77018563df501cf3b4ef79d921086314">01461</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a77018563df501cf3b4ef79d921086314">SubPoly</a> (<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6e072a2f6fe795c72870b498ec96e564">first</a>=0, <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6f1943bf7fcd5349e9d312a222804688" title="coord index of the first point">last</a>=0) :
<a name="l01462"></a>01462 <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6e072a2f6fe795c72870b498ec96e564">first</a> (<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6e072a2f6fe795c72870b498ec96e564">first</a>), <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6f1943bf7fcd5349e9d312a222804688" title="coord index of the first point">last</a> (<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6f1943bf7fcd5349e9d312a222804688" title="coord index of the first point">last</a>) {}
<a name="l01463"></a>01463
<a name="l01464"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6e072a2f6fe795c72870b498ec96e564">01464</a> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6e072a2f6fe795c72870b498ec96e564">first</a>;
<a name="l01465"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6f1943bf7fcd5349e9d312a222804688">01465</a> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6f1943bf7fcd5349e9d312a222804688" title="coord index of the first point">last</a>;
<a name="l01466"></a>01466 };
<a name="l01467"></a>01467
<a name="l01469"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html">01469</a> <span class="keyword">struct </span><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html" title="Defines the key of a polyline.">KeyInfo</a> {
<a name="l01470"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#ae9db44331df497b0e20e97f7b1a93491">01470</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#ae9db44331df497b0e20e97f7b1a93491">KeyInfo</a> (<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a>=0, <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#a18fc8b4698754902fa697d9ea92629f4" title="coord index of the key">dist2</a>=0) :
<a name="l01471"></a>01471 <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a> (<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a>), <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#a18fc8b4698754902fa697d9ea92629f4" title="coord index of the key">dist2</a> (<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#a18fc8b4698754902fa697d9ea92629f4" title="coord index of the key">dist2</a>) {}
<a name="l01472"></a>01472
<a name="l01473"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">01473</a> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a>;
<a name="l01474"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#a18fc8b4698754902fa697d9ea92629f4">01474</a> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#a18fc8b4698754902fa697d9ea92629f4" title="coord index of the key">dist2</a>;
<a name="l01475"></a>01475 };
<a name="l01476"></a>01476
<a name="l01478"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html">01478</a> <span class="keyword">struct </span><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html" title="Defines a sub polyline including its key.">SubPolyAlt</a> {
<a name="l01479"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a173dc5811db508a92806559d2e7d1a14">01479</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a173dc5811db508a92806559d2e7d1a14">SubPolyAlt</a> (<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a92345917355c59fbc19704c01a4bfa2d">first</a>=0, <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a4b6e337ce1250efd9599b7df99922fcf" title="coord index of the first point">last</a>=0) :
<a name="l01480"></a>01480 <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a92345917355c59fbc19704c01a4bfa2d">first</a> (<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a92345917355c59fbc19704c01a4bfa2d">first</a>), <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a4b6e337ce1250efd9599b7df99922fcf" title="coord index of the first point">last</a> (<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a4b6e337ce1250efd9599b7df99922fcf" title="coord index of the first point">last</a>) {}
<a name="l01481"></a>01481
<a name="l01482"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a92345917355c59fbc19704c01a4bfa2d">01482</a> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a92345917355c59fbc19704c01a4bfa2d">first</a>;
<a name="l01483"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a4b6e337ce1250efd9599b7df99922fcf">01483</a> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a4b6e337ce1250efd9599b7df99922fcf" title="coord index of the first point">last</a>;
<a name="l01484"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#afa58fb132744d1a2ba4c7ab4ddbc00fb">01484</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html" title="Defines the key of a polyline.">KeyInfo</a> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#afa58fb132744d1a2ba4c7ab4ddbc00fb" title="coord index of the last point">keyInfo</a>;
<a name="l01485"></a>01485
<a name="l01486"></a><a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a737d39204cbf1d26e4d7dccf267f2bc9">01486</a> <span class="keywordtype">bool</span> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a737d39204cbf1d26e4d7dccf267f2bc9" title="key of this sub poly">operator< </a>(<span class="keyword">const</span> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html" title="Defines a sub polyline including its key.">SubPolyAlt</a>& other)<span class="keyword"> const </span>{
<a name="l01487"></a>01487 <span class="keywordflow">return</span> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#afa58fb132744d1a2ba4c7ab4ddbc00fb" title="coord index of the last point">keyInfo</a>.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#a18fc8b4698754902fa697d9ea92629f4" title="coord index of the key">dist2</a> < other.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#afa58fb132744d1a2ba4c7ab4ddbc00fb" title="coord index of the last point">keyInfo</a>.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#a18fc8b4698754902fa697d9ea92629f4" title="coord index of the key">dist2</a>;
<a name="l01488"></a>01488 }
<a name="l01489"></a>01489 };
<a name="l01490"></a>01490
<a name="l01491"></a>01491 <span class="keyword">public</span>:
<a name="l01500"></a><a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html#a19ef5bd5a4ff343e4defbe3765215c28">01500</a> <span class="keyword">static</span> <span class="keywordtype">void</span> <a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html#a19ef5bd5a4ff343e4defbe3765215c28" title="Performs Douglas-Peucker approximation.">Approximate</a> (
<a name="l01501"></a>01501 <span class="keyword">const</span> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a>* coords,
<a name="l01502"></a>01502 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> coordCount,
<a name="l01503"></a>01503 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol,
<a name="l01504"></a>01504 <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>* keys)
<a name="l01505"></a>01505 {
<a name="l01506"></a>01506 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol2 = tol * tol; <span class="comment">// squared distance tolerance</span>
<a name="l01507"></a>01507 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> pointCount = coordCount / DIM;
<a name="l01508"></a>01508 <span class="comment">// zero out keys</span>
<a name="l01509"></a>01509 std::fill_n (keys, pointCount, 0);
<a name="l01510"></a>01510 keys [0] = 1; <span class="comment">// the first point is always a key</span>
<a name="l01511"></a>01511 keys [pointCount - 1] = 1; <span class="comment">// the last point is always a key</span>
<a name="l01512"></a>01512
<a name="l01513"></a>01513 <span class="keyword">typedef</span> std::stack <SubPoly> Stack;
<a name="l01514"></a>01514 Stack stack; <span class="comment">// LIFO job-queue containing sub-polylines</span>
<a name="l01515"></a>01515
<a name="l01516"></a>01516 <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html" title="Defines a sub polyline.">SubPoly</a> subPoly (0, coordCount-DIM);
<a name="l01517"></a>01517 stack.push (subPoly); <span class="comment">// add complete poly</span>
<a name="l01518"></a>01518
<a name="l01519"></a>01519 <span class="keywordflow">while</span> (!stack.empty ()) {
<a name="l01520"></a>01520 subPoly = stack.top (); <span class="comment">// take a sub poly</span>
<a name="l01521"></a>01521 stack.pop (); <span class="comment">// and find its key</span>
<a name="l01522"></a>01522 <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html" title="Defines the key of a polyline.">KeyInfo</a> keyInfo = <a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html#ab1e1bf2f9c562d9ea784466129ce0b19" title="Finds the key for the given sub polyline.">FindKey</a> (coords, subPoly.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6e072a2f6fe795c72870b498ec96e564">first</a>, subPoly.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6f1943bf7fcd5349e9d312a222804688" title="coord index of the first point">last</a>);
<a name="l01523"></a>01523 <span class="keywordflow">if</span> (keyInfo.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a> && tol2 < keyInfo.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#a18fc8b4698754902fa697d9ea92629f4" title="coord index of the key">dist2</a>) {
<a name="l01524"></a>01524 <span class="comment">// store the key if valid</span>
<a name="l01525"></a>01525 keys [keyInfo.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a> / DIM] = 1;
<a name="l01526"></a>01526 <span class="comment">// split the polyline at the key and recurse</span>
<a name="l01527"></a>01527 stack.push (<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html" title="Defines a sub polyline.">SubPoly</a> (keyInfo.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a>, subPoly.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6f1943bf7fcd5349e9d312a222804688" title="coord index of the first point">last</a>));
<a name="l01528"></a>01528 stack.push (<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html" title="Defines a sub polyline.">SubPoly</a> (subPoly.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly.html#a6e072a2f6fe795c72870b498ec96e564">first</a>, keyInfo.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a>));
<a name="l01529"></a>01529 }
<a name="l01530"></a>01530 }
<a name="l01531"></a>01531 }
<a name="l01532"></a>01532
<a name="l01541"></a><a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html#afd49bef5d20db1ef171f9dcfc297e953">01541</a> <span class="keyword">static</span> <span class="keywordtype">void</span> <a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html#afd49bef5d20db1ef171f9dcfc297e953" title="Performs Douglas-Peucker approximation.">ApproximateN</a> (
<a name="l01542"></a>01542 <span class="keyword">const</span> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a>* coords,
<a name="l01543"></a>01543 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> coordCount,
<a name="l01544"></a>01544 <span class="keywordtype">unsigned</span> countTol,
<a name="l01545"></a>01545 <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>* keys)
<a name="l01546"></a>01546 {
<a name="l01547"></a>01547 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> pointCount = coordCount / DIM;
<a name="l01548"></a>01548 <span class="comment">// zero out keys</span>
<a name="l01549"></a>01549 std::fill_n (keys, pointCount, 0);
<a name="l01550"></a>01550 keys [0] = 1; <span class="comment">// the first point is always a key</span>
<a name="l01551"></a>01551 keys [pointCount - 1] = 1; <span class="comment">// the last point is always a key</span>
<a name="l01552"></a>01552 <span class="keywordtype">unsigned</span> keyCount = 2;
<a name="l01553"></a>01553
<a name="l01554"></a>01554 <span class="keywordflow">if</span> (countTol == 2) {
<a name="l01555"></a>01555 <span class="keywordflow">return</span>;
<a name="l01556"></a>01556 }
<a name="l01557"></a>01557
<a name="l01558"></a>01558 <span class="keyword">typedef</span> std::priority_queue <SubPolyAlt> PriorityQueue;
<a name="l01559"></a>01559 PriorityQueue queue; <span class="comment">// sorted (max dist2) job queue containing sub-polylines</span>
<a name="l01560"></a>01560
<a name="l01561"></a>01561 <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html" title="Defines a sub polyline including its key.">SubPolyAlt</a> subPoly (0, coordCount-DIM);
<a name="l01562"></a>01562 subPoly.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#afa58fb132744d1a2ba4c7ab4ddbc00fb" title="coord index of the last point">keyInfo</a> = <a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html#ab1e1bf2f9c562d9ea784466129ce0b19" title="Finds the key for the given sub polyline.">FindKey</a> (coords, subPoly.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a92345917355c59fbc19704c01a4bfa2d">first</a>, subPoly.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a4b6e337ce1250efd9599b7df99922fcf" title="coord index of the first point">last</a>);
<a name="l01563"></a>01563 queue.push (subPoly); <span class="comment">// add complete poly</span>
<a name="l01564"></a>01564
<a name="l01565"></a>01565 <span class="keywordflow">while</span> (!queue.empty ()) {
<a name="l01566"></a>01566 subPoly = queue.top (); <span class="comment">// take a sub poly</span>
<a name="l01567"></a>01567 queue.pop ();
<a name="l01568"></a>01568 <span class="comment">// store the key</span>
<a name="l01569"></a>01569 keys [subPoly.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#afa58fb132744d1a2ba4c7ab4ddbc00fb" title="coord index of the last point">keyInfo</a>.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a> / DIM] = 1;
<a name="l01570"></a>01570 <span class="comment">// check point count tolerance</span>
<a name="l01571"></a>01571 keyCount++;
<a name="l01572"></a>01572 <span class="keywordflow">if</span> (keyCount == countTol) {
<a name="l01573"></a>01573 <span class="keywordflow">break</span>;
<a name="l01574"></a>01574 }
<a name="l01575"></a>01575 <span class="comment">// split the polyline at the key and recurse</span>
<a name="l01576"></a>01576 <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html" title="Defines a sub polyline including its key.">SubPolyAlt</a> left (subPoly.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a92345917355c59fbc19704c01a4bfa2d">first</a>, subPoly.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#afa58fb132744d1a2ba4c7ab4ddbc00fb" title="coord index of the last point">keyInfo</a>.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a>);
<a name="l01577"></a>01577 left.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#afa58fb132744d1a2ba4c7ab4ddbc00fb" title="coord index of the last point">keyInfo</a> = <a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html#ab1e1bf2f9c562d9ea784466129ce0b19" title="Finds the key for the given sub polyline.">FindKey</a> (coords, left.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a92345917355c59fbc19704c01a4bfa2d">first</a>, left.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a4b6e337ce1250efd9599b7df99922fcf" title="coord index of the first point">last</a>);
<a name="l01578"></a>01578 <span class="keywordflow">if</span> (left.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#afa58fb132744d1a2ba4c7ab4ddbc00fb" title="coord index of the last point">keyInfo</a>.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a>) {
<a name="l01579"></a>01579 queue.push (left);
<a name="l01580"></a>01580 }
<a name="l01581"></a>01581 <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html" title="Defines a sub polyline including its key.">SubPolyAlt</a> right (subPoly.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#afa58fb132744d1a2ba4c7ab4ddbc00fb" title="coord index of the last point">keyInfo</a>.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a>, subPoly.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a4b6e337ce1250efd9599b7df99922fcf" title="coord index of the first point">last</a>);
<a name="l01582"></a>01582 right.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#afa58fb132744d1a2ba4c7ab4ddbc00fb" title="coord index of the last point">keyInfo</a> = <a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html#ab1e1bf2f9c562d9ea784466129ce0b19" title="Finds the key for the given sub polyline.">FindKey</a> (coords, right.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a92345917355c59fbc19704c01a4bfa2d">first</a>, right.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#a4b6e337ce1250efd9599b7df99922fcf" title="coord index of the first point">last</a>);
<a name="l01583"></a>01583 <span class="keywordflow">if</span> (right.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_sub_poly_alt.html#afa58fb132744d1a2ba4c7ab4ddbc00fb" title="coord index of the last point">keyInfo</a>.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a>) {
<a name="l01584"></a>01584 queue.push (right);
<a name="l01585"></a>01585 }
<a name="l01586"></a>01586 }
<a name="l01587"></a>01587 }
<a name="l01588"></a>01588
<a name="l01589"></a>01589 <span class="keyword">private</span>:
<a name="l01602"></a><a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html#ab1e1bf2f9c562d9ea784466129ce0b19">01602</a> <span class="keyword">static</span> <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html" title="Defines the key of a polyline.">KeyInfo</a> <a class="code" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html#ab1e1bf2f9c562d9ea784466129ce0b19" title="Finds the key for the given sub polyline.">FindKey</a> (
<a name="l01603"></a>01603 <span class="keyword">const</span> <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a>* coords,
<a name="l01604"></a>01604 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> first,
<a name="l01605"></a>01605 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> last)
<a name="l01606"></a>01606 {
<a name="l01607"></a>01607 <a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html" title="Defines the key of a polyline.">KeyInfo</a> keyInfo;
<a name="l01608"></a>01608
<a name="l01609"></a>01609 <span class="keywordflow">for</span> (<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a> current = first + DIM; current < last; current += DIM) {
<a name="l01610"></a>01610 <a class="code" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> d2 = math::segment_distance2 <DIM> (coords + first, coords + last,
<a name="l01611"></a>01611 coords + current);
<a name="l01612"></a>01612 <span class="keywordflow">if</span> (d2 < keyInfo.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#a18fc8b4698754902fa697d9ea92629f4" title="coord index of the key">dist2</a>) {
<a name="l01613"></a>01613 <span class="keywordflow">continue</span>;
<a name="l01614"></a>01614 }
<a name="l01615"></a>01615 <span class="comment">// update maximum squared distance and the point it belongs to</span>
<a name="l01616"></a>01616 keyInfo.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#aa4ea63f0cb9abd4c7001d3f835a47ae4">index</a> = current;
<a name="l01617"></a>01617 keyInfo.<a class="code" href="structpsimpl_1_1_polyline_simplification_1_1_d_p_helper_1_1_key_info.html#a18fc8b4698754902fa697d9ea92629f4" title="coord index of the key">dist2</a> = d2;
<a name="l01618"></a>01618 }
<a name="l01619"></a>01619 <span class="keywordflow">return</span> keyInfo;
<a name="l01620"></a>01620 }
<a name="l01621"></a>01621 };
<a name="l01622"></a>01622 };
<a name="l01623"></a>01623
<a name="l01636"></a>01636 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> ForwardIterator, <span class="keyword">class</span> OutputIterator>
<a name="l01637"></a><a class="code" href="namespacepsimpl.html#a1a805a9e3eef7ca46bffae71a8b49dc0">01637</a> OutputIterator <a class="code" href="namespacepsimpl.html#a1a805a9e3eef7ca46bffae71a8b49dc0" title="Performs the nth point routine (NP).">simplify_nth_point</a> (
<a name="l01638"></a>01638 ForwardIterator first,
<a name="l01639"></a>01639 ForwardIterator last,
<a name="l01640"></a>01640 <span class="keywordtype">unsigned</span> n,
<a name="l01641"></a>01641 OutputIterator result)
<a name="l01642"></a>01642 {
<a name="l01643"></a>01643 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, ForwardIterator, OutputIterator></a> ps;
<a name="l01644"></a>01644 <span class="keywordflow">return</span> ps.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#ace21c52fe251f03dc87d17e2627f83ed" title="Performs the nth point routine (NP).">NthPoint</a> (first, last, n, result);
<a name="l01645"></a>01645 }
<a name="l01646"></a>01646
<a name="l01659"></a>01659 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> ForwardIterator, <span class="keyword">class</span> OutputIterator>
<a name="l01660"></a><a class="code" href="namespacepsimpl.html#a12f4b63e11188c5293fe3effabbfba31">01660</a> OutputIterator <a class="code" href="namespacepsimpl.html#a12f4b63e11188c5293fe3effabbfba31" title="Performs the (radial) distance between points routine (RD).">simplify_radial_distance</a> (
<a name="l01661"></a>01661 ForwardIterator first,
<a name="l01662"></a>01662 ForwardIterator last,
<a name="l01663"></a>01663 <span class="keyword">typename</span> std::iterator_traits <ForwardIterator>::value_type tol,
<a name="l01664"></a>01664 OutputIterator result)
<a name="l01665"></a>01665 {
<a name="l01666"></a>01666 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, ForwardIterator, OutputIterator></a> ps;
<a name="l01667"></a>01667 <span class="keywordflow">return</span> ps.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#aa9f3491a3aa88e3b795705045053a649" title="Performs the (radial) distance between points routine (RD).">RadialDistance</a> (first, last, tol, result);
<a name="l01668"></a>01668 }
<a name="l01669"></a>01669
<a name="l01683"></a>01683 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> ForwardIterator, <span class="keyword">class</span> OutputIterator>
<a name="l01684"></a><a class="code" href="namespacepsimpl.html#aa8c86b0f1529d529fc2ff84d09b00101">01684</a> OutputIterator <a class="code" href="namespacepsimpl.html#aa8c86b0f1529d529fc2ff84d09b00101" title="Repeatedly performs the perpendicular distance routine (PD).">simplify_perpendicular_distance</a> (
<a name="l01685"></a>01685 ForwardIterator first,
<a name="l01686"></a>01686 ForwardIterator last,
<a name="l01687"></a>01687 <span class="keyword">typename</span> std::iterator_traits <ForwardIterator>::value_type tol,
<a name="l01688"></a>01688 <span class="keywordtype">unsigned</span> repeat,
<a name="l01689"></a>01689 OutputIterator result)
<a name="l01690"></a>01690 {
<a name="l01691"></a>01691 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, ForwardIterator, OutputIterator></a> ps;
<a name="l01692"></a>01692 <span class="keywordflow">return</span> ps.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a2b10f2aeaec1cb48eb053b2b9f632c9c" title="Repeatedly performs the perpendicular distance routine (PD).">PerpendicularDistance</a> (first, last, tol, repeat, result);
<a name="l01693"></a>01693 }
<a name="l01694"></a>01694
<a name="l01707"></a>01707 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> ForwardIterator, <span class="keyword">class</span> OutputIterator>
<a name="l01708"></a><a class="code" href="namespacepsimpl.html#a71a8cbb4f1ebd41a5897c8174bdf8617">01708</a> OutputIterator <a class="code" href="namespacepsimpl.html#aa8c86b0f1529d529fc2ff84d09b00101" title="Repeatedly performs the perpendicular distance routine (PD).">simplify_perpendicular_distance</a> (
<a name="l01709"></a>01709 ForwardIterator first,
<a name="l01710"></a>01710 ForwardIterator last,
<a name="l01711"></a>01711 <span class="keyword">typename</span> std::iterator_traits <ForwardIterator>::value_type tol,
<a name="l01712"></a>01712 OutputIterator result)
<a name="l01713"></a>01713 {
<a name="l01714"></a>01714 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, ForwardIterator, OutputIterator></a> ps;
<a name="l01715"></a>01715 <span class="keywordflow">return</span> ps.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a2b10f2aeaec1cb48eb053b2b9f632c9c" title="Repeatedly performs the perpendicular distance routine (PD).">PerpendicularDistance</a> (first, last, tol, result);
<a name="l01716"></a>01716 }
<a name="l01717"></a>01717
<a name="l01730"></a>01730 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> ForwardIterator, <span class="keyword">class</span> OutputIterator>
<a name="l01731"></a><a class="code" href="namespacepsimpl.html#a0ae1a1e3ada43f9791ac6ac36df5fdf7">01731</a> OutputIterator <a class="code" href="namespacepsimpl.html#a0ae1a1e3ada43f9791ac6ac36df5fdf7" title="Performs Reumann-Witkam polyline simplification (RW).">simplify_reumann_witkam</a> (
<a name="l01732"></a>01732 ForwardIterator first,
<a name="l01733"></a>01733 ForwardIterator last,
<a name="l01734"></a>01734 <span class="keyword">typename</span> std::iterator_traits <ForwardIterator>::value_type tol,
<a name="l01735"></a>01735 OutputIterator result)
<a name="l01736"></a>01736 {
<a name="l01737"></a>01737 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, ForwardIterator, OutputIterator></a> ps;
<a name="l01738"></a>01738 <span class="keywordflow">return</span> ps.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#ae938c132f029b4e8e828f5e6c7ee4b16" title="Performs Reumann-Witkam approximation (RW).">ReumannWitkam</a> (first, last, tol, result);
<a name="l01739"></a>01739 }
<a name="l01740"></a>01740
<a name="l01754"></a>01754 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> ForwardIterator, <span class="keyword">class</span> OutputIterator>
<a name="l01755"></a><a class="code" href="namespacepsimpl.html#a433d47ec86872f64bdc2bc792e6444ca">01755</a> OutputIterator <a class="code" href="namespacepsimpl.html#a433d47ec86872f64bdc2bc792e6444ca" title="Performs Opheim polyline simplification (OP).">simplify_opheim</a> (
<a name="l01756"></a>01756 ForwardIterator first,
<a name="l01757"></a>01757 ForwardIterator last,
<a name="l01758"></a>01758 <span class="keyword">typename</span> std::iterator_traits <ForwardIterator>::value_type min_tol,
<a name="l01759"></a>01759 <span class="keyword">typename</span> std::iterator_traits <ForwardIterator>::value_type max_tol,
<a name="l01760"></a>01760 OutputIterator result)
<a name="l01761"></a>01761 {
<a name="l01762"></a>01762 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, ForwardIterator, OutputIterator></a> ps;
<a name="l01763"></a>01763 <span class="keywordflow">return</span> ps.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a0b9bf4a27ef12a4eb103266f50c6eb7e" title="Performs Opheim approximation (OP).">Opheim</a> (first, last, min_tol, max_tol, result);
<a name="l01764"></a>01764 }
<a name="l01765"></a>01765
<a name="l01779"></a>01779 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> B<span class="keywordtype">id</span>irectionalIterator, <span class="keyword">class</span> OutputIterator>
<a name="l01780"></a><a class="code" href="namespacepsimpl.html#a241debcb1ad56aa1046f4a4996922411">01780</a> OutputIterator <a class="code" href="namespacepsimpl.html#a241debcb1ad56aa1046f4a4996922411" title="Performs Lang polyline simplification (LA).">simplify_lang</a> (
<a name="l01781"></a>01781 BidirectionalIterator first,
<a name="l01782"></a>01782 BidirectionalIterator last,
<a name="l01783"></a>01783 <span class="keyword">typename</span> std::iterator_traits <BidirectionalIterator>::value_type tol,
<a name="l01784"></a>01784 <span class="keywordtype">unsigned</span> look_ahead,
<a name="l01785"></a>01785 OutputIterator result)
<a name="l01786"></a>01786 {
<a name="l01787"></a>01787 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, BidirectionalIterator, OutputIterator></a> ps;
<a name="l01788"></a>01788 <span class="keywordflow">return</span> ps.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a34f6cdc9223e0e99c671e07a15086e3e" title="Performs Lang approximation (LA).">Lang</a> (first, last, tol, look_ahead, result);
<a name="l01789"></a>01789 }
<a name="l01790"></a>01790
<a name="l01803"></a>01803 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> ForwardIterator, <span class="keyword">class</span> OutputIterator>
<a name="l01804"></a><a class="code" href="namespacepsimpl.html#ab71cedd762eee4006a85f4321fca6cad">01804</a> OutputIterator <a class="code" href="namespacepsimpl.html#ab71cedd762eee4006a85f4321fca6cad" title="Performs Douglas-Peucker polyline simplification (DP).">simplify_douglas_peucker</a> (
<a name="l01805"></a>01805 ForwardIterator first,
<a name="l01806"></a>01806 ForwardIterator last,
<a name="l01807"></a>01807 <span class="keyword">typename</span> std::iterator_traits <ForwardIterator>::value_type tol,
<a name="l01808"></a>01808 OutputIterator result)
<a name="l01809"></a>01809 {
<a name="l01810"></a>01810 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, ForwardIterator, OutputIterator></a> ps;
<a name="l01811"></a>01811 <span class="keywordflow">return</span> ps.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a75954f25bc0d99e0a756611ffa2b5fda" title="Performs Douglas-Peucker approximation (DP).">DouglasPeucker</a> (first, last, tol, result);
<a name="l01812"></a>01812 }
<a name="l01813"></a>01813
<a name="l01826"></a>01826 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> ForwardIterator, <span class="keyword">class</span> OutputIterator>
<a name="l01827"></a><a class="code" href="namespacepsimpl.html#aeff1b138293ca9cfb855d7e1f69dacf5">01827</a> OutputIterator <a class="code" href="namespacepsimpl.html#aeff1b138293ca9cfb855d7e1f69dacf5" title="Performs a variant of Douglas-Peucker polyline simplification (DPn).">simplify_douglas_peucker_n</a> (
<a name="l01828"></a>01828 ForwardIterator first,
<a name="l01829"></a>01829 ForwardIterator last,
<a name="l01830"></a>01830 <span class="keywordtype">unsigned</span> count,
<a name="l01831"></a>01831 OutputIterator result)
<a name="l01832"></a>01832 {
<a name="l01833"></a>01833 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, ForwardIterator, OutputIterator></a> ps;
<a name="l01834"></a>01834 <span class="keywordflow">return</span> ps.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#ae309320bd688e6752c8d1e70ff58e4c1" title="Performs a Douglas-Peucker approximation variant (DPn).">DouglasPeuckerN</a> (first, last, count, result);
<a name="l01835"></a>01835 }
<a name="l01836"></a>01836
<a name="l01851"></a>01851 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> ForwardIterator, <span class="keyword">class</span> OutputIterator>
<a name="l01852"></a><a class="code" href="namespacepsimpl.html#a187709033361ba469a60c3a848328118">01852</a> OutputIterator <a class="code" href="namespacepsimpl.html#a187709033361ba469a60c3a848328118" title="Computes the squared positional error between a polyline and its simplification.">compute_positional_errors2</a> (
<a name="l01853"></a>01853 ForwardIterator original_first,
<a name="l01854"></a>01854 ForwardIterator original_last,
<a name="l01855"></a>01855 ForwardIterator simplified_first,
<a name="l01856"></a>01856 ForwardIterator simplified_last,
<a name="l01857"></a>01857 OutputIterator result,
<a name="l01858"></a>01858 <span class="keywordtype">bool</span>* valid=0)
<a name="l01859"></a>01859 {
<a name="l01860"></a>01860 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, ForwardIterator, OutputIterator></a> ps;
<a name="l01861"></a>01861 <span class="keywordflow">return</span> ps.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a6b3ed5157f5bf51ef7be179896cd2903" title="Computes the squared positional error between a polyline and its simplification.">ComputePositionalErrors2</a> (original_first, original_last, simplified_first, simplified_last, result, valid);
<a name="l01862"></a>01862 }
<a name="l01863"></a>01863
<a name="l01877"></a>01877 <span class="keyword">template</span> <<span class="keywordtype">unsigned</span> DIM, <span class="keyword">class</span> ForwardIterator>
<a name="l01878"></a><a class="code" href="namespacepsimpl.html#a16418e391940b20609bc48289e7222a4">01878</a> <a class="code" href="structpsimpl_1_1math_1_1_statistics.html" title="POD structure for storing several statistical values.">math::Statistics</a> <a class="code" href="namespacepsimpl.html#a16418e391940b20609bc48289e7222a4" title="Computes statistics for the positional errors between a polyline and its simplification.">compute_positional_error_statistics</a> (
<a name="l01879"></a>01879 ForwardIterator original_first,
<a name="l01880"></a>01880 ForwardIterator original_last,
<a name="l01881"></a>01881 ForwardIterator simplified_first,
<a name="l01882"></a>01882 ForwardIterator simplified_last,
<a name="l01883"></a>01883 <span class="keywordtype">bool</span>* valid=0)
<a name="l01884"></a>01884 {
<a name="l01885"></a>01885 <a class="code" href="classpsimpl_1_1_polyline_simplification.html" title="Provides various simplification algorithms for n-dimensional simple polylines.">PolylineSimplification <DIM, ForwardIterator, ForwardIterator></a> ps;
<a name="l01886"></a>01886 <span class="keywordflow">return</span> ps.<a class="code" href="classpsimpl_1_1_polyline_simplification.html#a10af204d445105a8a4cbc81bd0563cb1" title="Computes statistics for the positional errors between a polyline and its simplification.">ComputePositionalErrorStatistics</a> (original_first, original_last, simplified_first, simplified_last, valid);
<a name="l01887"></a>01887 }
<a name="l01888"></a>01888 }
<a name="l01889"></a>01889
<a name="l01890"></a>01890 <span class="preprocessor">#endif // PSIMPL_GENERIC</span>
</pre></div></div>
</div>
<div id="nav-path" class="navpath">
<ul>
<li class="navelem"><a class="el" href="psimpl_8h.html">psimpl.h</a> </li>
<li class="footer">Generated on Fri Jun 24 2011 14:56:29 for psimpl by 
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.7.4 </li>
</ul>
</div>
</body>
</html>
Submit an article or tip