Reputation: 58921

How do I find the most complex convex polygon enclosing a set of points?

I have a list of (about 200-300) 2d points. I know needs to find the polygon that encloses all of them. The polygon has to be convex, and it should be as complex as possible (i.e. not a rectangular bounding box). It should find this in as low as possible time, but there are no restrictions on memory.

You may answer in pseudocode or any language you want to use.

Upvotes: 3

Answers (4)

Suresh

Reputation: 602

Qhull is good software for computing 2D convex hulls.

Upvotes: 1

Ofek Shilon

Reputation: 16129

If it is a real world problem - as in, not an academic one - there's never really a reason to solve such a generic problem yourself.

Upvotes: 0

crazyscot

Reputation: 11989

Sounds like you're looking for a convex hull algorithm? It's been more than a decade since I was taught about these, but the name Graham Scan sticks in my mind and would probably be where I'd start.

Upvotes: 15

zebrabox

Reputation: 5764

Take a look at Graham's Algorithm.

Upvotes: 4

How do I find the most complex convex polygon enclosing a set of points?

Answers (4)

Related Questions