Convex hull: Difference between revisions
Added Easylang
(Added Easylang) |
|||
(4 intermediate revisions by 3 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,306 ⟶ 3,351:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</
{{out}}
Line 3,313 ⟶ 3,358:
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
Line 3,561 ⟶ 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,567 ⟶ 3,612:
=={{header|Nim}}==
{{trans|Rust}}
<
Point = object
x: float
Line 3,638 ⟶ 3,683:
let hull = calculateConvexHull(points)
for i in hull:
echo i</
{{out}}
<pre>
Line 3,655 ⟶ 3,700:
<
#
# Convex hulls by Andrew's monotone chain algorithm.
Line 3,835 ⟶ 3,880:
every write ((!hull).to_string ())
end</
{{out}}
Line 3,852 ⟶ 3,897:
<
* Convex hulls by Andrew's monotone chain algorithm.
*
Line 4,042 ⟶ 4,087:
;;
(*------------------------------------------------------------------*)</
{{out}}
Line 4,051 ⟶ 4,096:
{{trans|Fortran}}
<
program convex_hull_task (output);
Line 4,375 ⟶ 4,420:
{ local variables: }
{ mode: fundamental }
{ end: }</
{{out}}
Line 4,395 ⟶ 4,440:
=={{header|Perl}}==
{{trans|Raku}}
<
use warnings;
use feature 'say';
Line 4,466 ⟶ 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,475 ⟶ 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,577 ⟶ 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,598 ⟶ 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,611 ⟶ 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,658 ⟶ 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,670 ⟶ 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,733 ⟶ 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,745 ⟶ 4,790:
<
# Convex hulls by Andrew's monotone chain algorithm.
#
Line 5,094 ⟶ 5,139:
write (fmt, '("(", I20, ''("(", F3.0, 1X, F3.0, ") ")'', ")")') n
write (*, fmt) (points(i), i = 0, n - 1)
end</
{{out}}
Line 5,102 ⟶ 5,147:
=={{header|REXX}}==
===version 1===
<
* Compute the Convex Hull for a set of points
* Format of the input file:
Line 5,566 ⟶ 5,611:
Trace ?R
Nop
Exit 12</
{{out}}
<pre> 1 x= -9 yl=-3
Line 5,584 ⟶ 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,858 ⟶ 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,876 ⟶ 5,921:
=={{header|Ruby}}==
{{trans|D}}
<
include Comparable
attr :x, :y
Line 5,942 ⟶ 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,948 ⟶ 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,015 ⟶ 6,060:
return Point {x:x as f32, y:y as f32};
}
</syntaxhighlight>
{{out}}
<pre>
Line 6,029 ⟶ 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,064 ⟶ 6,109:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 6,086 ⟶ 6,131:
<
(export vector-convex-hull)
Line 6,218 ⟶ 6,263:
(write (list-convex-hull example-points))
(newline)</
{{out}}
Line 6,240 ⟶ 6,285:
<
(export convex-hull)
Line 6,332 ⟶ 6,377:
(write (convex-hull example-points))
(newline)</
{{out}}
Line 6,343 ⟶ 6,388:
=={{header|Sidef}}==
{{trans|Raku}}
<
method to_s {
"(#{x}, #{y})"
Line 6,416 ⟶ 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,430 ⟶ 6,475:
<
* Convex hulls by Andrew's monotone chain algorithm.
*
Line 6,721 ⟶ 6,766:
(* sml-indent-level: 2 *)
(* sml-indent-args: 2 *)
(* end: *)</
{{out}}
Line 6,737 ⟶ 6,782:
{{trans|Rust}}
<
public var x: Double
public var y: Double
Line 6,813 ⟶ 6,858:
print("Input: \(points)")
print("Output: \(calculateConvexHull(fromPoints: points))")</
{{out}}
Line 6,824 ⟶ 6,869:
Translation of: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#Python
<
namespace eval test_convex_hull {
Line 6,876 ⟶ 6,921:
puts [convex_hull $tpoints]
}
</syntaxhighlight>
{{out}}
<pre>Test points:
Line 6,885 ⟶ 6,930:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Module Module1
Line 6,976 ⟶ 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,984 ⟶ 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 7,033 ⟶ 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 7,039 ⟶ 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 7,072 ⟶ 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 7,079 ⟶ 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>
|