CODEWITHSUNDEEP
algorithmpolygon
blejzz
blejzz

Reputation: 3349

create a concave polygon from image using N points

i am looking for a algorithm that will generate a concave polygon (with N points where N > 3 - user enters this value) from a image.

My idea for the algorithm:

 // Every pixel in image is checked and a minimal orientated bounding box  is generated  (transparent pixels are ignored)
 boundingBox = createImageBoundingBox(image);
 curpoints = 4, A = 0, B = 1, tmppoints = curpoints;
 while(curpoints < maxNumberOfPoints)
 { 
    add a new point between point A and point B (A and B are points from the boundingBox)
    reposition points so that it will contain the minimal surface
    A++; B++;
    curpoints++;

    if(A == tmppoints) 
    { A = 0; B = 1; tmppoints=curpoints; }
 }

The problem im facing is i dont know how to optimally reposition points. Can this be done any other (better/faster way). Would appreciate any thoughts.

Thanks

EDIT:

The image has to be at least 10x10. I need the N points parameter so the user can regulate how many points are going to be used (for optimization). An alternative would be to have a factor (0-1) which tells how much detailed (how many points) you want the polygon to have (0 being 4 points, > 0 5 or more points). But not sure how to implement it.

Upvotes: 0

Views: 1658

Answers (3)

Cybercartel
Cybercartel

Reputation: 12592

You can use a delaunay triangulation and get the average edge lenght. Then try to remove edges that are longer then the average. The concept is from the alpha shapes.

Upvotes: 2

MBo
MBo

Reputation: 80287

Concave hull may be built with alpha shapes. CGAL link.

Upvotes: 1

Brian Stinar
Brian Stinar

Reputation: 1109

1.) Select a point in the middle of the square image.

2.) Jitter this point N times randomly from the center to generate N new points.

3.) Sort these points based on maximum angle from the center point

4.) Use your four points in your bounding box and your midpoint(s) in sorted ascending angle order to create the ordered point list of your concave polygon.

I am not sure if I understand your 'minimal surface' step above, but I believe this algorithm will work for taking a cut out of image to generate a concave polygon. I think this is faster than your above, but I am not sure because I don't understand that step fully.

This will always generate a concave polygon with the same bounds as your original image. If you don't want this, you could add a step 0.) that jitters your bounding box, and then changes your midpoint jitter based on this. Both of these ideas will result in a bounding quadrilateral with a n-sized point chunk taken out, I think.

  • This requires n > 4 (collapse two of you bounding box points into one if you want this to require n > 3, like you said you want.)

Upvotes: 1

Related Questions