quickest point in ofPolyline method?

hello all

I am working on an app where I generate a large amount of irregularly shaped polygons and then call out the pixels that are contained within them. It is working reasonably well but I am wondering whether I am missing a method for detecting the ‘point in polyline’ (i.e. hits) that is faster than the one I am using.

At present I have:

  
  
  
void VRay::findInside(ofPolyline polycheck){  
    ofRectangle bounds = polycheck.getBoundingBox();  
    int x1 = bounds.getMinX();  
    int y1 = bounds.getMinY();  
    int x2 = bounds.getMaxX();  
    int y2 = bounds.getMaxY();  
      
    #pragma omp parallel for  
    for (int y = y1; y<y2; y++){  
        for (int x = x1; x<x2; x++){  
            if((y>by1)&&(y<by2)&&(x>bx1)&&(x<bx2)){  
                if(polycheck.inside(x, y)){  
  

As you can see I’m using the ofPolyline inside call after a bounding box (plus a little OMP to parallel the for loop)
Does anyone know a quicker method? Some of my bounding boxes are quite large.

For example, would drawing the shape into a buffer and then checking pixel colour be faster? And how would I do this?

In hope…
S

update:

I’m trying out using an ofFbo object as an offscreen buffer to do the pixel interrogation (to see if it is faster)
The following code compiles and runs ok but I don’t get any hit detections, is there something I am doing wrong here?

  
void VRay::findInside(ofPolyline polycheck, int k){  
    ofRectangle bounds = polycheck.getBoundingBox();  
    int x1 = bounds.getMinX();  
    int y1 = bounds.getMinY();  
    int x2 = bounds.getMaxX();  
    int y2 = bounds.getMaxY();  
    int widtho = x1-x2;  
    int heighto = y1-y2;  
      
    ofFbo fbo;  
    fbo.allocate(200,200,GL_RGBA);  
    fbo.begin();  
    ofClear(0,0,0);  
    ofSetColor(255, 255, 255);  
    polycheck.draw();  
    fbo.end();  
      
    ofPixels pixels;  
    fbo.readToPixels(pixels);  
          
    #pragma omp parallel for  
    for (int y = 0; y<(y1-y2); y++){  
        for (int x = 0; x<(x1-x2); x++){  
            if(((y+y1)>by1)&&((y+y1)<by2)&&((x+x1)>bx1)&&((x+x1)<bx2)){  
                int value = pixels[x+y*(widtho)];  
                if(value!=0){  
  

^^where the ‘pixels’ interrogation is replacing the former ofPolyline inside query

Anyone have any pointers?

S

not sure what might be going on but usually allocating an fbo, pixels and reading back from the graphics card will be slower than the process you were doing.

what are you trying to do? i mean what do you need to detect all the points inside a poly? there’s probably a faster way to do it than checking for every posible pixel

hey Arturo

Yes, that’s exactly it; I want to grap the x/y coords of all the points within the generated polygon.
(a side point, the app I am writing does this a lot! - for about ten polyline shapes generated from about ten locations on screen per frame at 50fps)

there were a couple of mistakes in my last code post, since then I’ve got both methods working in parallel.
Interestingly the ofFbo trick is slightly faster for larger, more irregular shapes but dies on small shapes; the ‘is inside’ ofpolyline is faster from smaller, regular shapes.

This is probably because of the relative sizes of the bounding rects…

However, I think that probably neither approach that I have at the minute is optimal; if there is another way to grab all points it would be good to know/I’d be keen to spend a little time on to get working.

Here is the two approaches as at the moment within one function (with a little more commenting this time):

  
  
void VRay::findInside(ofPolyline polycheck, int k){  
    ofRectangle bounds = polycheck.getBoundingBox();  
    int x1 = bounds.getMinX();  
    int y1 = bounds.getMinY();  
    int x2 = bounds.getMaxX();  
    int y2 = bounds.getMaxY();  
      
    if(((testApp*)ofGetAppPtr())->scatter){  //this is in the instance of large spread out shapes  
        ofPath path;  
        for( int i = 0; i < polycheck.getVertices().size(); i++) {  
            if(i == 0) path.moveTo(polycheck.getVertices()[i] );  
            else path.lineTo( polycheck.getVertices()[i] );  
        }  
        path.close();  
          
        ofPixels pixels;  
        ofFbo fbo;  
        pixels.allocate(width,height,OF_PIXELS_RGB);  
        int samples = fbo.maxSamples();  
        fbo.allocate(width,height,GL_RGB,samples);  
          
        fbo.begin();  
        ofClear(0,0,0);  
        ofSetColor(255,0,0);   //paint shape as a white object  
        path.draw();             //draw to ofFbo  
        fbo.readToPixels(pixels);  
        fbo.end();  
          
        #pragma omp parallel for  
        for (int y = y1; y<y2; y++){      //cycle through bounding box points  
            for (int x = x1; x<x2; x++){  
                if((y>by1)&&(y<by2)&&(x>bx1)&&(x<bx2)){  
                    ofColor cl = pixels.getColor(x,y);     
                    if(cl.r>0){      //if colour is higher than black  
                        int m = x + (y*width);  
                        //do stuff here using m to call back to the pixel array location  
                        }}}}}  
      
    else{       //this is for smaller shapes  
        #pragma omp parallel for  
        for (int y = y1; y<y2; y++){      //cycle through bounding box points  
            for (int x = x1; x<x2; x++){  
                if((y>by1)&&(y<by2)&&(x>bx1)&&(x<bx2)){  
                    if(polycheck.inside(x, y)){   //OF native polyline interrogation for point inside shape  
                        int m = x + (y*width);  
                        //do stuff here using m to call back to the pixel array location  
                        }}}}}  
}  
  

If anyone knows a way to beat the above for speed it would be great to know

S

what i mean is what are you doing with that info, there’s probably something you can do in a shader to avoid detecting the points inside the poly at all

ah, good question

I’m recording properties of the polygon; area, perimeter, centre of gravity + others. For each point in each polygon I save these back to an array that contains all the points on screen. Over multiple iterations of polygons…

Does that make sense?

S

ah ok, in that case i guess the fastest would be to use opencv. with ofxCv you can convert an ofPolyline to opencv native format using toCv and then use opencv functions to calculate those properties.

Ok, I’ll hopefully get to check this out tomorrow. Anywhere I could look in particular?

Thanks!
S

Me again

I’ve been through the ofxCV library and examples. I get that I can call the polyline toCV in order to grab area and perimeter, but I could do all this anyway using ofPolyline functions.

Does ofxCV have a function to find point in shape? Doubt it has a return all points in shape (tho that would be perfect as a vector) but this is the main process that I want to try and speed up.

This suggests it hasn’t been written yet? see line 25
https://github.com/kylemcdonald/ofxCv/blob/master/libs/ofxCv/include/ofxCv/ContourFinder.h

S

probably it has but not sure, what you can get though is the final parameters you need to extract like center of gravity, orientation…

well, some more time spent, some more dead ends discovered…

I dug into the ofPolyline to look at the .inside(x,y) method. It uses Bourke’s approach
(see here http://paulbourke.net/geometry/polygonmesh/)

Bourke also describes two other approaches for finding points within non convex polygons. So I thought what the hell and wrote them up to test respective speeds. One by Randolph Franklin and one by Philippe Reverdy.

Here are the functions, which work well enough to test speed but may not be perfect:

  
//--------------------------------------------------  
bool ofPolyline::inside(float x, float y, const ofPolyline & polyline){  
      
	int counter = 0;  
	int i;  
	double xinters;  
	ofPoint p1,p2;  
      
	int N = polyline.size();  
      
	p1 = polyline[0];  
	for (i=1;i<=N;i++) {  
		p2 = polyline[i % N];  
		if (y > MIN(p1.y,p2.y)) {  
            if (y <= MAX(p1.y,p2.y)) {  
                if (x <= MAX(p1.x,p2.x)) {  
                    if (p1.y != p2.y) {  
                        xinters = (y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;  
                        if (p1.x == p2.x || x <= xinters)  
                            counter++;  
                    }  
                }  
            }  
		}  
		p1 = p2;  
	}  
      
	if (counter % 2 == 0) return false;  
	else return true;  
}  
  
  
bool ofPolyline::ReverdyInside(float x, float y,const ofPolyline & polyline){  
    int n = polyline.size();  
    float angle=0;  
    ofPoint p1,p2;  
      
    for (int i=0;i<n;i++) {  
        ofVec2f startFirst(polyline[i].x, polyline[i].y);  
        ofVec2f point(x, y);  
        ofVec2f startLast(polyline[(i+1)%n].x, polyline[(i+1)%n].y);  
  
        ofVec2f First(startFirst-point);  
        First.normalize();  
        ofVec2f Last(startLast-point);  
        Last.normalize();  
        float d0T = First.x*Last.x + First.y*Last.y; //dot product  
        float dtheta = acos(d0T);  
        while (dtheta > PI) dtheta -= 2*PI;  
        while (dtheta < -PI) dtheta += 2*PI;  
          
        angle += dtheta;  
    }  
      
    if (abs(angle) < PI) return false;  
    else return true ;  
}  
  
  
  
bool ofPolyline::FranklinInside(float x, float y,const ofPolyline & polyline){  
    int counter = 0;  
    int nvert = polyline.size();  
    int i;  
    int k;  
    for (i = 0, k=nvert-1; i<nvert; k=i++){  
        int viX = polyline[i].x;  
        int viY = polyline[i].y;  
        int vkX = polyline[k].x;  
        int vkY = polyline[k].y;  
        if(((viY>y)!=(vkY>y))&&(x<(vkX-viX)*(y-viY)/(vkY-viY)+viX)) counter++;  
    }  
    if (counter % 2 == 0) return false;  
	else return true;  
}  

Having done all this, well, the Bourke method still wins. Franklin is a little bit slower and Reverdy seems to be quite a bit slower.

All of which leaves me where I was. The ofPolyline.inside method works fast for small shapes whilst the ofFbo ‘cheat’ approach is ok for larger ones.

There is one final possible improvement which would be if I could vary the size of the ofFbo object. At the minute it crashes if I allocate it to the size of the ofPolyline bounding object and so I have to size it to screen size.

For example, in this code:

  
void VRay::findInside(ofPolyline polycheck, int k){  
    ofRectangle bounds = polycheck.getBoundingBox();  
    int x1 = bounds.getMinX();  
    int y1 = bounds.getMinY();  
    int x2 = bounds.getMaxX();  
    int y2 = bounds.getMaxY();  
    int boundsW = x2-x1;  
    int boundsH = y2-y1;  
  
    if(((testApp*)ofGetAppPtr())->scatter){  
        ofPath path;  
        for( int i = 0; i < polycheck.getVertices().size(); i++) {  
            if(i == 0) path.moveTo(polycheck.getVertices()[i] );  
            else path.lineTo( polycheck.getVertices()[i] );  
        }  
        path.close();  
          
        ofPixels pixels;  
        ofFbo fbo;  
        pixels.allocate(width,height,OF_PIXELS_RGB);        //but would like to allocate to just bounding box size  
        int samples = fbo.maxSamples();  
        fbo.allocate(width,height,GL_RGB,samples);          //but would like to allocate to just bounding box size  
          
        fbo.begin();  
        ofClear(0,0,0);  
        ofSetColor(255,0,0);  
        path.draw();  
        fbo.readToPixels(pixels);  
        fbo.end();  
          
        #pragma omp parallel for  
        for (int y = y1; y<y2; y++){  
            for (int x = x1; x<x2; x++){  
                if((y>by1)&&(y<by2)&&(x>bx1)&&(x<bx2)){  
                    ofColor cl = pixels.getColor(x,y);  
                    if(cl.r>0){  
                        int m = x + (y*width);  
                        //send info to pixels here  
}}}}}  

You can see that both pixels and ofFbo object are allocated to width,height (i.e. screen size). This approach would be faster if they were just the ofPolyline bounding size, which would probably make the method work for small polygons just as well as large ones.

However, when I set the following:

  
  
      pixels.allocate(boundsW,boundsH,OF_PIXELS_RGB);        //but would like to allocate to just bounding box size  
        int samples = fbo.maxSamples();  
        fbo.allocate(boundsW,boundsH,GL_RGB,samples);          //but would like to allocate to just bounding box size  

the debug.app falls over as it tries to destroy and then recreate the ofFbo fbo object with a new allocation (ie on the second ofPolyline it tests). Is there something I don’t know about ofFbo that would solve this? Could then at least compare this method for small polys.

in hope…
S

1 Like