Outline Drawing

blyk

Hi all, If I have a 2D points set then how to get this
NOT This

I want to connect/join the outermost points of the 2D point set .. I have used "import megamu.mesh.*" convex hull library but it gives the result like second image not like the first image. Is there any function in this library to change the resolution of the outline or I 'll have to use totally different library ?

quark

I suspect that you will need to find something else. It is a 'convex hull' library which means that the internal angle at any vertex will be <= 180 degrees. What you want in a 'concave hull' library (I don't know of any) since this will not have the same restriction.

It is possible to write your own but the algorithm would be challenging to implement.

TfGuy44

Also, what you are asking for isn't defined very well. I mean, why follow the black lines instead of these green ones?

http://imgur.com/cU9kmvp

Redwire

Well, you could display the points on the screen then define the coordinates of the outline on screen using mousex, mousey, record them, then the draw a line shape using the coordinates.

blyk

@quark : yes, I know that is a convex hull library so can you suggest me something like how to create polygon with outermost points?

@ TfGuy44: :D :D I made the image very quickly ..actually it does look like your image and if we can control the resolution of point approximation can we control the shape of outline.

@Redwire: It is a dynamic point set ..I can't use mouse operation for this. any suggestion ?

Redwire

after the sketch is drawn can't you export it. Then in a new sketch use the pdf, png, etc as a background image and use the mouse function to pick up the xy coordinates to draw the outline

blyk

@Redwire : Actually I wanted to include it with the kinect user pixles and draw the boundary of users.... like here you see in the the video ..... can you suggest me how to do that my this code is different because I haven't used any library other than SimpleopneNI and it SHOWS BOUNDARY :D

quark

I know that is a convex hull library so can you suggest me something like how to create polygon with outermost points?

Yes I believe I could come up with an algorithm to trace the 'outermost points' but it would more likely to give you the green line in TfGuy44's picture (or perhaps something in between).

Unfortunately I have been unable to get SimpleOpenNi to work on my computer so I can't try out your code but looking at the video and the mention of 'SHOWS BOUNDARY' suggests that you have an outline you want to triangulate?

Could you give a bit more detail as to where the dots come from and how are they stored e.g. array of PVector or something else.

blyk

Quark!, I don't want the triangulation instead I want that boundary. It looks very jigglya and dynamic which is so cool so I want that effect in it. Currently in my code it is just pixels colored with red and blue color. Here is the result ..

Actually it doesn't store any PVector but as you can see blob_array store the pixels on users and all those pixles are set to 255 (in the first nested for loop) after storing desired pixels into the blob_array we again check in the next for loop if the left pixels or right pixels are white or black an according to that we paint them as red and blue. You can easily this red and blue effect in image.

I had tried storing the blob_array pixles in a PVector arrayList but when I tried applying Quickhull3D function on those points nothing showed up. I don't know what was the problem.

quark

The picture and the code make the problem a lot clearer, in fact I would suggest that it very different from your original post.

I don't want the triangulation instead I want that boundary

How do you propose the boundary will be defined or stored?

I would say that this image is very different from the one you first posted, and the problem is very different. The amount of data (points) is now larger, they no longer occupy the interior of a shape - they are the boundary of the shape. Unfortunately any algorithm I come up with is unlikely to be fast enough for a real time system especially since you want to keep that 'very jigglya and dynamic' look which means that you can't reduce the data set (points) in the analysis.

I did a Google search - bitmap to vector line tracing Java - any I can't find a pure Java library, I found Delineate, a Java front end to non-Java libraries AutoTrace and Potrace but these look difficult to get right. If you are feeling brave you might try this algorithm.

Sorry I can't be more help but I don't have a kinect so I can't try playing with your code.

blyk

I have used ArrayList (named poop) in the code. Which I have saved when pixels get colored with red and blue color in the second nested for loop (line 17-49). In the third loop I have call the ArrayList element (line 50-end). Now, the problems

• Lines (25-27) & (37-39) draw ellipse on the boundary and it will only show up when you comment the update.pixels(); otherwise you wont be able to see.
• I have saved the ellipse's coordinates in the ArrayList (poop) and then called it later.
• Line(50-end) I have called arrayList here but it doesn't show any that I had tried to draw. Any Idea what could be the problem. (now its working :D )

blyk

Quark! Line number (50-67) where I had called ArrayList, was not showing anything because extensive calculation made it slow. Replace it with this ...

Quark can your please write me a code which can show the boundary of the user like in the video that I had linked in the previous post. I want that effect only. Not the triangulation, only boundary I want because triangulation I can get like the image I have linked here. Actually I want boundary to be closed polygon so that I can check if any point is inside the polygon or not but this problem I'll solve later.

quark

Quark can your please write me a code which can show the boundary of the user like in the video that I had linked in the previous post.

I could have made an effort with the sparse point set in your original post but the blue-red edge image is something else. You probably need a line tracing algorithm but that would need a continuous pixel line - yours is discontinuous. The algorithm I mentioned in a previous post is useless for this scenario (I tried it). A Google search shows that line tracing algorithms to produce vector representations failed to find a simple to implement solution.

Sorry I can't help you further with this problem, maybe someone else might be able to help.

blyk

okey thanks a lot Quark! :)>- :)>- :)>- :)>- I'll try solving this by myself or wait someone to reply on this post.

