blob: fbc73c39a5b062afef85e6fa80fdcb9de4827195 [file] [log] [blame]
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!-- NewPage -->
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html" charset="UTF-8">
<title>MonotoneChain (Apache Commons Math 3.3 API)</title>
<link rel="stylesheet" type="text/css" href="../../../../../../../../stylesheet.css" title="Style">
</head>
<body>
<script type="text/javascript"><!--
if (location.href.indexOf('is-external=true') == -1) {
parent.document.title="MonotoneChain (Apache Commons Math 3.3 API)";
}
//-->
</script>
<noscript>
<div>JavaScript is disabled on your browser.</div>
</noscript>
<!-- ========= START OF TOP NAVBAR ======= -->
<div class="topNav"><a name="navbar_top">
<!-- -->
</a><a href="#skip-navbar_top" title="Skip navigation links"></a><a name="navbar_top_firstrow">
<!-- -->
</a>
<ul class="navList" title="Navigation">
<li><a href="../../../../../../../../overview-summary.html">Overview</a></li>
<li><a href="package-summary.html">Package</a></li>
<li class="navBarCell1Rev">Class</li>
<li><a href="class-use/MonotoneChain.html">Use</a></li>
<li><a href="package-tree.html">Tree</a></li>
<li><a href="../../../../../../../../deprecated-list.html">Deprecated</a></li>
<li><a href="../../../../../../../../index-all.html">Index</a></li>
<li><a href="../../../../../../../../help-doc.html">Help</a></li>
</ul>
<div class="aboutLanguage"><em><script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script></em></div>
</div>
<div class="subNav">
<ul class="navList">
<li><a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2D.html" title="interface in org.apache.commons.math3.geometry.euclidean.twod.hull"><span class="strong">Prev Class</span></a></li>
<li>Next Class</li>
</ul>
<ul class="navList">
<li><a href="../../../../../../../../index.html?org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.html" target="_top">Frames</a></li>
<li><a href="MonotoneChain.html" target="_top">No Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_top">
<li><a href="../../../../../../../../allclasses-noframe.html">All Classes</a></li>
</ul>
<div>
<script type="text/javascript"><!--
allClassesLink = document.getElementById("allclasses_navbar_top");
if(window==top) {
allClassesLink.style.display = "block";
}
else {
allClassesLink.style.display = "none";
}
//-->
</script>
</div>
<div>
<ul class="subNavList">
<li>Summary:&nbsp;</li>
<li>Nested&nbsp;|&nbsp;</li>
<li>Field&nbsp;|&nbsp;</li>
<li><a href="#constructor_summary">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method_summary">Method</a></li>
</ul>
<ul class="subNavList">
<li>Detail:&nbsp;</li>
<li>Field&nbsp;|&nbsp;</li>
<li><a href="#constructor_detail">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method_detail">Method</a></li>
</ul>
</div>
<a name="skip-navbar_top">
<!-- -->
</a></div>
<!-- ========= END OF TOP NAVBAR ========= -->
<!-- ======== START OF CLASS DATA ======== -->
<div class="header">
<div class="subTitle">org.apache.commons.math3.geometry.euclidean.twod.hull</div>
<h2 title="Class MonotoneChain" class="title">Class MonotoneChain</h2>
</div>
<div class="contentContainer">
<ul class="inheritance">
<li><a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">java.lang.Object</a></li>
<li>
<ul class="inheritance">
<li>org.apache.commons.math3.geometry.euclidean.twod.hull.MonotoneChain</li>
</ul>
</li>
</ul>
<div class="description">
<ul class="blockList">
<li class="blockList">
<dl>
<dt>All Implemented Interfaces:</dt>
<dd><a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2D.html" title="interface in org.apache.commons.math3.geometry.euclidean.twod.hull">ConvexHullGenerator2D</a>, <a href="../../../../../../../../org/apache/commons/math3/geometry/hull/ConvexHullGenerator.html" title="interface in org.apache.commons.math3.geometry.hull">ConvexHullGenerator</a>&lt;<a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/Euclidean2D.html" title="class in org.apache.commons.math3.geometry.euclidean.twod">Euclidean2D</a>,<a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/Vector2D.html" title="class in org.apache.commons.math3.geometry.euclidean.twod">Vector2D</a>&gt;</dd>
</dl>
<hr>
<br>
<pre>public class <span class="strong">MonotoneChain</span>
extends <a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">Object</a></pre>
<div class="block">Implements Andrew's monotone chain method to generate the convex hull of a finite set of
points in the two-dimensional euclidean space.
<p>
The runtime complexity is O(n log n), with n being the number of input points. If the
point set is already sorted (by x-coordinate), the runtime complexity is O(n).
<p>
The implementation is not sensitive to collinear points on the hull. The parameter
<code>includeCollinearPoints</code> allows to control the behavior with regard to collinear points.
If <code>true</code>, all points on the boundary of the hull will be added to the hull vertices,
otherwise only the extreme points will be present. By default, collinear points are not added
as hull vertices.
<p>
The <code>tolerance</code> parameter (default: 1e-10) is used as epsilon criteria to determine
identical and collinear points.</div>
<dl><dt><span class="strong">Since:</span></dt>
<dd>3.3</dd>
<dt><span class="strong">Version:</span></dt>
<dd>$Id: MonotoneChain.java 1568752 2014-02-16 12:19:51Z tn $</dd>
<dt><span class="strong">See Also:</span></dt><dd><a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain">
Andrew's monotone chain algorithm (Wikibooks)</a></dd></dl>
</li>
</ul>
</div>
<div class="summary">
<ul class="blockList">
<li class="blockList">
<!-- ======== CONSTRUCTOR SUMMARY ======== -->
<ul class="blockList">
<li class="blockList"><a name="constructor_summary">
<!-- -->
</a>
<h3>Constructor Summary</h3>
<table class="overviewSummary" border="0" cellpadding="3" cellspacing="0" summary="Constructor Summary table, listing constructors, and an explanation">
<caption><span>Constructors</span><span class="tabEnd">&nbsp;</span></caption>
<tr>
<th class="colOne" scope="col">Constructor and Description</th>
</tr>
<tr class="altColor">
<td class="colOne"><code><strong><a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.html#MonotoneChain()">MonotoneChain</a></strong>()</code>
<div class="block">Create a new MonotoneChain instance.</div>
</td>
</tr>
<tr class="rowColor">
<td class="colOne"><code><strong><a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.html#MonotoneChain(boolean)">MonotoneChain</a></strong>(boolean&nbsp;includeCollinearPoints)</code>
<div class="block">Create a new MonotoneChain instance.</div>
</td>
</tr>
<tr class="altColor">
<td class="colOne"><code><strong><a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.html#MonotoneChain(boolean, double)">MonotoneChain</a></strong>(boolean&nbsp;includeCollinearPoints,
double&nbsp;tolerance)</code>
<div class="block">Create a new MonotoneChain instance.</div>
</td>
</tr>
</table>
</li>
</ul>
<!-- ========== METHOD SUMMARY =========== -->
<ul class="blockList">
<li class="blockList"><a name="method_summary">
<!-- -->
</a>
<h3>Method Summary</h3>
<table class="overviewSummary" border="0" cellpadding="3" cellspacing="0" summary="Method Summary table, listing methods, and an explanation">
<caption><span>Methods</span><span class="tabEnd">&nbsp;</span></caption>
<tr>
<th class="colFirst" scope="col">Modifier and Type</th>
<th class="colLast" scope="col">Method and Description</th>
</tr>
<tr class="altColor">
<td class="colFirst"><code><a href="http://docs.oracle.com/javase/6/docs/api/java/util/Collection.html?is-external=true" title="class or interface in java.util">Collection</a>&lt;<a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/Vector2D.html" title="class in org.apache.commons.math3.geometry.euclidean.twod">Vector2D</a>&gt;</code></td>
<td class="colLast"><code><strong><a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.html#findHullVertices(java.util.Collection)">findHullVertices</a></strong>(<a href="http://docs.oracle.com/javase/6/docs/api/java/util/Collection.html?is-external=true" title="class or interface in java.util">Collection</a>&lt;<a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/Vector2D.html" title="class in org.apache.commons.math3.geometry.euclidean.twod">Vector2D</a>&gt;&nbsp;points)</code>
<div class="block">Find the convex hull vertices from the set of input points.</div>
</td>
</tr>
<tr class="rowColor">
<td class="colFirst"><code><a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.html" title="class in org.apache.commons.math3.geometry.euclidean.twod.hull">ConvexHull2D</a></code></td>
<td class="colLast"><code><strong><a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.html#generate(java.util.Collection)">generate</a></strong>(<a href="http://docs.oracle.com/javase/6/docs/api/java/util/Collection.html?is-external=true" title="class or interface in java.util">Collection</a>&lt;<a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/Vector2D.html" title="class in org.apache.commons.math3.geometry.euclidean.twod">Vector2D</a>&gt;&nbsp;points)</code>
<div class="block">Builds the convex hull from the set of input points.</div>
</td>
</tr>
<tr class="altColor">
<td class="colFirst"><code>double</code></td>
<td class="colLast"><code><strong><a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.html#getTolerance()">getTolerance</a></strong>()</code>
<div class="block">Get the tolerance below which points are considered identical.</div>
</td>
</tr>
<tr class="rowColor">
<td class="colFirst"><code>boolean</code></td>
<td class="colLast"><code><strong><a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.html#isIncludeCollinearPoints()">isIncludeCollinearPoints</a></strong>()</code>
<div class="block">Returns if collinear points on the hull will be added as hull vertices.</div>
</td>
</tr>
</table>
<ul class="blockList">
<li class="blockList"><a name="methods_inherited_from_class_java.lang.Object">
<!-- -->
</a>
<h3>Methods inherited from class&nbsp;java.lang.<a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">Object</a></h3>
<code><a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true#clone()" title="class or interface in java.lang">clone</a>, <a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true#equals(java.lang.Object)" title="class or interface in java.lang">equals</a>, <a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true#finalize()" title="class or interface in java.lang">finalize</a>, <a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true#getClass()" title="class or interface in java.lang">getClass</a>, <a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true#hashCode()" title="class or interface in java.lang">hashCode</a>, <a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true#notify()" title="class or interface in java.lang">notify</a>, <a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true#notifyAll()" title="class or interface in java.lang">notifyAll</a>, <a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true#toString()" title="class or interface in java.lang">toString</a>, <a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true#wait()" title="class or interface in java.lang">wait</a>, <a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true#wait(long)" title="class or interface in java.lang">wait</a>, <a href="http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html?is-external=true#wait(long, int)" title="class or interface in java.lang">wait</a></code></li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
<div class="details">
<ul class="blockList">
<li class="blockList">
<!-- ========= CONSTRUCTOR DETAIL ======== -->
<ul class="blockList">
<li class="blockList"><a name="constructor_detail">
<!-- -->
</a>
<h3>Constructor Detail</h3>
<a name="MonotoneChain()">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>MonotoneChain</h4>
<pre>public&nbsp;MonotoneChain()</pre>
<div class="block">Create a new MonotoneChain instance.</div>
</li>
</ul>
<a name="MonotoneChain(boolean)">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>MonotoneChain</h4>
<pre>public&nbsp;MonotoneChain(boolean&nbsp;includeCollinearPoints)</pre>
<div class="block">Create a new MonotoneChain instance.</div>
<dl><dt><span class="strong">Parameters:</span></dt><dd><code>includeCollinearPoints</code> - whether collinear points shall be added as hull vertices</dd></dl>
</li>
</ul>
<a name="MonotoneChain(boolean, double)">
<!-- -->
</a>
<ul class="blockListLast">
<li class="blockList">
<h4>MonotoneChain</h4>
<pre>public&nbsp;MonotoneChain(boolean&nbsp;includeCollinearPoints,
double&nbsp;tolerance)</pre>
<div class="block">Create a new MonotoneChain instance.</div>
<dl><dt><span class="strong">Parameters:</span></dt><dd><code>includeCollinearPoints</code> - whether collinear points shall be added as hull vertices</dd><dd><code>tolerance</code> - tolerance below which points are considered identical</dd></dl>
</li>
</ul>
</li>
</ul>
<!-- ============ METHOD DETAIL ========== -->
<ul class="blockList">
<li class="blockList"><a name="method_detail">
<!-- -->
</a>
<h3>Method Detail</h3>
<a name="findHullVertices(java.util.Collection)">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>findHullVertices</h4>
<pre>public&nbsp;<a href="http://docs.oracle.com/javase/6/docs/api/java/util/Collection.html?is-external=true" title="class or interface in java.util">Collection</a>&lt;<a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/Vector2D.html" title="class in org.apache.commons.math3.geometry.euclidean.twod">Vector2D</a>&gt;&nbsp;findHullVertices(<a href="http://docs.oracle.com/javase/6/docs/api/java/util/Collection.html?is-external=true" title="class or interface in java.util">Collection</a>&lt;<a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/Vector2D.html" title="class in org.apache.commons.math3.geometry.euclidean.twod">Vector2D</a>&gt;&nbsp;points)</pre>
<div class="block">Find the convex hull vertices from the set of input points.</div>
<dl><dt><span class="strong">Parameters:</span></dt><dd><code>points</code> - the set of input points</dd>
<dt><span class="strong">Returns:</span></dt><dd>the convex hull vertices in CCW winding</dd></dl>
</li>
</ul>
<a name="getTolerance()">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>getTolerance</h4>
<pre>public&nbsp;double&nbsp;getTolerance()</pre>
<div class="block">Get the tolerance below which points are considered identical.</div>
<dl><dt><span class="strong">Returns:</span></dt><dd>the tolerance below which points are considered identical</dd></dl>
</li>
</ul>
<a name="isIncludeCollinearPoints()">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>isIncludeCollinearPoints</h4>
<pre>public&nbsp;boolean&nbsp;isIncludeCollinearPoints()</pre>
<div class="block">Returns if collinear points on the hull will be added as hull vertices.</div>
<dl><dt><span class="strong">Returns:</span></dt><dd><code>true</code> if collinear points are added as hull vertices, or <code>false</code>
if only extreme points are present.</dd></dl>
</li>
</ul>
<a name="generate(java.util.Collection)">
<!-- -->
</a>
<ul class="blockListLast">
<li class="blockList">
<h4>generate</h4>
<pre>public&nbsp;<a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.html" title="class in org.apache.commons.math3.geometry.euclidean.twod.hull">ConvexHull2D</a>&nbsp;generate(<a href="http://docs.oracle.com/javase/6/docs/api/java/util/Collection.html?is-external=true" title="class or interface in java.util">Collection</a>&lt;<a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/Vector2D.html" title="class in org.apache.commons.math3.geometry.euclidean.twod">Vector2D</a>&gt;&nbsp;points)
throws <a href="../../../../../../../../org/apache/commons/math3/exception/NullArgumentException.html" title="class in org.apache.commons.math3.exception">NullArgumentException</a>,
<a href="../../../../../../../../org/apache/commons/math3/exception/ConvergenceException.html" title="class in org.apache.commons.math3.exception">ConvergenceException</a></pre>
<div class="block">Builds the convex hull from the set of input points.</div>
<dl>
<dt><strong>Specified by:</strong></dt>
<dd><code><a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2D.html#generate(java.util.Collection)">generate</a></code>&nbsp;in interface&nbsp;<code><a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2D.html" title="interface in org.apache.commons.math3.geometry.euclidean.twod.hull">ConvexHullGenerator2D</a></code></dd>
<dt><strong>Specified by:</strong></dt>
<dd><code><a href="../../../../../../../../org/apache/commons/math3/geometry/hull/ConvexHullGenerator.html#generate(java.util.Collection)">generate</a></code>&nbsp;in interface&nbsp;<code><a href="../../../../../../../../org/apache/commons/math3/geometry/hull/ConvexHullGenerator.html" title="interface in org.apache.commons.math3.geometry.hull">ConvexHullGenerator</a>&lt;<a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/Euclidean2D.html" title="class in org.apache.commons.math3.geometry.euclidean.twod">Euclidean2D</a>,<a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/Vector2D.html" title="class in org.apache.commons.math3.geometry.euclidean.twod">Vector2D</a>&gt;</code></dd>
<dt><span class="strong">Parameters:</span></dt><dd><code>points</code> - the set of input points</dd>
<dt><span class="strong">Returns:</span></dt><dd>the convex hull</dd>
<dt><span class="strong">Throws:</span></dt>
<dd><code><a href="../../../../../../../../org/apache/commons/math3/exception/NullArgumentException.html" title="class in org.apache.commons.math3.exception">NullArgumentException</a></code> - if the input collection is <code>null</code></dd>
<dd><code><a href="../../../../../../../../org/apache/commons/math3/exception/ConvergenceException.html" title="class in org.apache.commons.math3.exception">ConvergenceException</a></code> - if generator fails to generate a convex hull for
the given set of input points</dd></dl>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
</div>
<!-- ========= END OF CLASS DATA ========= -->
<!-- ======= START OF BOTTOM NAVBAR ====== -->
<div class="bottomNav"><a name="navbar_bottom">
<!-- -->
</a><a href="#skip-navbar_bottom" title="Skip navigation links"></a><a name="navbar_bottom_firstrow">
<!-- -->
</a>
<ul class="navList" title="Navigation">
<li><a href="../../../../../../../../overview-summary.html">Overview</a></li>
<li><a href="package-summary.html">Package</a></li>
<li class="navBarCell1Rev">Class</li>
<li><a href="class-use/MonotoneChain.html">Use</a></li>
<li><a href="package-tree.html">Tree</a></li>
<li><a href="../../../../../../../../deprecated-list.html">Deprecated</a></li>
<li><a href="../../../../../../../../index-all.html">Index</a></li>
<li><a href="../../../../../../../../help-doc.html">Help</a></li>
</ul>
<div class="aboutLanguage"><em><script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script></em></div>
</div>
<div class="subNav">
<ul class="navList">
<li><a href="../../../../../../../../org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2D.html" title="interface in org.apache.commons.math3.geometry.euclidean.twod.hull"><span class="strong">Prev Class</span></a></li>
<li>Next Class</li>
</ul>
<ul class="navList">
<li><a href="../../../../../../../../index.html?org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.html" target="_top">Frames</a></li>
<li><a href="MonotoneChain.html" target="_top">No Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_bottom">
<li><a href="../../../../../../../../allclasses-noframe.html">All Classes</a></li>
</ul>
<div>
<script type="text/javascript"><!--
allClassesLink = document.getElementById("allclasses_navbar_bottom");
if(window==top) {
allClassesLink.style.display = "block";
}
else {
allClassesLink.style.display = "none";
}
//-->
</script>
</div>
<div>
<ul class="subNavList">
<li>Summary:&nbsp;</li>
<li>Nested&nbsp;|&nbsp;</li>
<li>Field&nbsp;|&nbsp;</li>
<li><a href="#constructor_summary">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method_summary">Method</a></li>
</ul>
<ul class="subNavList">
<li>Detail:&nbsp;</li>
<li>Field&nbsp;|&nbsp;</li>
<li><a href="#constructor_detail">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method_detail">Method</a></li>
</ul>
</div>
<a name="skip-navbar_bottom">
<!-- -->
</a></div>
<!-- ======== END OF BOTTOM NAVBAR ======= -->
<p class="legalCopy"><small>Copyright &#169; 2003&#x2013;2014 <a href="http://www.apache.org/">The Apache Software Foundation</a>. All rights reserved.</small></p>
</body>
</html>