Rosetta Code

Convex hull: Difference between revisions

Page Discussion

Convex hull (view source)

Revision as of 22:17, 26 August 2022

1,715 bytes added ,  1 year ago
m
syntax highlighting fixup automation
m (syntax highlighting fixup automation)
Line 13:
{{trans|Nim}}
 
<langsyntaxhighlight lang="11l">F orientation(p, q, r)
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)</langsyntaxhighlight>
 
{{out}}
Line 85:
 
=={{header|Action!}}==
<langsyntaxhighlight Actionlang="action!">DEFINE POINTSIZE="4"
TYPE PointI=[INT x,y]
 
Line 186:
PrintE("Convex hull:")
PrintPoints(result,rLen)
RETURN</langsyntaxhighlight>
{{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}}
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO;
with Ada.Containers.Vectors;
 
Line 286:
Show (Find_Convex_Hull (Vec));
Ada.Text_IO.New_Line;
end Convex_Hull;</langsyntaxhighlight>
 
{{out}}
Line 296:
{{trans|Rust}}
 
<langsyntaxhighlight lang="rebol">define :point [x y][]
 
orientation: function [P Q R][
Line 363:
hull: calculateConvexHull points
loop hull 'i ->
print i</langsyntaxhighlight>
 
{{out}}
Line 382:
 
 
<langsyntaxhighlight lang="ats">//
// Convex hulls by Andrew's monotone chain algorithm.
//
Line 948:
}
 
(*------------------------------------------------------------------*)</langsyntaxhighlight>
 
{{out}}
Line 962:
=={{header|C}}==
{{trans|C++}}
<langsyntaxhighlight Clang="c">#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
Line 1,079:
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
 
=={{header|C sharp|C#}}==
<langsyntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
 
Line 1,179:
}
}
}</langsyntaxhighlight>
{{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}}
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <ostream>
Line 1,272:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
Line 1,285:
 
 
<langsyntaxhighlight lang="lisp">#!/bin/sh
#|-*- mode:lisp -*-|#
#|
Line 1,455:
(terpri))
 
;;; vim: set ft=lisp lisp:</langsyntaxhighlight>
 
{{out}}
Line 1,463:
=={{header|D}}==
{{trans|Kotlin}}
<langsyntaxhighlight Dlang="d">import std.algorithm.sorting;
import std.stdio;
 
