Convex hull: Difference between revisions
Added 11l
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 9:
* http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
<br><br>
=={{header|11l}}==
{{trans|Nim}}
<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
R 0
R I val > 0 {1} E 2
F calculateConvexHull(points)
[(Int, Int)] result
I points.len < 3
R points
V indexMinX = 0
L(p) points
V i = L.index
I p.x < points[indexMinX].x
indexMinX = i
V p = indexMinX
V q = 0
L
result.append(points[p])
q = (p + 1) % points.len
L(i) 0 .< points.len
I orientation(points[p], points[i], points[q]) == 2
q = i
p = q
I p == indexMinX
L.break
R result
V points = [(16, 3),
(12, 17),
(0, 6),
(-4, -6),
(16, 6),
(16, -7),
(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)]
V hull = calculateConvexHull(points)
L(i) hull
print(i)</lang>
{{out}}
<pre>
(-9, -3)
(-3, -9)
(19, -8)
(17, 5)
(12, 17)
(5, 19)
(-3, 15)
</pre>
=={{header|Ada}}==
| |||