But can you hint me something if it is possible to do - " Since this ArrayList is a unsorted collection of PVector so can we sort it and then connect all the points. Or Is there any method to make polygon out of the ArrayList point ? " :-/ :-/

quark

The problem is that this is 2D data so how do you sort it - if you sort it on x this will help find vertical lines, if you sort it by y then it will help find horizontal lines.

The best I could come up with was to convert this black and white image

to this

The algorithm first creates an arraylist of PVector and adds a PVector for every pixel identified as part of the border. It then converts the list to an array to speed up the next part of the algorithm.

The next stage takes the first PVector in the array which I call the pivot and sorts the ones after it in ascending order of distance from the pivot. The second item in the array becomes the pivot and again it sorts the elements after the pivot. It repeats this until the end of the array.

The image could be improved if there were less gaps in the original image. It would then be possible to modify the algorithm to find disparate groups of pixels e.g. holes.

The algorithm is slow (took ~480ms on my machine) so will not work well in a real-time system but its the best I can come up with.

HTH

PImage imgRaster;

public void setup(){
    size(462, 424);
    imgRaster = loadImage("data/points2.png");
    println("Image size " + imgRaster.width + ", " + imgRaster.height);
    long time = millis();
    PVector[] border = rasterToVector(imgRaster);
    println("Time to vectorize = " + (millis() - time) + " milliseconds" );
    println("Number of points " + border.length);
    // Draw border and save image
    background(0,32,0);
    stroke(0,255,0);
    strokeWeight(1);

    if(border.length > 1){
        for(int i = 1; i < border.length; i++)
            line(border[i-1].x, border[i-1].y, border[i].x, border[i].y);
    }
    redraw();
}

public PVector[] rasterToVector(PImage img){
    int w = img.width;
    int h = img.height;

    ArrayList<PVector> v = new ArrayList<PVector>();
    img.loadPixels();
    // Stage 1 create vectors for each boundary pixel
    int r, g, b, c;
    int index = 0;
    for(int k = 0; k < h; k++){
        for(int j = 0; j < w; j++){
            c = img.pixels[index];
            r = ((c & 0xff0000) >> 16);
            g = ((c & 0xff00) >> 8);
            b = (c & 0xff);
            if(r < 128 || g < 128 || b < 128) {
                img.pixels[index] = 0xffff0000;
                v.add(new PVector(j, k));
            }
            index++;
        }
    }
    img.updatePixels();
    // Get an array of EVectors for speed
    PVector[] vecs = v.toArray(new PVector[v.size()]);
    int nbrVecs = vecs.length;
    if(vecs.length > 2){
        for(int i = 1; i < nbrVecs - 2; i++) {
            PVector pivot = vecs[i-1];
            DistanceComparitor comp = new DistanceComparitor(pivot.x,  pivot.y);
            Arrays.sort(vecs, i, nbrVecs - 1, comp);
        }
    }
    return vecs;
}

public class DistanceComparitor implements Comparator<PVector> {
    private final float x;
    private final float y;

    public DistanceComparitor(float x, float y){
        this.x = x;
        this.y = y;
    }

    public int compare(PVector v1, PVector v2) {
        float v1d2 = (v1.x - x)*(v1.x - x) + (v1.y - y)*(v1.y - y);
        float v2d2 = (v2.x - x)*(v2.x - x) + (v2.y - y)*(v2.y - y);
        if(v1d2 == v2d2)
            return 0;
        else
            return (v1d2 < v2d2) ? -1 : 1;
    }

}

blyk

thanks Quark! I'll try to optimize it :)