Line 1,527:
auto hull = convexHull(points);
writeln("Convex Hull: ", hull);
}</langsyntaxhighlight>
{{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">
<lang Delphi>
program ConvexHulls;
 
Line 1,648:
 
end.
</syntaxhighlight>
</lang>
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
Line 1,654:
=={{header|F_Sharp|F#}}==
{{trans|C}}
<langsyntaxhighlight Flang="f#">open System
 
type Point =
Line 1,701:
affiche (convexHull (List.sortBy (fun (x : Point) -> x.X, x.Y) poly))
 
</syntaxhighlight>
</lang>
{{out}}
<pre>Convex Hull: [(-9,-3), (-3,-9), (19,-8), (17,5), (12,17), (5,19), (-3,15)]</pre>
Line 1,710:
 
 
<langsyntaxhighlight lang="fortran">module convex_hulls
!
! Convex hulls by Andrew's monotone chain algorithm.
Line 1,997:
write (*, fmt) (points(i), i = 1, n)
 
end program convex_hull_task</langsyntaxhighlight>
 
{{out}}
Line 2,005:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">
#include "crt.bi"
Screen 20
Line 2,097:
Next
Sleep
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,111:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
Line 2,173:
hull := pts.ConvexHull()
fmt.Println("Convex Hull:", hull)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 2,181:
=={{header|Groovy}}==
{{trans|Java}}
<langsyntaxhighlight lang="groovy">class ConvexHull {
private static class Point implements Comparable<Point> {
private int x, y
Line 2,266:
println("Convex Hull: $hull")
}
}</langsyntaxhighlight>
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
 
=={{header|Haskell}}==
<langsyntaxhighlight Haskelllang="haskell">import Data.List (sortBy, groupBy, maximumBy)
import Data.Ord (comparing)
 
Line 2,331:
, [-4, -2]
, [12, 10]
]</langsyntaxhighlight>
{{Out}}
<pre>[-3.0,-9.0]
Line 2,343:
=={{header|Haxe}}==
{{trans|Nim}}
<langsyntaxhighlight lang="haxe">typedef Point = {x:Float, y:Float};
 
class Main {
Line 2,435:
Sys.println(']');
}
}</langsyntaxhighlight>
 
{{out}}
Line 2,444:
 
 
<langsyntaxhighlight lang="icon">#
# Convex hulls by Andrew's monotone chain algorithm.
#
Line 2,637:
end
 
######################################################################</langsyntaxhighlight>
 
{{out}}
Line 2,653:
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].
 
<langsyntaxhighlight Jlang="j">counterclockwise =: ({. , }. /: 12 o. }. - {.) @ /:~
crossproduct =: 11 o. [: (* +)/ }. - {.
removeinner =: #~ (1 , (0 > 3 crossproduct\ ]) , 1:)
hull =: [: removeinner^:_ counterclockwise</langsyntaxhighlight>
 
Example use:
 
<langsyntaxhighlight Jlang="j"> hull 16j3 12j17 0j6 _4j_6 16j6 16j_7 16j_3 17j_4 5j19 19j_8 3j16 12j13 3j_4 17j5 _3j15 _3j_9 0j11 _9j_3 _4j_2 12j10
_9j_3 _3j_9 19j_8 17j5 12j17 5j19 _3j15
 
Line 2,693:
1 7
0 4
</syntaxhighlight>
</lang>
 
=={{header|Java}}==
{{trans|Kotlin}}
<langsyntaxhighlight Javalang="java">import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
Line 2,784:
System.out.printf("Convex Hull: %s\n", hull);
}
}</langsyntaxhighlight>
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
 
=={{header|Javascript}}==
<syntaxhighlight lang="javascript">
<lang Javascript>
function convexHull(points) {
points.sort(comparison);
Line 2,818:
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
</syntaxhighlight>
</lang>
 
'''For usage''':
<nowiki>convexhull.js</nowiki>
<syntaxhighlight lang="javascript">
<lang Javascript>
var points = [];
var hull = [];
Line 2,892:
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
</syntaxhighlight>
</lang>
 
<nowiki>convexhull.html</nowiki>
<langsyntaxhighlight lang="html">
<html>
 
Line 2,914:
 
</html>
</syntaxhighlight>
</lang>
 
=={{header|jq}}==
Line 2,920:
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<langsyntaxhighlight lang="jq"># ccw returns true if the three points make a counter-clockwise turn
def ccw(a; b; c):
a as [$ax, $ay]
Line 2,941:
| . + [$pt])
| .[:-1]
end ;</langsyntaxhighlight>
'''The task'''
<langsyntaxhighlight lang="jq">def pts: [
[16, 3], [12, 17], [ 0, 6], [-4, -6], [16, 6],
[16, -7], [16, -3], [17, -4], [ 5, 19], [19, -8],
Line 2,950:
];
 
"Convex Hull: \(pts|convexHull)"</langsyntaxhighlight>
{{out}}
<pre>
Line 2,958:
 
=={{header|Julia}}==
<langsyntaxhighlight Julialang="julia"># v1.0.4
# https://github.com/JuliaPolyhedra/Polyhedra.jl/blob/master/examples/operations.ipynb
using Polyhedra, CDDLib
Line 2,966:
Pch = convexhull(P, P)
removevredundancy!(Pch)
println("$Pch")</langsyntaxhighlight>
{{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:
=={{header|Kotlin}}==
{{trans|Go}}
<langsyntaxhighlight lang="scala">// version 1.1.3
 
class Point(val x: Int, val y: Int) : Comparable<Point> {
Line 3,021:
val hull = convexHull(points)
println("Convex Hull: $hull")
}</langsyntaxhighlight>
 
{{out}}
Line 3,056:
=={{header|Lua}}==
{{trans|C++}}
<langsyntaxhighlight lang="lua">function print_point(p)
io.write("("..p.x..", "..p.y..")")
return nil
Line 3,125:
io.write("Convex Hull: ")
print_points(hull)
print()</langsyntaxhighlight>
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
Line 3,133:
Function are available in the geometry, ComputationalGeometry and simplex packages.
 
<langsyntaxhighlight lang="maple">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]]:
 
Line 3,145:
 
simplex:-convexhull(pts);
# [[-9, -3], [-3, -9], [19, -8], [17, 5], [12, 17], [5, 19], [-3, 15]]</langsyntaxhighlight>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">hullPoints[data_] := MeshCoordinates[ConvexHullMesh[data]];
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}}]</langsyntaxhighlight>
{{out}}{{12., 17.}, {5., 19.}, {19., -8.}, {17., 5.}, {-3., 15.}, {-3., -9.}, {-9., -3.}}
 
