# Checking for a point within a 2D shape (v3.5)

Say I have a convex polygon and the coordinates of its vertices. Say I wish to check if a coordinate point is within that polygon. How do I do this without an absurd amount of rectangles?

My idea is adding the coordinate as a vertex of the polygon and then checking if a concave shape is formed. Since the polygon is convex, this method works most of the time for a point within the polygon’s edges. The only exception is when the point passes a certain distance from the polygon; then, a concave shape is still formed when the point is well beyond the border.

Share your ideas! I want to find the most efficient method possible of doing this.

This will work with any convex or concave polygon

If the point has the coordinates `[px,py]` then consider the line `[px,py]-[dx,dy]` where the point `[dx,dy]` is extremely long way from the polygon so that it is definitely outside the polygon. Now check for intersection between this line and each edge of the shape. If the number of intersections is odd then `[px,py]` is inside the polygon, if even it is outside.

1 Like

`http://JeffreyThompson.org/collision-detection/poly-point.php`

1 Like

You can cheat:

if you know the color of the polygon and it has one unique color that is different from the background (and all others polygons), use get(x,y). If the colors are the same, you are inside the polygon.

Extra tip: when your different polygons have all the same color, you can use a trick: Make an PGraphics (iirc) and draw the same polygons there (same size) but with unique colors.

Then use get() with the PGraphics and eval the unique number.

Chrisir

well well well…I’ll just resort to a circle around the polygon to fix that…

Now for something extra: Say I have an array of objects that, when I run a function on them, create the aforementioned polygons. How do I test if a point intersects with one of them?
(It must be possible to add objects to the HashMap and edit their values as well.)

use my approach

store a class polygon in the hashmap that also contains the unique number

loop over the hashmap and compare the color get(mouseX,mouseY) with the unique color of the polygon

I have multiple polygons that all need to be the same color. Plus, they change opacity throughout.
AND, I also need to exclude certain polygons.

Hello,

here is an example with unique colors. Without PGraphics.

The Sketch works like this:

• The Sketch fills Polygons in an HashMap (you could also use ArrayList) in setup().
• It displays the Polygons from the HashMap in draw().
• It checks the color where you pressed the mouse against the color of the Polygons in mousePressed(). When a color matches, the Polygon is identified (`println(p.id);`).

As I said, when they have the same color use an underlying PGraphics (where they don’t change the opacity). See Sketch below, next post.

When they have an id like in my version, you can exclude a set of IDs.

Warm regards,

Chrisir

The Sketch

``````import java.util.Map;

// Note the HashMap's "key" is a String and "value" is an Poly1
HashMap<String, Poly1> hm = new HashMap<String, Poly1>();

int globalID=0;

void setup() {

size(888, 777);
// Putting key-value pairs in the HashMap
hm.put("Ava", new Poly1());
hm.put("Cait", new Poly1());
hm.put("Casey", new Poly1());

// Using an enhanced loop to iterate over each entry
for (Map.Entry me : hm.entrySet()) {
print(me.getKey() + " is ");
println(me.getValue());
}
}

void draw() {
// We can also access values by their key
Poly1 val = hm.get("Casey");
//  println("Casey is " + val.id);

// Using an enhanced loop to iterate over each entry
for (Map.Entry me : hm.entrySet()) {
// print(me.getKey() + " is ");
// println(me.getValue());
Poly1 p = (Poly1) me.getValue();
p.display();
}//for
}

void mousePressed() {
color c1=get(mouseX, mouseY);
// Using an enhanced loop to iterate over each entry
for (Map.Entry me : hm.entrySet()) {
print(me.getKey() + " is ");
println(me.getValue());
Poly1 p = (Poly1) me.getValue();
if (p.col1==c1) {
println(p.id);
return; // leave
}
}//for
}
// ==========================================================================
class Poly1 {

color col1 = color(random(255), random(255), random(255));
PVector[]  list =  {  new PVector (random(width), random(height)),
new PVector (random(width), random(height)),
new PVector (random(width), random(height))
};

int id=globalID++;

void display() {
//
fill(col1);
beginShape();
for (PVector pv : list) {

vertex(pv.x, pv.y);
}
endShape();
}
//
}

``````

here is the example WITH PGraphics

NO unique colors visible but internal pg has unique colors

still works when you click with mouse (see println)

(no HashMap needed, ArrayList would do)

use this at end of draw() to see the pg:

``````  if (keyPressed)
image(pg, 0, 0);
``````

The Sketch

``````
import java.util.Map;

// Note the HashMap's "key" is a String and "value" is an Integer
HashMap<String, PolyClass> hm = new HashMap<String, PolyClass>();

int globalID=0;

PGraphics pg;

