Convex hull: Difference between revisions
Added Easylang
(Added Easylang) |
|||
| (10 intermediate revisions by 4 users not shown) | |||
Line 13:
{{trans|Nim}}
<
V val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)
I val == 0
Line 71:
V hull = calculateConvexHull(points)
L(i) hull
print(i)</
{{out}}
Line 85:
=={{header|Action!}}==
<
TYPE PointI=[INT x,y]
Line 186:
PrintE("Convex hull:")
PrintPoints(result,rLen)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Convex_hull.png Screenshot from Atari 8-bit computer]
Line 199:
=={{header|Ada}}==
{{trans|D}}
<
with Ada.Containers.Vectors;
Line 286:
Show (Find_Convex_Hull (Vec));
Ada.Text_IO.New_Line;
end Convex_Hull;</
{{out}}
Line 296:
{{trans|Rust}}
<
orientation: function [P Q R][
Line 363:
hull: calculateConvexHull points
loop hull 'i ->
print i</
{{out}}
Line 382:
<
// Convex hulls by Andrew's monotone chain algorithm.
//
Line 948:
}
(*------------------------------------------------------------------*)</
{{out}}
Line 962:
=={{header|C}}==
{{trans|C++}}
<
#include <stdbool.h>
#include <stdio.h>
Line 1,079:
return 0;
}</
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
Line 1,179:
}
}
}</
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
Line 1,185:
=={{header|C++}}==
{{trans|D}}
<
#include <iostream>
#include <ostream>
Line 1,272:
return 0;
}</
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
Line 1,285:
<
#|-*- mode:lisp -*-|#
#|
Line 1,455:
(terpri))
;;; vim: set ft=lisp lisp:</
{{out}}
Line 1,463:
=={{header|D}}==
{{trans|Kotlin}}
<
import std.stdio;
Line 1,527:
auto hull = convexHull(points);
writeln("Convex Hull: ", hull);
}</
{{out}}
<pre>Convex Hull: [(-9,-3), (-3,-9), (19,-8), (17,5), (12,17), (5,19), (-3,15)]</pre>
Line 1,538:
{{libheader| System.Generics.Defaults}}
{{libheader| System.Generics.Collections}}
<syntaxhighlight lang="delphi">
program ConvexHulls;
Line 1,648:
end.
</syntaxhighlight>
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
=={{header|EasyLang}}==
{{trans|Nim}}
<syntaxhighlight>
func orientation p[] q[] r[] .
return (q[2] - p[2]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[2] - q[2])
.
proc calcConvexHull . pts[][] res[][] .
res[][] = [ ]
indMinX = 1
for i to len pts[][]
if pts[i][1] < pts[indMinX][1]
indMinX = i
.
.
p = indMinX
repeat
res[][] &= pts[p][]
q = (p + 1) mod1 len pts[][]
for i to len pts[][]
if orientation pts[p][] pts[i][] pts[q][] < 0
q = i
.
.
p = q
until p = indMinX
.
.
#
pts[][] = [ [ 16 3 ] [ 12 17 ] [ 0 6 ] [ -4 -6 ] [ 16 6 ] [ 16 -7 ] [ 16 -3 ] [ 17 -4 ] [ 5 19 ] [ 19 -8 ] [ 3 16 ] [ 12 13 ] [ 3 -4 ] [ 17 5 ] [ -3 15 ] [ -3 -9 ] [ 0 11 ] [ -9 -3 ] [ -4 -2 ] [ 12 10 ] ]
calcConvexHull pts[][] res[][]
print res[][]
</syntaxhighlight>
{{out}}
<pre>
[
[ -9 -3 ]
[ -3 -9 ]
[ 19 -8 ]
[ 17 5 ]
[ 12 17 ]
[ 5 19 ]
[ -3 15 ]
]
</pre>
=={{header|F_Sharp|F#}}==
{{trans|C}}
<
type Point =
Line 1,701 ⟶ 1,746:
affiche (convexHull (List.sortBy (fun (x : Point) -> x.X, x.Y) poly))
</syntaxhighlight>
{{out}}
<pre>Convex Hull: [(-9,-3), (-3,-9), (19,-8), (17,5), (12,17), (5,19), (-3,15)]</pre>
Line 1,710 ⟶ 1,755:
<
!
! Convex hulls by Andrew's monotone chain algorithm.
Line 1,997 ⟶ 2,042:
write (*, fmt) (points(i), i = 1, n)
end program convex_hull_task</
{{out}}
Line 2,005 ⟶ 2,050:
=={{header|FreeBASIC}}==
<
#include "crt.bi"
Screen 20
Line 2,097 ⟶ 2,142:
Next
Sleep
</syntaxhighlight>
{{out}}
<pre>
Line 2,111 ⟶ 2,156:
=={{header|Go}}==
<
import (
Line 2,173 ⟶ 2,218:
hull := pts.ConvexHull()
fmt.Println("Convex Hull:", hull)
}</
{{out}}
<pre>
Line 2,181 ⟶ 2,226:
=={{header|Groovy}}==
{{trans|Java}}
<
private static class Point implements Comparable<Point> {
private int x, y
Line 2,266 ⟶ 2,311:
println("Convex Hull: $hull")
}
}</
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
=={{header|Haskell}}==
<
import Data.Ord (comparing)
Line 2,331 ⟶ 2,376:
, [-4, -2]
, [12, 10]
]</
{{Out}}
<pre>[-3.0,-9.0]
Line 2,343 ⟶ 2,388:
=={{header|Haxe}}==
{{trans|Nim}}
<
class Main {
Line 2,435 ⟶ 2,480:
Sys.println(']');
}
}</
{{out}}
Line 2,444 ⟶ 2,489:
<
# Convex hulls by Andrew's monotone chain algorithm.
#
Line 2,637 ⟶ 2,682:
end
######################################################################</
{{out}}
Line 2,653 ⟶ 2,698:
Restated from the implementation at [https://web.archive.org/web/20150919194242/http://kukuruku.co/hub/funcprog/introduction-to-j-programming-language-2004] which in turn is Kukuruku Hub's [https://web.archive.org/web/20150908060956/http://kukuruku.co/] translation of Dr. K. L. Metlov's original Russian article [http://dr-klm.livejournal.com/42312.html].
<
crossproduct =: 11 o. [: (* +)/ }. - {.
removeinner =: #~ (1 , (0 > 3 crossproduct\ ]) , 1:)
hull =: [: removeinner^:_ counterclockwise</
Example use:
<
_9j_3 _3j_9 19j_8 17j5 12j17 5j19 _3j15
Line 2,693 ⟶ 2,738:
1 7
0 4
</syntaxhighlight>
=={{header|Java}}==
{{trans|Kotlin}}
<
import java.util.Arrays;
import java.util.List;
Line 2,784 ⟶ 2,829:
System.out.printf("Convex Hull: %s\n", hull);
}
}</
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
=={{header|Javascript}}==
<syntaxhighlight lang="javascript">
function convexHull(points) {
points.sort(comparison);
Line 2,818 ⟶ 2,863:
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
</syntaxhighlight>
'''For usage''':
<nowiki>convexhull.js</nowiki>
<syntaxhighlight lang="javascript">
var points = [];
var hull = [];
Line 2,892 ⟶ 2,937:
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
</syntaxhighlight>
<nowiki>convexhull.html</nowiki>
<
<html>
Line 2,914 ⟶ 2,959:
</html>
</syntaxhighlight>
=={{header|jq}}==
Line 2,920 ⟶ 2,965:
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<
def ccw(a; b; c):
a as [$ax, $ay]
Line 2,941 ⟶ 2,986:
| . + [$pt])
| .[:-1]
end ;</
'''The task'''
<
[16, 3], [12, 17], [ 0, 6], [-4, -6], [16, 6],
[16, -7], [16, -3], [17, -4], [ 5, 19], [19, -8],
Line 2,950 ⟶ 2,995:
];
"Convex Hull: \(pts|convexHull)"</
{{out}}
<pre>
Line 2,958 ⟶ 3,003:
=={{header|Julia}}==
<
# https://github.com/JuliaPolyhedra/Polyhedra.jl/blob/master/examples/operations.ipynb
using Polyhedra, CDDLib
Line 2,966 ⟶ 3,011:
Pch = convexhull(P, P)
removevredundancy!(Pch)
println("$Pch")</
{{out}}
<pre>convexhull([5.0, 19.0], [19.0, -8.0], [17.0, 5.0], [-3.0, 15.0], [-9.0, -3.0], [12.0, 17.0], [-3.0, -9.0])</pre>
Line 2,972 ⟶ 3,017:
=={{header|Kotlin}}==
{{trans|Go}}
<
class Point(val x: Int, val y: Int) : Comparable<Point> {
Line 3,021 ⟶ 3,066:
val hull = convexHull(points)
println("Convex Hull: $hull")
}</
{{out}}
Line 3,056 ⟶ 3,101:
=={{header|Lua}}==
{{trans|C++}}
<
io.write("("..p.x..", "..p.y..")")
return nil
Line 3,125 ⟶ 3,170:
io.write("Convex Hull: ")
print_points(hull)
print()</
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
Line 3,133 ⟶ 3,178:
Function are available in the geometry, ComputationalGeometry and simplex packages.
<
[3,16],[12,13],[3,-4],[17,5],[-3,15],[-3,-9],[0,11],[-9,-3],[-4,-2],[12,10]]:
Line 3,145 ⟶ 3,190:
simplex:-convexhull(pts);
# [[-9, -3], [-3, -9], [19, -8], [17, 5], [12, 17], [5, 19], [-3, 15]]</
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
hullPoints[{{16, 3}, {12, 17}, {0, 6}, {-4, -6}, {16, 6}, {16, -7}, {16, -3}, {17, -4}, {5, 19}, {19, -8}, {3, 16}, {12, 13}, {3, -4}, {17, 5}, {-3, 15}, {-3, -9}, {0, 11}, {-9, -3}, {-4, -2}, {12, 10}}]</
{{out}}{{12., 17.}, {5., 19.}, {19., -8.}, {17., 5.}, {-3., 15.}, {-3., -9.}, {-9., -3.}}
Line 3,157 ⟶ 3,202:
<
:- interface.
Line 3,191 ⟶ 3,236:
:- type point_list == list(point).
:- type point_array == version_array(point).
:- pred point_comes_before(point, point).
Line 3,312 ⟶ 3,351:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</
{{out}}
Line 3,319 ⟶ 3,358:
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
Line 3,567 ⟶ 3,606:
DeleteNode(nodes);
ReadChar
END ConvexHull.</
{{out}}
<pre>[(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
Line 3,573 ⟶ 3,612:
=={{header|Nim}}==
{{trans|Rust}}
<
Point = object
x: float
Line 3,644 ⟶ 3,683:
let hull = calculateConvexHull(points)
for i in hull:
echo i</
{{out}}
<pre>
Line 3,661 ⟶ 3,700:
<
#
# Convex hulls by Andrew's monotone chain algorithm.
Line 3,841 ⟶ 3,880:
every write ((!hull).to_string ())
end</
{{out}}
Line 3,858 ⟶ 3,897:
<
* Convex hulls by Andrew's monotone chain algorithm.
*
Line 4,048 ⟶ 4,087:
;;
(*------------------------------------------------------------------*)</
{{out}}
Line 4,057 ⟶ 4,096:
{{trans|Fortran}}
<
program convex_hull_task (output);
Line 4,381 ⟶ 4,420:
{ local variables: }
{ mode: fundamental }
{ end: }</
{{out}}
Line 4,401 ⟶ 4,440:
=={{header|Perl}}==
{{trans|Raku}}
<
use warnings;
use feature 'say';
Line 4,472 ⟶ 4,511:
$list = join ' ', map { Point::print($_) } @hull_2;
say "Convex Hull (@{[scalar @hull_2]} points): [$list]";
</syntaxhighlight>
{{out}}
<pre>Convex Hull (7 points): [(-3, -9) (19, -8) (17, 5) (12, 17) (5, 19) (-3, 15) (-9, -3)]
Line 4,481 ⟶ 4,520:
{{libheader|Phix/online}}
You can run this online [http://phix.x10.mx/p2js/convexhull.htm here].
<!--<
<span style="color: #000080;font-style:italic;">--
-- demo/rosetta/Convex_hull.exw
Line 4,583 ⟶ 4,622:
<span style="color: #7060A8;">IupClose</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</
{{out}}
<pre>
Line 4,604 ⟶ 4,643:
{{libheader|Shapely}}
An approach that uses the shapely library:
<
from shapely.geometry import MultiPoint
if __name__=="__main__":
pts = MultiPoint([(16,3), (12,17), (0,6), (-4,-6), (16,6), (16,-7), (16,-3), (17,-4), (5,19), (19,-8), (3,16), (12,13), (3,-4), (17,5), (-3,15), (-3,-9), (0,11), (-9,-3), (-4,-2), (12,10)])
print (pts.convex_hull)</
{{out}}
Line 4,617 ⟶ 4,656:
Also an implementation of https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain (therefore kinda {{trans|Go}}
<
(define-type Point (Pair Real Real))
(define-type Points (Listof Point))
Line 4,664 ⟶ 4,703:
'(5 . 19) '(19 . -8) '(3 . 16) '(12 . 13) '(3 . -4) '(17 . 5) '(-3 . 15) '(-3 . -9)
'(0 . 11) '(-9 . -3) '(-4 . -2) '(12 . 10)))
(list '(-9 . -3) '(-3 . -9) '(19 . -8) '(17 . 5) '(12 . 17) '(5 . 19) '(-3 . 15))))</
{{out}}
Line 4,676 ⟶ 4,715:
Modified the angle sort method as the original could fail if there were multiple points on the same y coordinate as the starting point. Sorts on tangent rather than triangle area. Inexpensive since it still doesn't do any trigonometric math, just calculates the ratio of opposite over adjacent.
<syntaxhighlight lang="raku"
has Real $.x is rw;
has Real $.y is rw;
Line 4,739 ⟶ 4,778:
);
say "Convex Hull ({+@hull} points): ", @hull;</
{{out}}
<pre>Convex Hull (7 points): [(-3, -9) (19, -8) (17, 5) (12, 17) (5, 19) (-3, 15) (-9, -3)]
Line 4,751 ⟶ 4,790:
<
# Convex hulls by Andrew's monotone chain algorithm.
#
Line 5,100 ⟶ 5,139:
write (fmt, '("(", I20, ''("(", F3.0, 1X, F3.0, ") ")'', ")")') n
write (*, fmt) (points(i), i = 0, n - 1)
end</
{{out}}
Line 5,108 ⟶ 5,147:
=={{header|REXX}}==
===version 1===
<
* Compute the Convex Hull for a set of points
* Format of the input file:
Line 5,572 ⟶ 5,611:
Trace ?R
Nop
Exit 12</
{{out}}
<pre> 1 x= -9 yl=-3
Line 5,590 ⟶ 5,629:
===version 2===
After learning from https://www.youtube.com/watch?v=wRTGDig3jx8
<
* Compute the Convex Hull for a set of points
* Format of the input file:
Line 5,864 ⟶ 5,903:
*--------------------------------------------------------------------*/
If arg(2)=1 Then say arg(1)
Return lineout(g.0oid,arg(1))</
{{out}}
<pre> 1 x= -9 yl=-3
Line 5,882 ⟶ 5,921:
=={{header|Ruby}}==
{{trans|D}}
<
include Comparable
attr :x, :y
Line 5,948 ⟶ 5,987:
end
main()</
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
Line 5,954 ⟶ 5,993:
=={{header|Rust}}==
Calculates convex hull from list of points (f32, f32). This can be executed entirely in the Rust Playground.
<syntaxhighlight lang="rust">
#[derive(Debug, Clone)]
struct Point {
Line 6,021 ⟶ 6,060:
return Point {x:x as f32, y:y as f32};
}
</syntaxhighlight>
{{out}}
<pre>
Line 6,035 ⟶ 6,074:
=={{header|Scala}}==
Scala Implementation to find Convex hull of given points collection. Functional Paradigm followed
<syntaxhighlight lang="scala">
object convex_hull{
def get_hull(points:List[(Double,Double)], hull:List[(Double,Double)]):List[(Double,Double)] = points match{
Line 6,070 ⟶ 6,109:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 6,092 ⟶ 6,131:
<
(export vector-convex-hull)
Line 6,224 ⟶ 6,263:
(write (list-convex-hull example-points))
(newline)</
{{out}}
Line 6,233 ⟶ 6,272:
<pre>$ csc -O3 -R r7rs convex-hull-task.scm && ./convex-hull-task
((-9 -3) (-3 -9) (19 -8) (17 5) (12 17) (5 19) (-3 15))</pre>
=== A second implementation ===
{{trans|Mercury}}
From the first Scheme implementation, above, I derived an implementation in [[#Standard_ML|Standard ML]]. From that I derived one in [[#Mercury|Mercury]]. Now, starting from that [[#Mercury|Mercury implementation]], I can come back and write a Scheme program more concise than the original.
One could pass these changes along to other languages as well.
If you are using CHICKEN Scheme you will need the '''srfi-1''' egg, in addition to those you needed for the first Scheme implementation.
<syntaxhighlight lang="scheme">(define-library (convex-hulls)
(export convex-hull)
(import (scheme base))
(import (only (srfi 1) fold))
(import (only (srfi 1) append!))
(import (only (srfi 132) list-sort))
(import (only (srfi 132) list-delete-neighbor-dups))
(begin
;;
;; Andrew's monotone chain algorithm for the convex hull in a
;; plane.
;;
;; For a description of the algorithm, see
;; https://en.wikibooks.org/w/index.php?title=Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain&stableid=4016938
;;
(define x@ car)
(define y@ cadr)
(define (cross u v)
;; Cross product (as a signed scalar).
(- (* (x@ u) (y@ v)) (* (y@ u) (x@ v))))
(define (point- u v)
(list (- (x@ u) (x@ v)) (- (y@ u) (y@ v))))
(define (point=? u v)
(and (= (x@ u) (x@ v)) (= (y@ u) (y@ v))))
(define (point<? u v)
(let ((xu (x@ u))
(xv (x@ v)))
(or (< xu xv) (and (= xu xv) (< (y@ u) (y@ v))))))
(define (convex-hull points-list)
(let* ((points (list-delete-neighbor-dups
point=? (list-sort point<? points-list)))
(n (length points)))
(cond
((<= n 2) points)
(else
(let ((half-hull (make-vector n)))
(define (cross-test pt j)
(or (zero? j)
(let ((elem-j (vector-ref half-hull j))
(elem-j1 (vector-ref half-hull (- j 1))))
(positive? (cross (point- elem-j elem-j1)
(point- pt elem-j1))))))
(define (construct-half-hull points)
(vector-set! half-hull 0 (car points))
(vector-set! half-hull 1 (cadr points))
(fold (lambda (pt j)
(let loop ((j j))
(if (cross-test pt j)
(let ((j1 (+ j 1)))
(vector-set! half-hull j1 pt)
j1)
(loop (- j 1)))))
1 (cddr points)))
(let* ((lower-hull
;; Leave out the last point, which is the same
;; as the first point of the upper hull.
(let ((j (construct-half-hull points)))
(vector->list half-hull 0 j)))
(upper-hull
;; Leave out the last point, which is the same
;; as the first point of the lower hull.
(let ((j (construct-half-hull (reverse points))))
(vector->list half-hull 0 j))))
(append! lower-hull upper-hull)))))))
)) ;; end of library convex-hulls.
;;
;; A demonstration.
;;
(import (scheme base))
(import (scheme write))
(import (convex-hulls))
(define example-points
'((16 3) (12 17) (0 6) (-4 -6) (16 6)
(16 -7) (16 -3) (17 -4) (5 19) (19 -8)
(3 16) (12 13) (3 -4) (17 5) (-3 15)
(-3 -9) (0 11) (-9 -3) (-4 -2) (12 10)))
(write (convex-hull example-points))
(newline)</syntaxhighlight>
{{out}}
<pre>$ gosh convex-hull-task-2.scm
((-9 -3) (-3 -9) (19 -8) (17 5) (12 17) (5 19) (-3 15))</pre>
Footnote: My Mercury implementation originally had a "fold" in it, the way this Scheme program does, but that got lost during debugging. (The bug turned out to be elsewhere.) The fold and inner loop became one loop that I think is easier to understand. However, here I wanted to show it could be done with a fold.
=={{header|Sidef}}==
{{trans|Raku}}
<
method to_s {
"(#{x}, #{y})"
Line 6,309 ⟶ 6,461:
[-3,15], [-3,-9], [ 0,11], [-9,-3], [-4,-2], [12,10], [14,-9], [1,-9])
say("Convex Hull (#{hull.len} points): ", hull.join(" "))</
{{out}}
<pre>
Line 6,323 ⟶ 6,475:
<
* Convex hulls by Andrew's monotone chain algorithm.
*
Line 6,614 ⟶ 6,766:
(* sml-indent-level: 2 *)
(* sml-indent-args: 2 *)
(* end: *)</
{{out}}
Line 6,630 ⟶ 6,782:
{{trans|Rust}}
<
public var x: Double
public var y: Double
Line 6,706 ⟶ 6,858:
print("Input: \(points)")
print("Output: \(calculateConvexHull(fromPoints: points))")</
{{out}}
Line 6,717 ⟶ 6,869:
Translation of: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#Python
<
namespace eval test_convex_hull {
Line 6,769 ⟶ 6,921:
puts [convex_hull $tpoints]
}
</syntaxhighlight>
{{out}}
<pre>Test points:
Line 6,778 ⟶ 6,930:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Module Module1
Line 6,869 ⟶ 7,021:
End Sub
End Module</
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
Line 6,877 ⟶ 7,029:
{{libheader|Wren-sort}}
{{libheader|Wren-trait}}
{{libheader|Wren-iterate}}
<syntaxhighlight lang="wren">import "./
import "./trait" for Comparable
import "./iterate" for Stepped
class Point is Comparable {
Line 6,926 ⟶ 7,080:
Point.new(-3, -9), Point.new( 0, 11), Point.new(-9, -3), Point.new(-4, -2), Point.new(12, 10)
]
System.print("Convex Hull: %(convexHull.call(pts))")</
{{out}}
Line 6,932 ⟶ 7,086:
Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">func real CosAng(A, B); \Return cosine of angle between vectors A and B
int A, B; \Cos(Ang) = DotProd / (|A|*|B|)
real DotProd, Magnitude;
[DotProd:= float( A(0)*B(0) + A(1)*B(1));
Magnitude:= sqrt(float( sq(B(0)-A(0)) + sq(B(1)-A(1)) ));
return DotProd / Magnitude;
];
proc ConvexHull(N, P);
int N, P;
int Min, I, HullI, EndI, A(2), B(2), J, SJ;
real Ang, MinAng;
[Min:= -1>>1; \find index of point with smallest X coordinate
for I:= 0 to N-1 do
if P(I,0) < Min then
[Min:= P(I,0); HullI:= I];
EndI:= HullI;
A(0):= 0; A(1):= -1;
repeat ChOut(0, ^();
IntOut(0, P(HullI,0)); ChOut(0, ^,); IntOut(0, P(HullI,1));
ChOut(0, ^));
MinAng:= -1e12; \find index of point with smallest diverting angle
for J:= 0 to N-1 do
[B(0):= P(J,0) - P(HullI,0); B(1):= P(J,1) - P(HullI,1);
Ang:= CosAng(A, B);
if Ang > MinAng and J # HullI then
[MinAng:= Ang; SJ:= J];
];
A(0):= P(SJ,0) - P(HullI,0); A(1):= P(SJ,1) - P(HullI,1);
HullI:= SJ;
if HullI # EndI then Text(0, ", ");
until HullI = EndI;
];
ConvexHull(20, [[16,3], [12,17], [0,6], [-4,-6], [16,6], [16,-7], [16,-3],
[17,-4], [5,19], [19,-8], [3,16], [12,13], [3,-4], [17,5],
[-3,15], [-3,-9], [0,11], [-9,-3], [-4,-2], [12,10]])
</syntaxhighlight>
{{out}}
<pre>
(-9,-3), (-3,-9), (19,-8), (17,5), (12,17), (5,19), (-3,15)</pre>
=={{header|zkl}}==
<
// https://en.wikipedia.org/wiki/Graham_scan, O(n log n)
// http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
Line 6,965 ⟶ 7,163:
fcn ccw(a,b,c){ // a,b,c are points: (x,y)
((b[0] - a[0])*(c[1] - a[1])) - ((b[1] - a[1])*(c[0] - a[0]))
}</
<
T(16, -7), T(16,-3),T(17,-4), T(5,19), T(19,-8),
T(3,16), T(12,13), T(3,-4), T(17,5), T(-3,15),
Line 6,972 ⟶ 7,170:
.apply(fcn(xy){ xy.apply("toFloat") }).copy();
hull:=grahamScan(pts);
println("Convex Hull (%d points): %s".fmt(hull.len(),hull.toString(*)));</
{{out}}
<pre>
| |||