https://aplwiki.com/index.php?title=Convex_Hull&feed=atom&action=history
Convex Hull - Revision history
2024-03-29T14:58:52Z
Revision history for this page on the wiki
MediaWiki 1.38.2
https://aplwiki.com/index.php?title=Convex_Hull&diff=9541&oldid=prev
Adám Brudzewsky: Text replacement - "<source" to "<syntaxhighlight"
2022-09-10T22:19:57Z
<p>Text replacement - "<source" to "<syntaxhighlight"</p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en-GB">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 22:19, 10 September 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l35">Line 35:</td>
<td colspan="2" class="diff-lineno">Line 35:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Code ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Code ==</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><<del style="font-weight: bold; text-decoration: none;">source </del>lang="apl"></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><<ins style="font-weight: bold; text-decoration: none;">syntaxhighlight </ins>lang="apl"></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>ConvexHull←{</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>ConvexHull←{</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>⍝ ⍵: matrix (2 rows) of points - first row:abscissae second row:ordinates</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>⍝ ⍵: matrix (2 rows) of points - first row:abscissae second row:ordinates</div></td></tr>
</table>
Adám Brudzewsky
https://aplwiki.com/index.php?title=Convex_Hull&diff=9412&oldid=prev
Adám Brudzewsky: Text replacement - "</source>" to "</syntaxhighlight>"
2022-09-10T22:07:21Z
<p>Text replacement - "</source>" to "</syntaxhighlight>"</p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en-GB">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 22:07, 10 September 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l64">Line 64:</td>
<td colspan="2" class="diff-lineno">Line 64:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> (⊂ixHull)⌷[1]pts</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> (⊂ixHull)⌷[1]pts</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div></<del style="font-weight: bold; text-decoration: none;">source</del>></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></<ins style="font-weight: bold; text-decoration: none;">syntaxhighlight</ins>></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Examples]][[Category:Dyalog APL examples]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Examples]][[Category:Dyalog APL examples]]</div></td></tr>
</table>
Adám Brudzewsky
https://aplwiki.com/index.php?title=Convex_Hull&diff=4108&oldid=prev
Marshall: Text replacement - "Category:Dyalog APL" to "Category:Dyalog APL examples"
2020-05-04T09:48:59Z
<p>Text replacement - "<a href="/wiki/Category:Dyalog_APL" title="Category:Dyalog APL">Category:Dyalog APL</a>" to "<a href="/wiki/Category:Dyalog_APL_examples" title="Category:Dyalog APL examples">Category:Dyalog APL examples</a>"</p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en-GB">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 09:48, 4 May 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l66">Line 66:</td>
<td colspan="2" class="diff-lineno">Line 66:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></source></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></source></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Examples]][[Category:Dyalog APL]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Examples]][[Category:Dyalog APL <ins style="font-weight: bold; text-decoration: none;">examples</ins>]]</div></td></tr>
</table>
Marshall
https://aplwiki.com/index.php?title=Convex_Hull&diff=4060&oldid=prev
Marshall: Text replacement - "\[\[Category:(Essays|Examples|Tutorials)\]\]" to "Category:$1Category:Dyalog APL"
2020-05-04T09:26:58Z
<p>Text replacement - "\[\[Category:(Essays|Examples|Tutorials)\]\]" to "<a href="/index.php?title=Category:$1&action=edit&redlink=1" class="new" title="Category:$1 (page does not exist)">Category:$1</a><a href="/wiki/Category:Dyalog_APL" title="Category:Dyalog APL">Category:Dyalog APL</a>"</p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en-GB">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 09:26, 4 May 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l66">Line 66:</td>
<td colspan="2" class="diff-lineno">Line 66:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></source></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></source></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Examples]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Examples<ins style="font-weight: bold; text-decoration: none;">]][[Category:Dyalog APL</ins>]]</div></td></tr>
</table>
Marshall
https://aplwiki.com/index.php?title=Convex_Hull&diff=3599&oldid=prev
Marshall: Examples category
2020-04-30T13:10:51Z
<p>Examples category</p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en-GB">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 13:10, 30 April 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l65">Line 65:</td>
<td colspan="2" class="diff-lineno">Line 65:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></source></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></source></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Category:Examples]]</ins></div></td></tr>
</table>
Marshall
https://aplwiki.com/index.php?title=Convex_Hull&diff=1957&oldid=prev
RichPark: 1 revision imported
2019-11-21T09:39:36Z
<p>1 revision imported</p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<tr class="diff-title" lang="en-GB">
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 09:39, 21 November 2019</td>
</tr><tr><td colspan="2" class="diff-notice" lang="en-GB"><div class="mw-diff-empty">(No difference)</div>
</td></tr></table>
RichPark
https://aplwiki.com/index.php?title=Convex_Hull&diff=1956&oldid=prev
Miraheze>Adám Brudzewsky at 16:20, 18 November 2019
2019-11-18T16:20:47Z
<p></p>
<p><b>New page</b></p><div>The problem of finding convex hulls finds its practical applications in [[wikipedia:pattern recognition|pattern recognition]], [[wikipedia:digital image processing|digital image processing]], [[wikipedia:statistics|statistics]] and [[wikipedia:geographic information systems|geographic information systems]]. It also serves as a tool, a building block for a number of other computational-geometric algorithms. This page describes and implements an algorithm for computing a convex hull in R<sup>2</sup>.<br />
<br />
== Introduction ==<br />
<br />
In a Euclidean Space the Convex Hull of a set '''''I''''' is defined as the intersection of all convex sets containing '''''I'''''.<br />
<br />
For ''planar objects'', i.e., lying in the plane R<sup>2</sup>, the convex hull may be easily visualized by imagining an elastic band stretched open to encompass the given object; when released, it will assume the shape of the required convex hull.<br />
<br />
[[File:ConvexHull.svg|thumb|right]]<br />
=== Graphical example ===<br />
If the set '''''I''''' is a set of points in R<sup>2</sup>, then the convex hull is the smallest convex polygon which encloses '''''I'''''.<br />
<br />
== Gift wrapping algorithm ==<br />
Many convex hull algorithms had been proposed for finding the points lying on the convex polygon.<br />
<br />
Here a [[dfn]] is presented that implements a gift wrapping algorithm.<br />
<br />
It follows a suggestion from [mailto:Lars.Strand@skogoglandskap.no Lars Strand], written in an email to [mailto:programming@jsoftware.com programming@jsoftware.com] at Jan 11, 2008.<br />
<br />
A number of points in R<sup>2</sup> are given. The problem is to determine the smallest convex region which includes all of the points.<br />
<br />
The solution starts with the point '''p0''' having the smallest x-value. The next point '''p1''' will be the point which together with the first point defines a line having the smallest angle to the x-axis. Using this point '''p1''' as vertex, the task is to find a third point '''p2''' so that a line from the vertex has the largest angle to the line '''p0-p1'''.<br />
<br />
Three points in the solution are now determined.<br />
<br />
The procedure is repeated after a shift of '''p1''' to '''p0''', '''p2''' to '''p1''', and a new point '''p2''' is found in the same way.<br />
<br />
The procedure stops when the new point '''p2''' is the same as the starting point.<br />
<br />
The solution contains the coordinates of the points of the hull.<br />
<br />
This dfn calls another dfn for computing the polar phase of all points with respect of a previously chosen point lying on the hull.<br />
<br />
The iteration is implemented by means of primitive [[power operator]].<br />
<br />
== Code ==<br />
<source lang="apl"><br />
ConvexHull←{<br />
⍝ ⍵: matrix (2 rows) of points - first row:abscissae second row:ordinates<br />
⍝ return: matrix (2 rows) of points of convex hull<br />
<br />
⍝ try: ConvexHull ⍉9 2⍴1 0,1 ¯10,3 3,2 1,6 3,1 6,3 1,6 1,9 0<br />
⍝<br />
⎕IO←0<br />
pts←(⊂⍋⊃↓⍵)⌷[1]⍵ ⍝sort by x-values:first point←→start vertex<br />
phs←{ ⍝ 12○⍵ polar phase ○¯1>≥○1. see DFNS<br />
x y←⊂[1↓⍳⍴⍴⍵]⍵ ⍝ x and y coordinates.<br />
x0 xn←1 0=⊂0=x ⍝ points on/off y axis.<br />
top←(x0×○0.5)+xnׯ3○(|y)÷x+x0 ⍝ upper quadrants.<br />
(0∨.≠⍵)×(1-2×y<0)×top+○x<0 ⍝ other quadrants.<br />
}<br />
angles←phs(0 1↓pts)-[0]0⌷[1]pts ⍝phases(radians) of the vectors<br />
ixStart←0,1+⊃angles⍳⌊/angles ⍝start with indexes of first segment<br />
ixHull←{<br />
ix0 ix1←¯2↑⍵ ⍝ix1: index of last point←→last vertex<br />
v←{⍵+(⍵<0)×○2}phs pts-[0]ix1⌷[1]pts ⍝phases with respect to the last vertex<br />
other←(⍳1↓⍴pts)~ix0 ix1 ⍝indexes of other points<br />
angles←|(ix0⊃v)-(⊂other)⌷v ⍝ _______/\_______<br />
angles←{f←⍵>○1 ⋄ (⍵×~f)+f×-⍵-○2}angles ⍝angles (p0-p1) (p1-px)<br />
⍵,(angles⍳⌈/angles)⊃other ⍝new vertex is where angle is largest<br />
}⍣{<br />
0=⊃⌽⍺ ⍝repeat until first and last vertex coincide<br />
}ixStart<br />
(⊂ixHull)⌷[1]pts<br />
}<br />
</source></div>
Miraheze>Adám Brudzewsky