Line 3,157:
 
 
<langsyntaxhighlight lang="mercury">:- module convex_hull_task.
 
:- interface.
Line 3,306:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</langsyntaxhighlight>
 
{{out}}
Line 3,313:
 
=={{header|Modula-2}}==
<langsyntaxhighlight lang="modula2">MODULE ConvexHull;
FROM FormatString IMPORT FormatString;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
Line 3,561:
DeleteNode(nodes);
ReadChar
END ConvexHull.</langsyntaxhighlight>
{{out}}
<pre>[(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
Line 3,567:
=={{header|Nim}}==
{{trans|Rust}}
<langsyntaxhighlight lang="nim">type
Point = object
x: float
Line 3,638:
let hull = calculateConvexHull(points)
for i in hull:
echo i</langsyntaxhighlight>
{{out}}
<pre>
Line 3,655:
 
 
<langsyntaxhighlight lang="objecticon"># -*- ObjectIcon -*-
#
# Convex hulls by Andrew's monotone chain algorithm.
Line 3,835:
 
every write ((!hull).to_string ())
end</langsyntaxhighlight>
 
{{out}}
Line 3,852:
 
 
<langsyntaxhighlight lang="ocaml">(*
* Convex hulls by Andrew's monotone chain algorithm.
*
Line 4,042:
;;
 
(*------------------------------------------------------------------*)</langsyntaxhighlight>
 
{{out}}
Line 4,051:
{{trans|Fortran}}
 
<langsyntaxhighlight lang="pascal">{$mode ISO}
 
program convex_hull_task (output);
Line 4,375:
{ local variables: }
{ mode: fundamental }
{ end: }</langsyntaxhighlight>
 
{{out}}
Line 4,395:
=={{header|Perl}}==
{{trans|Raku}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
Line 4,466:
$list = join ' ', map { Point::print($_) } @hull_2;
say "Convex Hull (@{[scalar @hull_2]} points): [$list]";
</syntaxhighlight>
</lang>
{{out}}
<pre>Convex Hull (7 points): [(-3, -9) (19, -8) (17, 5) (12, 17) (5, 19) (-3, 15) (-9, -3)]
Line 4,475:
{{libheader|Phix/online}}
You can run this online [http://phix.x10.mx/p2js/convexhull.htm here].
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">--
-- demo/rosetta/Convex_hull.exw
Line 4,577:
<span style="color: #7060A8;">IupClose</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 4,598:
{{libheader|Shapely}}
An approach that uses the shapely library:
<langsyntaxhighlight lang="python">from __future__ import print_function
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)</langsyntaxhighlight>
 
{{out}}
Line 4,611:
Also an implementation of https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain (therefore kinda {{trans|Go}}
 
<langsyntaxhighlight lang="racket">#lang typed/racket
(define-type Point (Pair Real Real))
(define-type Points (Listof Point))
Line 4,658:
'(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))))</langsyntaxhighlight>
 
{{out}}
Line 4,670:
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" perl6line>class Point {
has Real $.x is rw;
has Real $.y is rw;
Line 4,733:
);
 
say "Convex Hull ({+@hull} points): ", @hull;</langsyntaxhighlight>
{{out}}
<pre>Convex Hull (7 points): [(-3, -9) (19, -8) (17, 5) (12, 17) (5, 19) (-3, 15) (-9, -3)]
Line 4,745:
 
 
<langsyntaxhighlight lang="ratfor">#
# Convex hulls by Andrew's monotone chain algorithm.
#
Line 5,094:
write (fmt, '("(", I20, ''("(", F3.0, 1X, F3.0, ") ")'', ")")') n
write (*, fmt) (points(i), i = 0, n - 1)
end</langsyntaxhighlight>
 
{{out}}
Line 5,102:
=={{header|REXX}}==
===version 1===
<langsyntaxhighlight lang="rexx">/* REXX ---------------------------------------------------------------
* Compute the Convex Hull for a set of points
* Format of the input file:
Line 5,566:
Trace ?R
Nop
Exit 12</langsyntaxhighlight>
{{out}}
<pre> 1 x= -9 yl=-3
Line 5,584:
===version 2===
After learning from https://www.youtube.com/watch?v=wRTGDig3jx8
<langsyntaxhighlight lang="rexx">/* REXX ---------------------------------------------------------------
* Compute the Convex Hull for a set of points
* Format of the input file:
Line 5,858:
*--------------------------------------------------------------------*/
If arg(2)=1 Then say arg(1)
Return lineout(g.0oid,arg(1))</langsyntaxhighlight>
{{out}}
<pre> 1 x= -9 yl=-3
Line 5,876:
=={{header|Ruby}}==
{{trans|D}}
<langsyntaxhighlight lang="ruby">class Point
include Comparable
attr :x, :y
Line 5,942:
end
 
main()</langsyntaxhighlight>
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
Line 5,948:
=={{header|Rust}}==
Calculates convex hull from list of points (f32, f32). This can be executed entirely in the Rust Playground.
<syntaxhighlight lang="rust">
<lang Rust>
#[derive(Debug, Clone)]
struct Point {
Line 6,015:
return Point {x:x as f32, y:y as f32};
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 6,029:
=={{header|Scala}}==
Scala Implementation to find Convex hull of given points collection. Functional Paradigm followed
<syntaxhighlight lang="scala">
<lang Scala>
object convex_hull{
def get_hull(points:List[(Double,Double)], hull:List[(Double,Double)]):List[(Double,Double)] = points match{
Line 6,064:
}
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 6,086:
 
 
<langsyntaxhighlight lang="scheme">(define-library (convex-hulls)
 
(export vector-convex-hull)
Line 6,218:
 
(write (list-convex-hull example-points))
(newline)</langsyntaxhighlight>
 
{{out}}
Line 6,240:
 
 
<langsyntaxhighlight lang="scheme">(define-library (convex-hulls)
 
(export convex-hull)
Line 6,332:
 
(write (convex-hull example-points))
(newline)</langsyntaxhighlight>
 
{{out}}
Line 6,343:
=={{header|Sidef}}==
{{trans|Raku}}
<langsyntaxhighlight lang="ruby">class Point(Number x, Number y) {
method to_s {
"(#{x}, #{y})"
Line 6,416:
[-3,15], [-3,-9], [ 0,11], [-9,-3], [-4,-2], [12,10], [14,-9], [1,-9])
 
say("Convex Hull (#{hull.len} points): ", hull.join(" "))</langsyntaxhighlight>
{{out}}
<pre>
Line 6,430:
 
 
<langsyntaxhighlight lang="sml">(*
* Convex hulls by Andrew's monotone chain algorithm.
*
Line 6,721:
(* sml-indent-level: 2 *)
(* sml-indent-args: 2 *)
(* end: *)</langsyntaxhighlight>
 
{{out}}
Line 6,737:
{{trans|Rust}}
 
<langsyntaxhighlight lang="swift">public struct Point: Equatable, Hashable {
public var x: Double
public var y: Double
Line 6,813:
 
print("Input: \(points)")
print("Output: \(calculateConvexHull(fromPoints: points))")</langsyntaxhighlight>
 
{{out}}
Line 6,824:
Translation of: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#Python
 
<langsyntaxhighlight lang="tcl">catch {namespace delete test_convex_hull} ;# Start with a clean namespace
 
namespace eval test_convex_hull {
Line 6,876:
puts [convex_hull $tpoints]
}
</syntaxhighlight>
</lang>
{{out}}
<pre>Test points:
Line 6,885:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Imports ConvexHull
 
Module Module1
Line 6,976:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
Line 6,984:
{{libheader|Wren-sort}}
{{libheader|Wren-trait}}
<langsyntaxhighlight lang="ecmascript">import "/sort" for Sort
import "/trait" for Comparable, Stepped
 
Line 7,033:
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))")</langsyntaxhighlight>
 
{{out}}
Line 7,041:
 
=={{header|zkl}}==
<langsyntaxhighlight lang="zkl">// Use Graham Scan to sort points into a convex hull
// https://en.wikipedia.org/wiki/Graham_scan, O(n log n)
// http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
Line 7,072:
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]))
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">pts:=List( T(16,3), T(12,17), T(0,6), T(-4,-6), T(16,6),
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:
.apply(fcn(xy){ xy.apply("toFloat") }).copy();
hull:=grahamScan(pts);
println("Convex Hull (%d points): %s".fmt(hull.len(),hull.toString(*)));</langsyntaxhighlight>
{{out}}
<pre>
Thundergnat
10,327

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/327281"