void setup() {

size(888, 777);

pg = createGraphics(width, height);

// Putting key-value pairs in the HashMap
hm.put("Ava", new PolyClass());
hm.put("Cait", new PolyClass());
hm.put("Casey", new PolyClass());

// Using an enhanced loop to iterate over each entry
for (Map.Entry me : hm.entrySet()) {
print(me.getKey() + " is ");
println(me.getValue());
}

pg.beginDraw();
// Using an enhanced loop to iterate over each entry
for (Map.Entry me : hm.entrySet()) {
// print(me.getKey() + " is ");
// println(me.getValue());
PolyClass p = (PolyClass) me.getValue();
p.displayOnPG();
}//for
pg.endDraw();
}

void draw() {
// We can also access values by their key
// PolyClass val = hm.get("Casey");
//  println("Casey is " + val.id);

// Using an enhanced loop to iterate over each entry
for (Map.Entry me : hm.entrySet()) {
// print(me.getKey() + " is ");
// println(me.getValue());
PolyClass p = (PolyClass) me.getValue();
p.display();
}//for
}

void mousePressed() {
color c1=pg.get(mouseX, mouseY);
// Using an enhanced loop to iterate over each entry
for (Map.Entry me : hm.entrySet()) {
PolyClass p = (PolyClass) me.getValue();
if (p.col1==c1) {
println(p.id);
return;
}//if
}//for
}
// ==========================================================================
class PolyClass {

color col1 = color(random(255), random(255), random(255));
PVector[]  list =  {  new PVector (random(width), random(height)),
new PVector (random(width), random(height)),
new PVector (random(width), random(height))
};

int id=globalID++;

void display() {
//
fill(0);
beginShape();
for (PVector pv : list) {
vertex(pv.x, pv.y);
}
endShape();
}
//

void displayOnPG() {
pg.fill(col1);
pg.beginShape();
for (PVector pv : list) {
pg.vertex(pv.x, pv.y);
}
pg.endShape();
}
//
}

``````

When i was working on a similar problem, i calculated the midpoint for each shape, then going through each of the vertices i find the maximum distance from the mid point. This way i can use a radius check using the mouse and the midpoint. If the test passes then i can test the point shape collision. If not move on and test another shapes radius. The midPoint only needs to be calculated once, providing your vertices arent changing, and if the shape is translated then you would update the midpoint based on dx and dy.

1 Like

By changing, do you mean relative location?

Yes if all the vertices are moving in the same direction with the same velocity then the max distance from the midpoint stays the same, however if only some vertices change then you just need to test those to see if they now exceed your maximum or to check if the maximum has decreased.

Here is a very simple sketch that shows how to determine whether a point is inside a concave or convex polygon.

``````PVector[] p0 = new PVector[] {  // Concave polygon
new PVector(80, 40), new PVector(60, 120), new PVector(120, 160),
new PVector(180, 60), new PVector(100, 110)
};

PVector[] p1 = new PVector[] {  // Convex polygon
new PVector(240, 80), new PVector(260, 160), new PVector(330, 180),
new PVector(360, 60), new PVector(330, 40)
};

void setup() {
size(400, 200);
cursor(CROSS);
}

void draw() {
background(255);
drawPoly(p0);
drawPoly(p1);
}

void drawPoly(PVector[] verts) {
boolean inside = isInsidePolygon(verts, mouseX, mouseY);
if (inside) {
strokeWeight(6);
stroke(200, 0, 0);
} else {
strokeWeight(3);
stroke(0, 0, 200);
}
PVector prev = verts[verts.length - 1];
for (int i = 0; i < verts.length; i++) {
PVector curr = verts[i];
line(prev.x, prev.y, curr.x, curr.y);
prev = curr;
}
}

/**
* See if the given point is inside a polygon defined by the vertices provided.
*
* @param verts the vertices of the shape
* @param x0
* @param y0
* @return true if x0, y0 is inside polygon else returns false
*/
boolean isInsidePolygon(PVector[] verts, float x0, float y0) {
boolean oddNodes = false;
for (int i = 0, j = verts.length - 1; i < verts.length; j = i, i++) {
PVector vi = verts[i];
PVector vj = verts[j];
if ((vi.y < y0 && vj.y >= y0 || vj.y < y0 && vi.y >= y0) && (vi.x + (y0 - vi.y) / (vj.y - vi.y) * (vj.x - vi.x) < x0))
oddNodes = !oddNodes;
}
return oddNodes;
}
``````

Now to store said PVector[]s inside objects and then store those in an arrayList

Do you want to store them by mouse input or just type them in your program code with fixed positions?

In my code you can see the class that holds PVector data

here is an example where you can click the mouse to add points and create shapes. Please note it works best on pc as I havent coded it to handle touchscreens.

1 Like

Easiest concept: Build normal vectors and Dot Products. But everybody does it differently. Most prefer a conplicated formula.