Convex hull: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,208: / Line 1,208: @@
 {{out}}
 <pre>[(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
+=={{header|Nim}}==
+{{trans|Rust}}
+<lang nim>type
+  Point = object
+    x: float
+    y: float
+# Calculate orientation for 3 points
+# 0 -> Straight line
+# 1 -> Clockwise
+# 2 -> Counterclockwise
+proc orientation(p, q, r: Point): int =
+  let val = (q.y - p.y) * (r.x - q.x) -
+    (q.x - p.x) * (r.y - q.y)
+  if val == 0: 0
+  elif val > 0: 1
+  else: 2
+proc calculateConvexHull(points: openArray[Point]): seq[Point] =
+  result = newSeq[Point]()
+  # There must be at least 3 points
+  if len(points) < 3:
+    for i in points: result.add(i)
+  # Find the leftmost point
+  var indexMinX = 0
+  for i, _ in points:
+    if points[i].x < points[indexMinX].x:
+      indexMinX = i
+  var p = indexMinX
+  var q = 0
+  while true:
+    # The leftmost point must be part of the hull.
+    result.add(points[p])
+    q = (p + 1) mod len(points)
+    for i in 0..<len(points):
+      if orientation(points[p], points[i], points[q]) == 2:
+        q = i
+    p = q
+    # Break from loop once we reach the first point again
+    if p == indexMinX:
+      break
+var points = @[Point(x: 16, y: 3),
+               Point(x: 12, y: 17),
+               Point(x: 0, y: 6),
+               Point(x: -4, y: -6),
+               Point(x: 16, y: 6),
+               Point(x: 16, y: -7),
+               Point(x: 17, y: -4),
+               Point(x: 5, y: 19),
+               Point(x: 19, y: -8),
+               Point(x: 3, y: 16),
+               Point(x: 12, y: 13),
+               Point(x: 3, y: -4),
+               Point(x: 17, y: 5),
+               Point(x: -3, y: 15),
+               Point(x: -3, y: -9),
+               Point(x: 0, y: 11),
+               Point(x: -9, y: -3),
+               Point(x: -4, y: -2),
+               Point(x: 12, y: 10)]
+let hull = calculateConvexHull(points)
+for i in hull:
+  echo $i</lang>
+{{out}}
+<pre>
+(x: -9.0, y: -3.0)
+(x: -3.0, y: -9.0)
+(x: 19.0, y: -8.0)
+(x: 17.0, y: 5.0)
+(x: 12.0, y: 17.0)
+(x: 5.0, y: 19.0)
+(x: -3.0, y: 15.0)
+</pre>
 =={{header|Perl 6}}==