Entry tags:

c++, d language, python

Convex Hull in D
From Wikipedia I have found a link to simple C++ code to find the Convex Hull of points in 2D (about 795 lines with comments, and it crashes with n=10000 random integer 2D points):
http://www.microplop.com/assets_c/2007/11/convexhull.h
http://www.microplop.com/assets_c/2007/11/main.cpp

This is (nice) Python code written by David Eppstein (Mar 2002):
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117225

And the following templated function is its translation to D (about 14 lines without comments):

/** Returns the array of the points on the convex hull of a list of 2D
points in O(n log n) time. A point is a static array of length 2. */
T[2][] convexHull2D(T)(T[2][] points) {
  // Andrew's monotone chain algorithm
  T[2][] U, L;
  // Return positive number if p-q-r are clockwise, neg if ccw, zero if colinear
  T orientation(T[2] p, T[2] q, T[2] r) {
    return (q[1]-p[1])*(r[0]-p[0]) - (q[0]-p[0])*(r[1]-p[1]);
  }
  foreach(p; points.sort) {
    while (U.length > 1 && orientation(U[$-2],U[$-1],p) <= 0)
      U.length = U.length - 1;
    while (L.length > 1 && orientation(L[$-2],L[$-1],p) >= 0)
      L.length = L.length - 1;
    U ~= p; L ~= p;
  }
  return U.length ? U[0 .. $-1] ~ L.reverse : U;
}

import std.stdio: writefln;
void main() {
  int[2][] points = [[2, 284], [12, 465], [339, 495], [641, 815], [171, 37],
                     [99, 694], [207, 633], [648, 855], [713, 300], [331, 563]];
  writefln(convexHull2D(points));
}

If you want to make it faster you can use my D libs and replace this line:

foreach(p; points.sort) {

With:

foreach(p; points.fastSort()) {

This convexHull2D() code isn't optimized for speed, but for small practical situations it's enough, it's able to find the convex hull of 1_000_000 float 2D points uniform in [0,1]^2 in 6.5 seconds (convex hull of 38 points) on a Pentium3 500 MHz.
On 200_000 2D points (double) it needs 1.5 seconds, while the same code in Python (a different dataset) needs 12.6 s and Psyco 5.2 s. This shows that in some situations D allows to write (templated) programs not much more complex than Python ones, despite running quite faster.

This page on Wikipedia shows another simpler way to speed up the code:
http://en.wikipedia.org/wiki/Convex_hull_algorithms

/>The idea is to quickly exclude many points that would not be part of the convex hull anyway. This method is based on the following idea. Find the two points with the lowest and highest x-coordinates, and the two points with the lowest and highest y-coordinates. (Each of these operations takes O(n).) These four points form a convex quadrilateral, and all points that lie in this quadrilateral (except for the four initially chosen vertices) are not part of the convex hull. Finding all of these points that lie in this quadrilateral is also O(n), and thus, the entire operation is O(n). Optionally, the points with smallest and largest sums of x- and y-coordinates as well as those with smallest and largest differences of x- and y-coordinates can also be added to the quadrilateral, thus forming an irregular convex octagon, whose insides can be safely discarded.<