<!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: psimpl::PolylineSimplification< DIM, InputIterator, OutputIterator > Class Template Reference</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 class="current"><a href="annotated.html"><span>Classes</span></a></li>
<li><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="annotated.html"><span>Class List</span></a></li>
<li><a href="classes.html"><span>Class Index</span></a></li>
<li><a href="functions.html"><span>Class Members</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('classpsimpl_1_1_polyline_simplification.html','');
</script>
<div id="doc-content">
<div class="header">
<div class="summary">
<a href="#nested-classes">Classes</a> |
<a href="#pub-methods">Public Member Functions</a> |
<a href="#pri-types">Private Types</a> |
<a href="#pri-methods">Private Member Functions</a> </div>
<div class="headertitle">
<div class="title">psimpl::PolylineSimplification< DIM, InputIterator, OutputIterator > Class Template Reference</div> </div>
</div>
<div class="contents">
<!-- doxytag: class="psimpl::PolylineSimplification" -->
<p>Provides various simplification algorithms for n-dimensional simple polylines.
<a href="classpsimpl_1_1_polyline_simplification.html#details">More...</a></p>
<p><code>#include <<a class="el" href="psimpl_8h_source.html">psimpl.h</a>></code></p>
<p><a href="classpsimpl_1_1_polyline_simplification-members.html">List of all members.</a></p>
<table class="memberdecls">
<tr><td colspan="2"><h2><a name="nested-classes"></a>
Classes</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">class  </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html">DPHelper</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Douglas-Peucker approximation helper class. <a href="classpsimpl_1_1_polyline_simplification_1_1_d_p_helper.html#details">More...</a><br/></td></tr>
<tr><td colspan="2"><h2><a name="pub-methods"></a>
Public Member Functions</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">OutputIterator </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#ace21c52fe251f03dc87d17e2627f83ed">NthPoint</a> (InputIterator first, InputIterator last, unsigned n, OutputIterator result)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Performs the nth point routine (NP). <a href="#ace21c52fe251f03dc87d17e2627f83ed"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">OutputIterator </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#aa9f3491a3aa88e3b795705045053a649">RadialDistance</a> (InputIterator first, InputIterator last, <a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol, OutputIterator result)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Performs the (radial) distance between points routine (RD). <a href="#aa9f3491a3aa88e3b795705045053a649"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">OutputIterator </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a2b10f2aeaec1cb48eb053b2b9f632c9c">PerpendicularDistance</a> (InputIterator first, InputIterator last, <a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol, unsigned repeat, OutputIterator result)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Repeatedly performs the perpendicular distance routine (PD). <a href="#a2b10f2aeaec1cb48eb053b2b9f632c9c"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">OutputIterator </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a54fec7f2139b6ec1b82ca884fc402f2f">PerpendicularDistance</a> (InputIterator first, InputIterator last, <a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol, OutputIterator result)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Performs the perpendicular distance routine (PD). <a href="#a54fec7f2139b6ec1b82ca884fc402f2f"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">OutputIterator </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#ae938c132f029b4e8e828f5e6c7ee4b16">ReumannWitkam</a> (InputIterator first, InputIterator last, <a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol, OutputIterator result)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Performs Reumann-Witkam approximation (RW). <a href="#ae938c132f029b4e8e828f5e6c7ee4b16"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">OutputIterator </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a0b9bf4a27ef12a4eb103266f50c6eb7e">Opheim</a> (InputIterator first, InputIterator last, <a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> min_tol, <a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> max_tol, OutputIterator result)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Performs Opheim approximation (OP). <a href="#a0b9bf4a27ef12a4eb103266f50c6eb7e"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">OutputIterator </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a34f6cdc9223e0e99c671e07a15086e3e">Lang</a> (InputIterator first, InputIterator last, <a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol, unsigned look_ahead, OutputIterator result)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Performs Lang approximation (LA). <a href="#a34f6cdc9223e0e99c671e07a15086e3e"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">OutputIterator </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a75954f25bc0d99e0a756611ffa2b5fda">DouglasPeucker</a> (InputIterator first, InputIterator last, <a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> tol, OutputIterator result)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Performs Douglas-Peucker approximation (DP). <a href="#a75954f25bc0d99e0a756611ffa2b5fda"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">OutputIterator </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#ae309320bd688e6752c8d1e70ff58e4c1">DouglasPeuckerN</a> (InputIterator first, InputIterator last, unsigned count, OutputIterator result)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Performs a Douglas-Peucker approximation variant (DPn). <a href="#ae309320bd688e6752c8d1e70ff58e4c1"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">OutputIterator </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a6b3ed5157f5bf51ef7be179896cd2903">ComputePositionalErrors2</a> (InputIterator original_first, InputIterator original_last, InputIterator simplified_first, InputIterator simplified_last, OutputIterator result, bool *valid=0)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Computes the squared positional error between a polyline and its simplification. <a href="#a6b3ed5157f5bf51ef7be179896cd2903"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="structpsimpl_1_1math_1_1_statistics.html">math::Statistics</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a10af204d445105a8a4cbc81bd0563cb1">ComputePositionalErrorStatistics</a> (InputIterator original_first, InputIterator original_last, InputIterator simplified_first, InputIterator simplified_last, bool *valid=0)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Computes statistics for the positional errors between a polyline and its simplification. <a href="#a10af204d445105a8a4cbc81bd0563cb1"></a><br/></td></tr>
<tr><td colspan="2"><h2><a name="pri-types"></a>
Private Types</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef std::iterator_traits<br class="typebreak"/>
< InputIterator ><br class="typebreak"/>
::difference_type </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef std::iterator_traits<br class="typebreak"/>
< InputIterator >::<a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef std::iterator_traits<br class="typebreak"/>
< const <a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> * ><br class="typebreak"/>
::difference_type </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a></td></tr>
<tr><td colspan="2"><h2><a name="pri-methods"></a>
Private Member Functions</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#acd517bb1803b28ad69aa9012ac2577e5">CopyKeyAdvance</a> (InputIterator &key, OutputIterator &result)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Copies the key to the output destination, and increments the iterator. <a href="#acd517bb1803b28ad69aa9012ac2577e5"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a">CopyKey</a> (InputIterator key, OutputIterator &result)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Copies the key to the output destination. <a href="#a46fd020dc9f03e4b44bf95f256a06b1a"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19">Advance</a> (InputIterator &it, <a class="el" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> n=1)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Increments the iterator by n points. <a href="#a825677c1dbe228d8904846ea2781ee19"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">InputIterator </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a9c2510b3c8466f2080b924629e8ce2e6">AdvanceCopy</a> (InputIterator it, <a class="el" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> n=1)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Increments a copy of the iterator by n points. <a href="#a9c2510b3c8466f2080b924629e8ce2e6"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">unsigned </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#ab371de18bbb855cbd2912ceea5260519">Forward</a> (InputIterator &it, unsigned n, unsigned &remaining)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Increments the iterator by n points if possible. <a href="#ab371de18bbb855cbd2912ceea5260519"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a5af6938c7d84c84f20c4981a51228865">Backward</a> (InputIterator &it, unsigned &remaining)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Decrements the iterator by 1 point. <a href="#a5af6938c7d84c84f20c4981a51228865"></a><br/></td></tr>
</table>
<hr/><a name="details" id="details"></a><h2>Detailed Description</h2>
<div class="textblock"><h3>template<unsigned DIM, class InputIterator, class OutputIterator><br/>
class psimpl::PolylineSimplification< DIM, InputIterator, OutputIterator ></h3>
<p>Provides various simplification algorithms for n-dimensional simple polylines. </p>
<p>A polyline is simple when it is non-closed and non-selfintersecting. All algorithms operate on input iterators and output iterators. Note that unisgned integer types are NOT supported. </p>
</div><hr/><h2>Member Typedef Documentation</h2>
<a class="anchor" id="a5a3b5d1a275e366f2c0bab770140507c"></a><!-- doxytag: member="psimpl::PolylineSimplification::diff_type" ref="a5a3b5d1a275e366f2c0bab770140507c" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">typedef std::iterator_traits<InputIterator>::difference_type <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::<a class="el" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a><code> [private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
</div>
</div>
<a class="anchor" id="a08f998ecc4af984c070603b489b3ce28"></a><!-- doxytag: member="psimpl::PolylineSimplification::ptr_diff_type" ref="a08f998ecc4af984c070603b489b3ce28" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">typedef std::iterator_traits<const <a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a>*>::difference_type <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::<a class="el" href="classpsimpl_1_1_polyline_simplification.html#a08f998ecc4af984c070603b489b3ce28">ptr_diff_type</a><code> [private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
</div>
</div>
<a class="anchor" id="aacad79ca2e6dc004483838f460ab8df1"></a><!-- doxytag: member="psimpl::PolylineSimplification::value_type" ref="aacad79ca2e6dc004483838f460ab8df1" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">typedef std::iterator_traits<InputIterator>::<a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::<a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a><code> [private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
</div>
</div>
<hr/><h2>Member Function Documentation</h2>
<a class="anchor" id="a825677c1dbe228d8904846ea2781ee19"></a><!-- doxytag: member="psimpl::PolylineSimplification::Advance" ref="a825677c1dbe228d8904846ea2781ee19" args="(InputIterator &it, diff_type n=1)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::Advance </td>
<td>(</td>
<td class="paramtype">InputIterator & </td>
<td class="paramname"><em>it</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> </td>
<td class="paramname"><em>n</em> = <code>1</code> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Increments the iterator by n points. </p>
<dl class="see"><dt><b>See also:</b></dt><dd><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a9c2510b3c8466f2080b924629e8ce2e6" title="Increments a copy of the iterator by n points.">AdvanceCopy</a></dd></dl>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in,out]</td><td class="paramname">it</td><td>iterator to be advanced </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">n</td><td>number of points to advance </td></tr>
</table>
</dd>
</dl>
</div>
</div>
<a class="anchor" id="a9c2510b3c8466f2080b924629e8ce2e6"></a><!-- doxytag: member="psimpl::PolylineSimplification::AdvanceCopy" ref="a9c2510b3c8466f2080b924629e8ce2e6" args="(InputIterator it, diff_type n=1)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">InputIterator <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::AdvanceCopy </td>
<td>(</td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>it</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a5a3b5d1a275e366f2c0bab770140507c">diff_type</a> </td>
<td class="paramname"><em>n</em> = <code>1</code> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Increments a copy of the iterator by n points. </p>
<dl class="see"><dt><b>See also:</b></dt><dd><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a825677c1dbe228d8904846ea2781ee19" title="Increments the iterator by n points.">Advance</a></dd></dl>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">it</td><td>iterator to be advanced </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">n</td><td>number of points to advance </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>an incremented copy of the input iterator </dd></dl>
</div>
</div>
<a class="anchor" id="a5af6938c7d84c84f20c4981a51228865"></a><!-- doxytag: member="psimpl::PolylineSimplification::Backward" ref="a5af6938c7d84c84f20c4981a51228865" args="(InputIterator &it, unsigned &remaining)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::Backward </td>
<td>(</td>
<td class="paramtype">InputIterator & </td>
<td class="paramname"><em>it</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned & </td>
<td class="paramname"><em>remaining</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Decrements the iterator by 1 point. </p>
<dl class="see"><dt><b>See also:</b></dt><dd><a class="el" href="classpsimpl_1_1_polyline_simplification.html#ab371de18bbb855cbd2912ceea5260519" title="Increments the iterator by n points if possible.">Forward</a></dd></dl>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in,out]</td><td class="paramname">it</td><td>iterator to be advanced </td></tr>
<tr><td class="paramdir">[in,out]</td><td class="paramname">remaining</td><td>number of points remaining after it </td></tr>
</table>
</dd>
</dl>
</div>
</div>
<a class="anchor" id="a6b3ed5157f5bf51ef7be179896cd2903"></a><!-- doxytag: member="psimpl::PolylineSimplification::ComputePositionalErrors2" ref="a6b3ed5157f5bf51ef7be179896cd2903" args="(InputIterator original_first, InputIterator original_last, InputIterator simplified_first, InputIterator simplified_last, OutputIterator result, bool *valid=0)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">OutputIterator <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::ComputePositionalErrors2 </td>
<td>(</td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>original_first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>original_last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>simplified_first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>simplified_last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator </td>
<td class="paramname"><em>result</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">bool * </td>
<td class="paramname"><em>valid</em> = <code>0</code> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Computes the squared positional error between a polyline and its simplification. </p>
<p>For each point in the range [original_first, original_last) the squared distance to the simplification [simplified_first, simplified_last) is calculated. Each positional error is copied to the output range [result, result + count), where count is the number of points in the original polyline. The return value is the end of the output range: result + count.</p>
<p>Note that both the original and simplified polyline must be defined using the same value_type.</p>
<div class="image">
<img src="psimpl_pos_error.png" alt="psimpl_pos_error.png"/>
</div>
<p>Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The InputIterator value type is convertible to a value type of the output iterator 4- The ranges [original_first, original_last) and [simplified_first, simplified_last) contain vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The ranges [original_first, original_last) and [simplified_first, simplified_last) contain a minimum of 2 vertices 6- The range [simplified_first, simplified_last) represents a simplification of the range [original_first, original_last), meaning each point in the simplification has the exact same coordinates as some point from the original polyline</p>
<p>In case these requirements are not met, the valid flag is set to false OR compile errors may occur.</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">original_first</td><td>the first coordinate of the first polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">original_last</td><td>one beyond the last coordinate of the last polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">simplified_first</td><td>the first coordinate of the first simplified polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">simplified_last</td><td>one beyond the last coordinate of the last simplified polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">result</td><td>destination of the squared positional errors </td></tr>
<tr><td class="paramdir">[out]</td><td class="paramname">valid</td><td>[optional] indicates if the computed positional errors are valid </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>one beyond the last computed positional error </dd></dl>
</div>
</div>
<a class="anchor" id="a10af204d445105a8a4cbc81bd0563cb1"></a><!-- doxytag: member="psimpl::PolylineSimplification::ComputePositionalErrorStatistics" ref="a10af204d445105a8a4cbc81bd0563cb1" args="(InputIterator original_first, InputIterator original_last, InputIterator simplified_first, InputIterator simplified_last, bool *valid=0)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="structpsimpl_1_1math_1_1_statistics.html">math::Statistics</a> <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::ComputePositionalErrorStatistics </td>
<td>(</td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>original_first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>original_last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>simplified_first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>simplified_last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">bool * </td>
<td class="paramname"><em>valid</em> = <code>0</code> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Computes statistics for the positional errors between a polyline and its simplification. </p>
<p>Various statistics (mean, max, sum, std) are calculated for the positional errors between the range [original_first, original_last) and its simplification the range [simplified_first, simplified_last).</p>
<p>Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The InputIterator value type is convertible to double 4- The ranges [original_first, original_last) and [simplified_first, simplified_last) contain vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The ranges [original_first, original_last) and [simplified_first, simplified_last) contain a minimum of 2 vertices 6- The range [simplified_first, simplified_last) represents a simplification of the range [original_first, original_last), meaning each point in the simplification has the exact same coordinates as some point from the original polyline</p>
<p>In case these requirements are not met, the valid flag is set to false OR compile errors may occur.</p>
<dl class="see"><dt><b>See also:</b></dt><dd><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a6b3ed5157f5bf51ef7be179896cd2903" title="Computes the squared positional error between a polyline and its simplification.">ComputePositionalErrors2</a></dd></dl>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">original_first</td><td>the first coordinate of the first polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">original_last</td><td>one beyond the last coordinate of the last polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">simplified_first</td><td>the first coordinate of the first simplified polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">simplified_last</td><td>one beyond the last coordinate of the last simplified polyline point </td></tr>
<tr><td class="paramdir">[out]</td><td class="paramname">valid</td><td>[optional] indicates if the computed statistics are valid </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>the computed statistics </dd></dl>
</div>
</div>
<a class="anchor" id="a46fd020dc9f03e4b44bf95f256a06b1a"></a><!-- doxytag: member="psimpl::PolylineSimplification::CopyKey" ref="a46fd020dc9f03e4b44bf95f256a06b1a" args="(InputIterator key, OutputIterator &result)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::CopyKey </td>
<td>(</td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>key</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator & </td>
<td class="paramname"><em>result</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Copies the key to the output destination. </p>
<dl class="see"><dt><b>See also:</b></dt><dd><a class="el" href="classpsimpl_1_1_polyline_simplification.html#acd517bb1803b28ad69aa9012ac2577e5" title="Copies the key to the output destination, and increments the iterator.">CopyKeyAdvance</a></dd></dl>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">key</td><td>the first coordinate of the key </td></tr>
<tr><td class="paramdir">[in,out]</td><td class="paramname">result</td><td>destination of the copied key </td></tr>
</table>
</dd>
</dl>
</div>
</div>
<a class="anchor" id="acd517bb1803b28ad69aa9012ac2577e5"></a><!-- doxytag: member="psimpl::PolylineSimplification::CopyKeyAdvance" ref="acd517bb1803b28ad69aa9012ac2577e5" args="(InputIterator &key, OutputIterator &result)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::CopyKeyAdvance </td>
<td>(</td>
<td class="paramtype">InputIterator & </td>
<td class="paramname"><em>key</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator & </td>
<td class="paramname"><em>result</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Copies the key to the output destination, and increments the iterator. </p>
<dl class="see"><dt><b>See also:</b></dt><dd><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a46fd020dc9f03e4b44bf95f256a06b1a" title="Copies the key to the output destination.">CopyKey</a></dd></dl>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in,out]</td><td class="paramname">key</td><td>the first coordinate of the key </td></tr>
<tr><td class="paramdir">[in,out]</td><td class="paramname">result</td><td>destination of the copied key </td></tr>
</table>
</dd>
</dl>
</div>
</div>
<a class="anchor" id="a75954f25bc0d99e0a756611ffa2b5fda"></a><!-- doxytag: member="psimpl::PolylineSimplification::DouglasPeucker" ref="a75954f25bc0d99e0a756611ffa2b5fda" args="(InputIterator first, InputIterator last, value_type tol, OutputIterator result)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">OutputIterator <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::DouglasPeucker </td>
<td>(</td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> </td>
<td class="paramname"><em>tol</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator </td>
<td class="paramname"><em>result</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Performs Douglas-Peucker approximation (DP). </p>
<p>The DP algorithm uses the RadialDistance (RD) routine O(n) as a preprocessing step. After RD the algorithm is O (n m) in worst case and O(n log m) on average, where m < n (m is the number of points after RD).</p>
<p>The DP algorithm starts with a simplification that is the single edge joining the first and last vertices of the polyline. The distance of the remaining vertices to that edge are computed. The vertex that is furthest away from theedge (called a key), and has a computed distance that is larger than a specified tolerance, will be added to the simplification. This process will recurse for each edge in the current simplification, untill all vertices of the original polyline are within tolerance.</p>
<div class="image">
<img src="psimpl_dp.png" alt="psimpl_dp.png"/>
</div>
<p>Note that this algorithm will create a copy of the input polyline during the vertex reduction step.</p>
<p>RD followed by DP is applied to the range [first, last) using the specified tolerance tol. The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.</p>
<p>Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The InputIterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- tol is not 0</p>
<p>In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>the first coordinate of the first polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>one beyond the last coordinate of the last polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">tol</td><td>perpendicular (point-to-segment) distance tolerance </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">result</td><td>destination of the simplified polyline </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>one beyond the last coordinate of the simplified polyline </dd></dl>
</div>
</div>
<a class="anchor" id="ae309320bd688e6752c8d1e70ff58e4c1"></a><!-- doxytag: member="psimpl::PolylineSimplification::DouglasPeuckerN" ref="ae309320bd688e6752c8d1e70ff58e4c1" args="(InputIterator first, InputIterator last, unsigned count, OutputIterator result)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">OutputIterator <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::DouglasPeuckerN </td>
<td>(</td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned </td>
<td class="paramname"><em>count</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator </td>
<td class="paramname"><em>result</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Performs a Douglas-Peucker approximation variant (DPn). </p>
<p>This algorithm is a variation of the original implementation. Instead of considering one polyline segment at a time, all segments of the current simplified polyline are evaluated at each step. Only the vertex with the maximum distance from its edge is added to the simplification. This process will recurse untill the the simplification contains the desired amount of vertices.</p>
<p>The algorithm, which does not use the (radial) distance between points routine as a preprocessing step, is O(n2) in worst case and O(n log n) on average.</p>
<p>Note that this algorithm will create a copy of the input polyline for performance reasons.</p>
<p>DPn is applied to the range [first, last). The resulting simplified polyline consists of count vertices and is copied to the output range [result, result + count). The return value is the end of the output range: result + count.</p>
<p>Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The InputIterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains a minimum of count vertices 6- count is at least 2</p>
<p>In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.</p>
<dl class="see"><dt><b>See also:</b></dt><dd><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a75954f25bc0d99e0a756611ffa2b5fda" title="Performs Douglas-Peucker approximation (DP).">DouglasPeucker</a></dd></dl>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>the first coordinate of the first polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>one beyond the last coordinate of the last polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">count</td><td>the maximum number of points of the simplified polyline </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">result</td><td>destination of the simplified polyline </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>one beyond the last coordinate of the simplified polyline </dd></dl>
</div>
</div>
<a class="anchor" id="ab371de18bbb855cbd2912ceea5260519"></a><!-- doxytag: member="psimpl::PolylineSimplification::Forward" ref="ab371de18bbb855cbd2912ceea5260519" args="(InputIterator &it, unsigned n, unsigned &remaining)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">unsigned <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::Forward </td>
<td>(</td>
<td class="paramtype">InputIterator & </td>
<td class="paramname"><em>it</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned </td>
<td class="paramname"><em>n</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned & </td>
<td class="paramname"><em>remaining</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Increments the iterator by n points if possible. </p>
<p>If there are fewer than n point remaining the iterator will be incremented to the last point.</p>
<dl class="see"><dt><b>See also:</b></dt><dd><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a5af6938c7d84c84f20c4981a51228865" title="Decrements the iterator by 1 point.">Backward</a></dd></dl>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in,out]</td><td class="paramname">it</td><td>iterator to be advanced </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">n</td><td>number of points to advance </td></tr>
<tr><td class="paramdir">[in,out]</td><td class="paramname">remaining</td><td>number of points remaining after it </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>the actual amount of points that the iterator advanced </dd></dl>
</div>
</div>
<a class="anchor" id="a34f6cdc9223e0e99c671e07a15086e3e"></a><!-- doxytag: member="psimpl::PolylineSimplification::Lang" ref="a34f6cdc9223e0e99c671e07a15086e3e" args="(InputIterator first, InputIterator last, value_type tol, unsigned look_ahead, OutputIterator result)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">OutputIterator <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::Lang </td>
<td>(</td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> </td>
<td class="paramname"><em>tol</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned </td>
<td class="paramname"><em>look_ahead</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator </td>
<td class="paramname"><em>result</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Performs Lang approximation (LA). </p>
<p>The LA routine defines a fixed size search-region. The first and last points of that search region form a segment. This segment is used to calculate the perpendicular distance to each intermediate point. If any calculated distance is larger than the specified tolerance, the search region will be shrunk by excluding its last point. This process will continue untill all calculated distances fall below the specified tolerance , or there are no more intermediate points. At this point all intermediate points are removed and a new search region is defined starting at the last point from old search region. Note that the size of the search region (look_ahead parameter) controls the maximum amount of simplification, e.g.: a size of 20 will always result in a simplification that contains at least 5% of the original points.</p>
<div class="image">
<img src="psimpl_la.png" alt="psimpl_la.png"/>
</div>
<p>LA routine is applied to the range [first, last) using the specified tolerance and look ahead values. The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.</p>
<p>Input (Type) Requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a bidirectional iterator 3- The InputIterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- tol is not 0 7- look_ahead is not zero</p>
<p>In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>the first coordinate of the first polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>one beyond the last coordinate of the last polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">tol</td><td>perpendicular (point-to-segment) distance tolerance </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">look_ahead</td><td>defines the size of the search region </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">result</td><td>destination of the simplified polyline </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>one beyond the last coordinate of the simplified polyline </dd></dl>
</div>
</div>
<a class="anchor" id="ace21c52fe251f03dc87d17e2627f83ed"></a><!-- doxytag: member="psimpl::PolylineSimplification::NthPoint" ref="ace21c52fe251f03dc87d17e2627f83ed" args="(InputIterator first, InputIterator last, unsigned n, OutputIterator result)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">OutputIterator <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::NthPoint </td>
<td>(</td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned </td>
<td class="paramname"><em>n</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator </td>
<td class="paramname"><em>result</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Performs the nth point routine (NP). </p>
<p>NP is an O(n) algorithm for polyline simplification. It keeps only the first, last and each nth point. As an example, consider any random line of 8 points. Using n = 3 will always yield a simplification consisting of points: 1, 4, 7, 8</p>
<div class="image">
<img src="psimpl_np.png" alt="psimpl_np.png"/>
</div>
<p>NP is applied to the range [first, last). The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.</p>
<p>Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The input iterator value type is convertible to a value type of the OutputIterator 4- The range [first, last) contains only vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- n is not 0</p>
<p>In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>the first coordinate of the first polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>one beyond the last coordinate of the last polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">n</td><td>specifies 'each nth point' </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">result</td><td>destination of the simplified polyline </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>one beyond the last coordinate of the simplified polyline </dd></dl>
</div>
</div>
<a class="anchor" id="a0b9bf4a27ef12a4eb103266f50c6eb7e"></a><!-- doxytag: member="psimpl::PolylineSimplification::Opheim" ref="a0b9bf4a27ef12a4eb103266f50c6eb7e" args="(InputIterator first, InputIterator last, value_type min_tol, value_type max_tol, OutputIterator result)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">OutputIterator <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::Opheim </td>
<td>(</td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> </td>
<td class="paramname"><em>min_tol</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> </td>
<td class="paramname"><em>max_tol</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator </td>
<td class="paramname"><em>result</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Performs Opheim approximation (OP). </p>
<p>The O(n) OP routine is very similar to the Reumann-Witkam (RW) routine, and can be seen as a constrained version of that RW routine. OP uses both a minimum and a maximum distance tolerance to constrain the search area. For each successive vertex vi, its radial distance to the current key vkey (initially v0) is calculated. The last point within the minimum distance tolerance is used to define a ray R (vkey, vi). If no such vi exists, the ray is defined as R(vkey, vkey+1). For each successive vertex vj beyond vi its perpendicular distance to the ray R is calculated. A new key is found at vj-1, when this distance exceeds the minimum tolerance Or when the radial distance between vj and the vkey exceeds the maximum tolerance. After a new key is found, the process repeats itself.</p>
<div class="image">
<img src="psimpl_op.png" alt="psimpl_op.png"/>
</div>
<p>OP routine is applied to the range [first, last) using the specified distance tolerances min_tol and max_tol. The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.</p>
<p>Input (Type) Requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The input iterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- min_tol is not 0 7- max_tol is not 0</p>
<p>In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>the first coordinate of the first polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>one beyond the last coordinate of the last polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">min_tol</td><td>radial and perpendicular (point-to-ray) distance tolerance </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">max_tol</td><td>radial distance tolerance </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">result</td><td>destination of the simplified polyline </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>one beyond the last coordinate of the simplified polyline </dd></dl>
</div>
</div>
<a class="anchor" id="a54fec7f2139b6ec1b82ca884fc402f2f"></a><!-- doxytag: member="psimpl::PolylineSimplification::PerpendicularDistance" ref="a54fec7f2139b6ec1b82ca884fc402f2f" args="(InputIterator first, InputIterator last, value_type tol, OutputIterator result)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">OutputIterator <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::PerpendicularDistance </td>
<td>(</td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> </td>
<td class="paramname"><em>tol</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator </td>
<td class="paramname"><em>result</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Performs the perpendicular distance routine (PD). </p>
<p>PD is an O(n) algorithm for polyline simplification. It computes the perpendicular distance of each point pi to the line segment S(pi-1, pi+1). Only when this distance is larger than the given tolerance will pi be part of the simpification. Note that the original polyline can only be reduced by a maximum of 50%. Multiple passes are required to achieve higher points reductions.</p>
<div class="image">
<img src="psimpl_pd.png" alt="psimpl_pd.png"/>
</div>
<p>PD is applied to the range [first, last) using the specified tolerance tol. The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.</p>
<p>Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The input iterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains only vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- tol is not 0</p>
<p>In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>the first coordinate of the first polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>one beyond the last coordinate of the last polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">tol</td><td>perpendicular (segment-to-point) distance tolerance </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">result</td><td>destination of the simplified polyline </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>one beyond the last coordinate of the simplified polyline </dd></dl>
</div>
</div>
<a class="anchor" id="a2b10f2aeaec1cb48eb053b2b9f632c9c"></a><!-- doxytag: member="psimpl::PolylineSimplification::PerpendicularDistance" ref="a2b10f2aeaec1cb48eb053b2b9f632c9c" args="(InputIterator first, InputIterator last, value_type tol, unsigned repeat, OutputIterator result)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">OutputIterator <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::PerpendicularDistance </td>
<td>(</td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> </td>
<td class="paramname"><em>tol</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned </td>
<td class="paramname"><em>repeat</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator </td>
<td class="paramname"><em>result</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Repeatedly performs the perpendicular distance routine (PD). </p>
<p>The algorithm stops after calling the PD routine 'repeat' times OR when the simplification does not improve. Note that this algorithm will need to store up to two intermediate simplification results.</p>
<dl class="see"><dt><b>See also:</b></dt><dd><a class="el" href="classpsimpl_1_1_polyline_simplification.html#a54fec7f2139b6ec1b82ca884fc402f2f" title="Performs the perpendicular distance routine (PD).">PerpendicularDistance(InputIterator, InputIterator, value_type, OutputIterator)</a></dd></dl>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>the first coordinate of the first polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>one beyond the last coordinate of the last polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">tol</td><td>perpendicular (segment-to-point) distance tolerance </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">repeat</td><td>the number of times to successively apply the PD routine </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">result</td><td>destination of the simplified polyline </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>one beyond the last coordinate of the simplified polyline </dd></dl>
</div>
</div>
<a class="anchor" id="aa9f3491a3aa88e3b795705045053a649"></a><!-- doxytag: member="psimpl::PolylineSimplification::RadialDistance" ref="aa9f3491a3aa88e3b795705045053a649" args="(InputIterator first, InputIterator last, value_type tol, OutputIterator result)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">OutputIterator <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::RadialDistance </td>
<td>(</td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> </td>
<td class="paramname"><em>tol</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator </td>
<td class="paramname"><em>result</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Performs the (radial) distance between points routine (RD). </p>
<p>RD is a brute-force O(n) algorithm for polyline simplification. It reduces successive vertices that are clustered too closely to a single vertex, called a key. The resulting keys form the simplified polyline.</p>
<div class="image">
<img src="psimpl_rd.png" alt="psimpl_rd.png"/>
</div>
<p>RD is applied to the range [first, last) using the specified tolerance tol. The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.</p>
<p>Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The input iterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains only vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- tol is not 0</p>
<p>In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>the first coordinate of the first polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>one beyond the last coordinate of the last polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">tol</td><td>radial (point-to-point) distance tolerance </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">result</td><td>destination of the simplified polyline </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>one beyond the last coordinate of the simplified polyline </dd></dl>
</div>
</div>
<a class="anchor" id="ae938c132f029b4e8e828f5e6c7ee4b16"></a><!-- doxytag: member="psimpl::PolylineSimplification::ReumannWitkam" ref="ae938c132f029b4e8e828f5e6c7ee4b16" args="(InputIterator first, InputIterator last, value_type tol, OutputIterator result)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<unsigned DIM, class InputIterator, class OutputIterator> </div>
<table class="memname">
<tr>
<td class="memname">OutputIterator <a class="el" href="classpsimpl_1_1_polyline_simplification.html">psimpl::PolylineSimplification</a>< DIM, InputIterator, OutputIterator >::ReumannWitkam </td>
<td>(</td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">InputIterator </td>
<td class="paramname"><em>last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="classpsimpl_1_1_polyline_simplification.html#aacad79ca2e6dc004483838f460ab8df1">value_type</a> </td>
<td class="paramname"><em>tol</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">OutputIterator </td>
<td class="paramname"><em>result</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Performs Reumann-Witkam approximation (RW). </p>
<p>The O(n) RW routine uses a point-to-line (perpendicular) distance tolerance. It defines a line through the first two vertices of the original polyline. For each successive vertex vi its perpendicular distance to this line is calculated. A new key is found at vi-1, when this distance exceeds the specified tolerance. The vertices vi and vi+1 are then used to define a new line, and the process repeats itself.</p>
<div class="image">
<img src="psimpl_rw.png" alt="psimpl_rw.png"/>
</div>
<p>RW routine is applied to the range [first, last) using the specified perpendicular distance tolerance tol. The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.</p>
<p>Input (Type) Requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The input iterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- tol is not 0</p>
<p>In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>the first coordinate of the first polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>one beyond the last coordinate of the last polyline point </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">tol</td><td>perpendicular (point-to-line) distance tolerance </td></tr>
<tr><td class="paramdir">[in]</td><td class="paramname">result</td><td>destination of the simplified polyline </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>one beyond the last coordinate of the simplified polyline </dd></dl>
</div>
</div>
<hr/>The documentation for this class was generated from the following file:<ul>
<li>D:/Code/Projects/psimpl/trunk/lib/<a class="el" href="psimpl_8h_source.html">psimpl.h</a></li>
</ul>
</div>
</div>
<div id="nav-path" class="navpath">
<ul>
<li class="navelem"><a class="el" href="namespacepsimpl.html">psimpl</a> </li>
<li class="navelem"><a class="el" href="classpsimpl_1_1_polyline_simplification.html">PolylineSimplification</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