Hit test (point in polygon) algorithm for complex polygons

Programming Questions

cingraham

Hit test (point in polygon) algorithm for complex polygons

in Programming Questions • 1 year ago

I'm looking to do a hit test on complex polygon shapes (basically, testing whether a mouse is over a state or country area on a map). I've tried the PGraphics buffer solution (color-picking), but ran into a wall when I found out that off-screen PGraphics buffers aren't supported in Processing.js (which is a requirement for the projects I'm working on).

So, I'd like to implement some sort of algorithm for hit test. I've found a lot of generic algorithms for this online, but the problem is that I have no idea how to adapt these for a Processing environment. Can anyone help me rewrite one of the algorithms below?

Here's one possibility, from http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test/2922778#2922778:

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy) { int i, j, c = 0; for (i = 0, j = nvert-1; i < nvert; j = i++) { if ( ((verty[i]>testy) != (verty[j]>testy)) && (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) ) c = !c; } return c; }

Another, from http://www.wildbunny.co.uk/blog/2012/03/29/fun-with-convex-polygons/ :

public function Within( localP:Vector2 ):Boolean { for ( var i:int = 0; i<m_numPoints; i++ ) { var A:Vector2 = m_localSpacePoints[(i+1)%m_numPoints].Sub( m_localSpacePoints[i] ); var B:Vector2 = localP.Sub( m_localSpacePoints[i] );   if ( A.Wedge( B )<0 ) { // separating axis return false; } }   return true; }

Thanks!

Replies(13)

calsign

Re: Hit test (point in polygon) algorithm for complex polygons

1 year ago

Really?
I got the following example (not much point, but it uses PGraphics) to work both in Processing 2.0a6's JavaScript mode and in Processing.js via OpenProcessing:

PGraphics pg;
void setup() {
size(250, 250);
pg = createGraphics(200, 200, JAVA2D);
}
void draw() {
background(255);
pg.beginDraw();
pg.background(253);
pg.rect(mouseX - 25, mouseY - 25, 20, 20);
pg.endDraw();
image(pg, 25, 25);
}

cingraham

Re: Hit test (point in polygon) algorithm for complex polygons

1 year ago

Sorry, I realize I should have been more specific about the PGraphics issue. Drawing an offscreen buffer works in pjs, but *not* when rendering shapes from an SVG file. Here's a relevant ticket from the pjs bug tracker: https://processing-js.lighthouseapp.com/projects/41284/tickets/1777-offscreen-drawing-of-pshape-fail

Hence, the interest in a solution that doesn't involve color-picking:) Thanks again.

calsign

Re: Hit test (point in polygon) algorithm for complex polygons

1 year ago

I was going to suggest AWT's Polygon class, only to find it incompatible with Processing.js...
That's the trick...

Check out this post... specifically, from Moggach:

boolean pixelInPoly(PVector[] verts, PVector pos) {
int i, j;
boolean c=false;
int sides = verts.length;
for (i=0,j=sides-1;i<sides;j=i++) {
if (( ((verts[i].y <= pos.y) && (pos.y < verts[j].y)) || ((verts[j].y <= pos.y) && (pos.y < verts[i].y))) &&
(pos.x < (verts[j].x - verts[i].x) * (pos.y - verts[i].y) / (verts[j].y - verts[i].y) + verts[i].x)) {
c = !c;
}
}
return c;
}

I haven't tested it, but other people said that it worked...

Funny, I searched a broad scope including the keyword "java", yet this still came up...

cingraham

Re: Hit test (point in polygon) algorithm for complex polygons

1 year ago

Thanks! Would this work with an svg file loaded using PShape? It looks like it requires access to the vertices of the polygon -- can we do that with an .svg? Simplified version of my code is below ("Table" is just Ben Fry's table parser).

PShape USMap;

PShape state;

Table data;

void setup() {
size(600, 400);
USMap = loadShape("usmap.svg");
data = new Table("random.tsv");
smooth();
}
void draw() {
USMap.disableStyle();
int rowCount = data.getRowCount();
for (int row = 0; row < rowCount; row++) {
String abbrev = data.getRowName(row);
state = USMap.getChild(abbrev);
stroke(255);
fill(0);
shape(state, 0, 0);
}
}
}

calsign

Re: Hit test (point in polygon) algorithm for complex polygons

1 year ago

Actually, this approach will only work if the shape is a simple polygon (no curves or fancy SVG stuff)...
But, you can access the shape's vertices with getVertex() (for one vertex)...

To generate an array of PVectors containing the vertices of the shape for use in your code (untested...):

PVector[] getVertices(PShape shape) {
PVector[] vertices = new PVector[shape.getVertexCount()];
for(int i = 0; i < shape.getVertexCount(); i ++) vertices[i] = shape.getVertex(i);
return vertices;
}

cingraham

Re: Hit test (point in polygon) algorithm for complex polygons

1 year ago

I think I'm making some progress here -- I'm able to access a given state's vertices using getVertexCount(), getVertexX(), and getVertexY(). So for example, if I replace line 20 in the above code with the snippet below, I can get access to what I'm pretty sure are the X and Y coordinates of all the vertices of a given state.

Still trying to figure out A) how to work the hit test algorithm into this framework and B) whether the functions I mention above are valid in Processing.js -- any ideas?

shape(state, 0, 0);
int numchildren = state.getVertexCount();
for (int i = 0; i < numchildren; i++) {
float x = state.getVertexX(i);
float y = state.getVertexY(i);
}

calsign

Re: Re: Hit test (point in polygon) algorithm for complex polygons

1 year ago

I simplified this approach in my above code by using getVertex(), which returns a PVector directly.
And, yes... if you can use PShape is Processing.js, you can use all of these functions, as well.

cingraham

Re: Hit test (point in polygon) algorithm for complex polygons

1 year ago

Oops, didn't see your reply before I responded -- let me take a look at your code and get back to you...

cingraham

Re: Hit test (point in polygon) algorithm for complex polygons

1 year ago

Okay got it -- so actually the two snippets we posted do basically the same thing -- your method returns a simple two-item array for each vertex, with the first item in each array being the X coordinate and the second being the Y coordinate (FYI, "vertices" in your example needs to be an array of floats, not an array of PVectors, in order for it to work, otherwise I get "cannot convert from float[] to PVector[]"). Mine returns separate values for the X and Y coordinates.

So the question becomes: How do I use these values in a hit-test algorithm? Sorry if I'm being a total nub-cake about this, still relatively new to the whole coding thing...

calsign

Re: Hit test (point in polygon) algorithm for complex polygons

1 year ago

Sorry about my code, the reference must not be documented properly... the below code works:

PVector[] getVertices(PShape shape) {
PVector[] vertices = new PVector[shape.getVertexCount()];
for(int i = 0; i < shape.getVertexCount(); i ++) vertices[i] = new PVector(shape.getVertex(i)[0], shape.getVertex(i)[1]);
return vertices;
}

Basically, to implement mouse over detection, you need to call the pixelInPoly() function I provided above, giving the result of getVertices() as the first parameter and new PVector(0, 0) as the second.

It would look like this:

if(mousePressed && pixelInPoly(getVertices(state), new PVector(0, 0)) {
//The mouse is pressed inside the shape
}

cingraham

Re: Hit test (point in polygon) algorithm for complex polygons

1 year ago

So, bad news: getVertices(), getVertexCount() and the like are not supported in processing.js. They throw

Uncaught TypeError: Object #<Object> has no method 'getVertexCount'

I'll check in with the processing.js guys to see if there's a workaround, but I doubt it.

So, here's my question: would it be possible/feasible to store the vertices in say, a csv file instead of svg, and then manually draw the shapes using beginShape() endShape()? Then I'd theoretically have access to the vertices without having to rely on getVertices().

If this were the case, would I be able to do things like scale and translate (pan and zoom, basically) and still retain the mouseover functionality?

calsign

Re: Hit test (point in polygon) algorithm for complex polygons

1 year ago

Okay... the real problem with Processing.js is that you can't load external files.
Also, your SVG file has to be formatted properly for getVertexCount() to work...

For your questions, yes and yes. All around, this would be a good approach, as long as you have a way of getting the data into the Processing.js application.

cingraham

Re: Hit test (point in polygon) algorithm for complex polygons

1 year ago

Cool, I'll give that a whirl and see what happens.

I can load external files fine in pjs -- I've done several projects that involved displaying an .svg file and overlaying data on it from a .csv. I simply reference the files as I normally would, as the whole "preload" thing is completely bewildering, never works right, and seems to be unnecessary.

The getVertexCount() works fine for me in regular Processing, so I know that wasn't an issue.

All in all, the lack of a more robust mouseover function is one of the more frustrating things about working with Processing/pjs. All of Processing's "competitors" in the online datavis space (d3, Raphael, Actionscript(ugh)) have one, which makes interactive choropleth maps a snap.

I do appreciate all your help -- many thanks.

Top Reply