How to check if a 2d point is inside a 2D polygon in Java?

Question

In my Java application I'm creating 2D polygons using an array of vertices. For example, I want to create a simple square using these 4 vertices

[-130, -74], [-125, -74], [-125, -70], [-130, -70]

Then I want to check if a point is inside the generated Polygon. But if I check, for example, this point

[-125, -73]

using polygon.contains(x, z) it says is not inside the Polygon. Even if I check a corner, like [-125, -74] is returns false. The strange part for me is that is I check this point [-126, -74] is returns true, so some points are actually seen as inside the polygon, while others are not, and I can't understand why is it. This is a sample code I set up to test this, nothing special about it

public static void main(String[] args) {
   Polygon polygon = new Polygon(new int[]{-130, -125, -125, -130}, new int[]{-74, -74, -70, -70}, 4);
   System.out.println("" + polygon.contains(-125, -73));
   System.out.println("" + polygon.contains(-125, -74));
   System.out.println("" + polygon.contains(-126, -74));
}

And the output as well

false
false
true

I would also point out the fact that this is just a simple example, but the Polygon could be a really complex shape, for example something crazy like this

this could help you: https://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon — AlphaConqueror, Jul 23 '20 at 22:16
You should use [java.awt.Polygon](https://download.java.net/java/GA/jdk14/docs/api/java.desktop/java/awt/Polygon.html) and [Polygon.contains(int, int)](https://download.java.net/java/GA/jdk14/docs/api/java.desktop/java/awt/Polygon.html#contains(int,int)). — , Jul 23 '20 at 22:21
@AlphaConqueror Thank you, I'll check that answer and see if I can implement the ray casting algorithm — Jimi, Jul 23 '20 at 22:23

score 2 · Answer 1 · 2020-07-24T12:00:05.223

The document Polygon says

This Polygon is defined with an even-odd winding rule. See WIND_EVEN_ODD for a definition of the even-odd winding rule.

WIND_EVEN_ODD
The winding rule constant for specifying an even-odd rule for determining the interior of a path. The even-odd rule specifies that a point lies inside the path if a ray drawn in any direction from that point to infinity is crossed by path segments an odd number of times.

So you can do like this.

static Polygon mirror(Polygon p) {
    int npoints = p.npoints;
    int[] xpoints = new int[npoints];
    int[] ypoints = new int[npoints];
    for (int i = 0; i < npoints; ++i) {
        xpoints[i] = -p.xpoints[i];
        ypoints[i] = -p.ypoints[i];
    }
    return new Polygon(xpoints, ypoints, npoints);
}

static boolean onVertex(Polygon p, int x, int y) {
    int npoints = p.npoints;
    for (int i = 0; i < npoints; ++i)
        if (p.xpoints[i] == x && p.ypoints[i] == y)
            return true;
    return false;
}

static boolean contains(Polygon p, int x, int y) {
    return p.contains(x, y)
        || onVertex(p, x, y)
        || mirror(p).contains(-x, -y);
}

And

Polygon polygon = new Polygon(new int[]{-130, -125, -125, -130}, new int[]{-74, -74, -70, -70}, 4);
System.out.println("" + contains(polygon, -125, -73));
System.out.println("" + contains(polygon, -125, -74));
System.out.println("" + contains(polygon, -126, -74));

output:

true
true
true

A test for a polygon with a hole.

int width = 100, height = 100;
BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
int[] xs = {20, 80, 80, 20, 20, 40, 60, 60, 40, 40};
int[] ys = {20, 20, 80, 80, 20, 40, 40, 60, 60, 40};
Polygon p = new Polygon(xs, ys, xs.length);
Graphics2D g = image.createGraphics();
try (Closeable c = () -> g.dispose()) {
    g.setColor(Color.WHITE);
    g.fillRect(0, 0, width, height);
    g.setColor(Color.BLACK);
    g.drawPolygon(p);
    g.setColor(Color.RED);
    for (int x = 0; x < width; ++x)
        for (int y = 0; y < height; ++y)
            if (contains(p, x, y))
                g.fillRect(x, y, 1, 1);
}
ImageIO.write(image, "png", new File("data/testPolygon.png"));

output

If contains(p, x, y) -> p.contains(x, y) then

I've tested this solution but it only seems to work with polygons that has no holes in it. For instance, suppose you have a situation like this https://imgur.com/3BVCiXo If you check a point that is "inside the inner square" (so infact is outside the polygon) it returns true, while other points inside the outer square returns false — Jimi, Jul 24 '20 at 10:36

score 1 · Answer 2 · answered Jul 23 '20 at 22:26

1

Shoot a ray from point P(x, y) and count for intersection with the edges, if intersection count is odd, then P is inside polygon.

However if ray intersects with one of the vertices it might be difficult to determine intersection point due to rounding problem. Therefore you may follow these steps:

Shoot a ray in any direction, such that the ray does not directly hit any vertices.
For each edge in polygon determine whether the ray intersects the edge, if yes - increase counter
After all edges have been checked, P inside if intersection counter is odd.

https://en.wikipedia.org/wiki/Point_in_polygon

answered Jul 23 '20 at 22:26

eparvan

1,639
1
15
26

I saw this solution in the AlphaConqueror comment as well. Seems like this could work, just note that I'm using int for coordinates, so I think that rounding problems shouldn't occur. But I still wonder why it seems there is no "vanilla" way for testing this, because I think is a common problem when dealing with polygons – Jimi Jul 23 '20 at 22:30
1

Even with `int` values you need to use division to determine intersection point. It could lead to non-integer numbers and if you convert the number back to integer it could lead to an inaccurate result. – eparvan Jul 23 '20 at 22:39

How to check if a 2d point is inside a 2D polygon in Java?

2 Answers2