[Haskell-cafe] Finding the Convex Hull (Problem 12 of Real World Haskell)
I wrote a solution to this problem, but it appears to return incorrect results. There's a pastebin of the code at http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2121 and a picture of the inputs, outputs, and expected results graphed at http://img510.imageshack.us/img510/9971/resultsg.jpg I'm wondering if this is a flaw in my code, my understanding of the problem, or both. Any ideas on how to track this one down would be very much appreciated. Thank you! -- ヽ(^o^)ノ -rob ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finding the Convex Hull (Problem 12 of Real World Haskell)
Whenever I'm looking for a bug in Haskell code, I find it helpful to start by seeing if I can simplify the code any first. In this case, there are a couple of things I notice: - validPointsOf is just a filter. It would be easier to write valid :: MyDirection - Bool and then validPointsOf = filter (valid . snd) - Similarly, there's no need to write your own minimum-finder and call it lowestY. Instead, write (or derive!) an Ord instance, and then use the standard prelude function minimum - a small simplification of sortByCoTan: sortByCoTan pivot = sortBy (comparing (coTan pivot)) Hope this helps! 2009/3/5 Rob Crowther weila...@gmail.com I wrote a solution to this problem, but it appears to return incorrect results. There's a pastebin of the code at http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2121 and a picture of the inputs, outputs, and expected results graphed at http://img510.imageshack.us/img510/9971/resultsg.jpg I'm wondering if this is a flaw in my code, my understanding of the problem, or both. Any ideas on how to track this one down would be very much appreciated. Thank you! -- ヽ(^o^)ノ -rob ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finding the Convex Hull (Problem 12 of Real World Haskell)
Am Donnerstag, 5. März 2009 13:40 schrieb Rob Crowther: I wrote a solution to this problem, but it appears to return incorrect results. There's a pastebin of the code at http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2121 and a picture of the inputs, outputs, and expected results graphed at http://img510.imageshack.us/img510/9971/resultsg.jpg I'm wondering if this is a flaw in my code, my understanding of the problem, or both. Definitely flawed code, probably based on incorrect understanding of the algorithm. Any ideas on how to track this one down would be very much appreciated. To track it down, it would be helpful to look at the intermediate results and see where they differ in what way from your expectations. *ConvexHull let pointlist :: [Point2D]; pointlist = [(0,0), (2,0), (4,0), (6,0), (5,-2), (5,2), (0,4), (6,4), (5,6)] *ConvexHull lowestY pointlist (5.0,-2.0) *ConvexHull sortByCoTan it pointlist [(0.0,0.0),(2.0,0.0),(0.0,4.0),(4.0,0.0),(5.0,2.0),(5.0,6.0),(6.0,4.0),(5.0,-2.0),(6.0,0.0)] *ConvexHull let sortedpoints = it *ConvexHull listOfTurns sortedpoints [MyRight,MyLeft,MyRight,MyRight,MyLeft,MyLeft,MyRight] *ConvexHull zip sortedpoints (MyStraight:MyStraight:it) [((0.0,0.0),MyStraight),((2.0,0.0),MyStraight),((0.0,4.0),MyRight),((4.0,0.0),MyLeft),((5.0,2.0),MyRight),((5.0,6.0),MyRight),((6.0,4.0),MyLeft),((5.0,-2.0),MyLeft),((6.0,0.0),MyRight)] *ConvexHull validPointsOf it Thank you! *ConvexHull let ly = lowestY pointlist *ConvexHull coTan ly ly NaN First, you'd want to separate the point with lowest y-coordinate from the rest, like lowestY :: [Point2D] - (Point2D,[Point2D]) lowestY (x:xs) = foldr update (x,[]) xs where update a (b,cs) = -- left as an exercise Then it might be a good idea to make sortByCoTan insensitive to other points with the same lowest y-coordinate, and of course, sort only the points other than the starting point. Also, the way the points are sorted, you'll walk clockwise around the boundary, so you'd never turn left, only proceed straight or turn right. But the turn at each point does not depend on its neighbours in the list sorted by cotangent, but on which points have so far been chosen, so you have to compute the turn based on that. The selection of points is considerably more complicated than just looking at the turn, consider e.g. [(0,0), (-2,2), (-2,3),(-1,3),(0,4),(1,4),(2,6),(3,9)]. When you have three points a, b and c, and you go from a via b to c, the turn at b is right, iff crossProduct a b c 0 left, iff crossProduct a b c 0. HTH, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Finding points contained within a convex hull.
It's been a while, but I believe that you can solve integer programming problems of this type using Groebner bases. (Google for integer programming with Groebner bases). I have some Groebner basis code in Haskell at http://www.polyomino.f2s.com/david/haskell/commalg.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finding points contained within a convex hull.
On Jun 6, 2007, at 11:38 PM, Daniel McAllansmith wrote: [Trying to find the domain of a bounded integer linear program] How would you go about finding extreme vertices? Would it be quicker than solving the constraints for each max/min? If you're just looking to find bounding coordinates in each dimension, you should be able to do this using linear programming. This will yield non-integer coordinate bounds which you can narrow as appropriate. -Jan-Willem Maessen smime.p7s Description: S/MIME cryptographic signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finding points contained within a convex hull.
On Wed, Jun 06, 2007 at 12:23:03PM +1200, Daniel McAllansmith wrote: Hello. I've got a system of linear inequalities representing half-spaces. The half-spaces may or may not form a convex hull. I need to find the integral coordinates that are contained within the convex hull, if there is one. For example, given 0 = x = 4 0 = y = 3 0 = 2x - y 0 = 1.2y - x I want the following (x,y) coordinates [(0,0),(1,1),(1,2),(2,2),(2,3),(3,3)] Anybody have any suggestions, or libraries, for solving this in many dimensions and equations? If I am not mistaken, this problem is called integer programming and it is NP-complete ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finding points contained within a convex hull.
Do you simply want the set of coordinates, or do you want to do something smart with the them (i.e. optimize a function value etc)? In the first case, with a good starting point and a function that enumerates all coordinates (by going in a spiral, perhaps), I think this can be done in O(nm), where n = number of coordinates in the hull and m = number of conditions to be tested for each point. But that all depends on the number of coordinates iterated but not in the hull being constant, i.e. the number of coordinates iterated but filtered out of the set - I have a hunch that that you'll have to factor in the number of dimensions somehow - it could well be O(n^dm) or something. Oh, and you'll need a terminating condition for the coordinate enumerator - and prove that it is correct. The latter case is NP-complete ;-) Which might mean that what I said above is totally wrong and is also an NP-complete problem. Oh, and BTW, isn't any intersection of half-spaces always a convex hull? In which case is it not? // Simon On 6/6/07, Ilya Tsindlekht [EMAIL PROTECTED] wrote: On Wed, Jun 06, 2007 at 12:23:03PM +1200, Daniel McAllansmith wrote: Hello. I've got a system of linear inequalities representing half-spaces. The half-spaces may or may not form a convex hull. I need to find the integral coordinates that are contained within the convex hull, if there is one. For example, given 0 = x = 4 0 = y = 3 0 = 2x - y 0 = 1.2y - x I want the following (x,y) coordinates [(0,0),(1,1),(1,2),(2,2),(2,3),(3,3)] Anybody have any suggestions, or libraries, for solving this in many dimensions and equations? If I am not mistaken, this problem is called integer programming and it is NP-complete ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finding points contained within a convex hull.
Daniel McAllansmith wrote: Hello. I've got a system of linear inequalities representing half-spaces. The half-spaces may or may not form a convex hull. They could only fail to define a convex volume if they are inconsistent and define an empty set. Though they might define a convex volume of lesser dimension than the space. I need to find the integral coordinates that are contained within the convex hull, if there is one. For example, given 0 = x = 4 0 = y = 3 0 = 2x - y 0 = 1.2y - x I want the following (x,y) coordinates [(0,0),(1,1),(1,2),(2,2),(2,3),(3,3)] Anybody have any suggestions, or libraries, for solving this in many dimensions and equations? Thanks Daniel This FAQ looks useful: http://www.cs.mcgill.ca/~fukuda/soft/polyfaq/polyfaq.html You want to find something like the Volume, so Quoting from: http://www.cs.mcgill.ca/~fukuda/soft/polyfaq/node26.html Is there any efficient algorithm to compute the volume of a convex polytope in $ R^d$? It is known that computing the volume of a $ V$-polytope (or H-polytope) is #P-hard, see [DF88] and [Kha93]. There are theoretically efficient randomized algorithms to approximate the volume of a convex body [LS93] but no implementation seems to be available. There is a comparative study [BEF00] of various volume computation algorithms for convex polytopes. It indicates that there is no single algorithm that works well for many different types of polytopes. For ``near'' simple polytopes, triangulation-based algorithms are more efficient. For ``near'' simplicial polytopes, sign-decomposition-based algorithms are better. See the paper for the justification of these claims. I have never touched a problem like this, but it seems that enumerating the point could be attacked by recursive brute force: * Find an extreme vertex and any other point in the polyhedra (e.g. a different extreme vertex). If the polyhedra is empty this will fail. If the polyhedra is a single point this will find one vertex but no other point, so just check this vertex to see if it has all integer coordinates. * Pick a dimension for which the vertex and other point have different coordinates. Call this dimension's coordinate x. The vertex has value vx and the other point ix. Neither vx nor ix are required to be integers. * Now you make several recursive problems that have different integer values of coordinate x. These subproblems are in two series: ** Increasing series x = a, a+1, a+2, a+3, ... where a = ceil of vx. ** Decreasing series x = b, b-1, b-2, b-3, ... where b = floor of vx. ** Obviously a==b is a special case. ** If you are very clever you can always find a dimensions for which it is obvious that one of the two series is always outside the polygon and need not be checked. But this will also be noticed by the brute force algorithm once that series is run for the first x not equal to vx (which will be either the first or second element of that series depending on whether vx is an integer). * For the two series plug 'x' back into your original set of equations. ** If any equation is False then stop this series of subproblems ** If an equation is True then you can remove it ** If all equations are True, then you have found a integer point in the volume and you can return it and continue with the series of subproblems. ** Otherwise, take the remaining equation compute the vertices of the convex hull (If the new polyhedra is empty then stop this series of subproblems) and iterate this enumeration procedure. ** Note: A subproblem may find no integer points in its convex hull, but that does not stop the algorithm from checking the next value of x in the series. The above looks like a polynomial time complexity algorithm to me. Cheers, Chris ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finding points contained within a convex hull.
Simon Brenner wrote: Do you simply want the set of coordinates, or do you want to do something smart with the them (i.e. optimize a function value etc)? In the first case, with a good starting point and a function that enumerates all coordinates (by going in a spiral, perhaps), I think this can be done in O(nm), where n = number of coordinates in the hull and m = number of conditions to be tested for each point. But that all depends on the number of coordinates iterated but not in the hull being constant, i.e. the number of coordinates iterated but filtered out of the set - I have a hunch that that you'll have to factor in the number of dimensions somehow - it could well be O(n^dm) or something. Oh, and you'll need a terminating condition for the coordinate enumerator - and prove that it is correct. The latter case is NP-complete ;-) Which might mean that what I said above is totally wrong and is also an NP-complete problem. Oh, and BTW, isn't any intersection of half-spaces always a convex hull? In which case is it not? If one transforms to get all the extreme vertexes, then you can easily bound each coordinate by the min and max values of that coordinate in the set of vertexes. These bounds on each coordinate give you a large rectangular box that contains your polyhedra. Brute force testing all the integer coordinates in the box scales as the volume of the box (some length^d) times the cost of computing the conditions, O(d*m). Cheers, Chris ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Finding points contained within a convex hull.
Simon Brenner wrote: Do you simply want the set of coordinates, or do you want to do something smart with the them (i.e. optimize a function value etc)? In the first case, with a good starting point and a function that enumerates all coordinates (by going in a spiral, perhaps), I think this can be done in O(nm), where n = number of coordinates in the hull and m = number of conditions to be tested for each point. But that all depends on the number of coordinates iterated but not in the hull being constant, i.e. the number of coordinates iterated but filtered out of the set - I have a hunch that that you'll have to factor in the number of dimensions somehow - it could well be O(n^dm) or something. Oh, and you'll need a terminating condition for the coordinate enumerator - and prove that it is correct. The latter case is NP-complete ;-) Which might mean that what I said above is totally wrong and is also an NP-complete problem. The number of coordinates in the hull is exponential in the number of bits you use to represent those integers. So, the algorithm and NP-completeness don't contradict each other. The situation is similar to the knapsack problem. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finding points contained within a convex hull.
Thanks for the responses everyone. On Thursday 07 June 2007 00:37, [EMAIL PROTECTED] wrote: Simon Brenner wrote: Do you simply want the set of coordinates, or do you want to do something smart with the them (i.e. optimize a function value etc)? Ultimately optimise several functions over the feasible coordinates, however the functions to optimise are complicated, definitely non-linear, and the linear constraints are already a simplification of non-linear constraints. I was hoping to get a superset of coordinates, filter with the real constraints then optimise each of the target functions. Oh, and BTW, isn't any intersection of half-spaces always a convex hull? In which case is it not? Inconsistent constraints, e.g. x5, y5, x+y10 If one transforms to get all the extreme vertexes, then you can easily bound each coordinate by the min and max values of that coordinate in the set of vertexes. These bounds on each coordinate give you a large rectangular box that contains your polyhedra. Since Ilya pointed out that integer linear programming is NP-complete I've been thinking of determining the bounding-box and doing a branch-and-bound search. My idea was to solve the linear constraints twice for each dimension, to maximise and minimise the variable in that dimension. From there I can divide and conquer, hopefully discarding/fixing whole dimensions and reducing the proportion of invalid coordinates. If need be I could even randomly sample the remaining coordinates to keep things tractable. I guess that's not much different from what I was orginally planning - superset, filter, optimise... the superset is just bigger now. How would you go about finding extreme vertices? Would it be quicker than solving the constraints for each max/min? Thanks Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Finding points contained within a convex hull.
Hello. I've got a system of linear inequalities representing half-spaces. The half-spaces may or may not form a convex hull. I need to find the integral coordinates that are contained within the convex hull, if there is one. For example, given 0 = x = 4 0 = y = 3 0 = 2x - y 0 = 1.2y - x I want the following (x,y) coordinates [(0,0),(1,1),(1,2),(2,2),(2,3),(3,3)] Anybody have any suggestions, or libraries, for solving this in many dimensions and equations? Thanks Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: convex hull
| I need a 'convex hull' implementation in Haskell. | Does anyone know where I can find one? Joern Dinkla has implemented several geometric algorithms in Haskell, see http://goethe.ira.uka.de/~dinkla/cglib.html Cheers, Ralf
