simple-polygon hull with limited verticies

[frupel]

I don't know whether term I used in the name of topic is proper but I need something like this :

I have set P of points (x,y) in the input and I need to find a polygon which will contain all these points. But this polygon can consist of N verticies only.

So.. convex hull algorithms seem to be useless cause I gonna have to reduce significantly number of its(hulls) verticies , and it's only convex, I need concave shapes too.

I've been thinking , I've walked through whole internet two or three times but I've gone nowhere.

Any ideas will be appreciated..

[MXP]

If the N verticies must come from P and N is less than the number of verticies in P then it's not necessarily true that such a polygon exists. Suppose P consists of the verticies of a regular pentagon and N = 3, it should be clear that no three verticies can form a polygon which also contains the other two.

There must be some conditions that you have not specified.

If the N verticies does not need to be contained in P then the problem becomes much simpler.

[frupel]

i didn't write that N verticies must be contained in P , so there is no such condition. these points can lie anywhere.
maybe i unnecessarily mentioned called it 'hull' and it confused you

but i forgot to mention about 'little' thing - i'm looking for optimal ( minimum space polygon ) solution. if it's not possible - for a good heuristic..

[MXP]

That is an important condition. I would imagine that the optimal polygon should have as many points on its edges as possible.

I wonder if you could do something like this: (I'm making this up as I go along and basing it off a diagram I drew on the back of a small receipt so it may be very wrong)
1. Find the center of the collection of points in P (by averaging all of the x- and y-coordinates), call this point C
2. Find the point furthest from the center, let that be a vertex in the N-gon. Call this point P1
3. Draw a horizontal line from P1. Find the point furthest from the horizonal (in terms of the line segment passing through that point and perpendicular to the horizontal) which is not on the same side of the horizontal as C. That is, if C is below the horizontal look for the point above the horizontal and vise-versa. If there is no such point, look for the point closest to the horizontal but on the same side as C. Call this point P2.
4. Let L1 be the line passing through P1 and P2.

At this point, if my imagination and the drawing I made on the back of a receipt are correct, L1 should divide the plane so that all points in P are on one side of L1. A segment of L1 will be an edge of the N-gon.

5. Repeat steps (3) and (4) but instead of a horizontal line from P1, draw a vertical line. Use this to find the point P3 and line L2.

You should now have two lines which contain edges of the N-gon as well as a vertex, P1. Unless all the points of P are colinear then the points P1, P2, and P3, should be distinct.

6. Find the point furthest from P1, call this P4. Note, P4 may not be distinct from P2 or P3.
7. Draw a line through P2 and P3 and call it L3.
8. Draw a line passing through P4 that is parallel to L3 and call this L4.

You should now have the smallest possible triangle which includes all of your points in P. This triangle is made by L1, L2, and L4. From here it should be a lot easier to find the smallest possible N-gon.

[frupel]

this algorithm works but only for subsets of points which form a convex polygon. it won't budge if one of subset forms a concave polygon.

look :
( sorry for leaving links as static text with '_' but it has something to do with spam policy of this forum, and i can't post url's )

here we have sets of points whose 2 subsets form convex shape everything is ok :

h_ttp://img147.imageshack.us/img147/7942/img2267di4.jpg
h_ttp://img118.imageshack.us/img118/8704/img2268jp7.jpg

but that's
h_ttp://img118.imageshack.us/img118/5416/dscn9303nd5.jpg

what happens when one of the subsets is set of verticies forming a concave polygon.

we can't draw L1 line through P1 and P2 cause it will divide plane incorrectly cause points of P will be on both sides of L1.

[MXP]

I made no guarantees that it would work. I was just making it up as I went along. Unfortunately, I had a lot more time while I was making it up than I do now so you'll most likely need to use it as a starting point and then figure out how to fix it.