Calculate if an object is inside a set of coordinates?

Question

I have a set of X and Y points that builds a shape and I need to know if an object is inside it or not what is the calculation to it ?

X and Y coords example:

522.56055 2389.885
544.96 2386.3406
554.18616 2369.2385
535.21814 2351.396
497.5552 2355.8396

I am not really good with math :( so i would appreciate some support to understand how it is done.

Example of what I have so far but doesnt seem very reliable:

private boolean isInsideShape(Zone verifyZone, Position object)
{
    int corners = verifyZone.getCorners();
    float[] xCoords = verifyZone.getxCoordinates();
    float[] yCoords = verifyZone.getyCoordinates();

    float x = object.getX();
    float y = object.getY();
    float z = object.getZ();

    int i, j = corners - 1;
    boolean inside = false;

    for(i = 0; i < corners; i++)
    {
        if(yCoords[i] < y && yCoords[j] >= y || yCoords[j] < y && yCoords[i] >= y)
            if(xCoords[i] + (y - yCoords[i]) / (yCoords[j] - yCoords[i]) * (xCoords[j] - xCoords[i]) < x)
                inside = !inside;
        j = i;
    }

    return inside;
}

Not that simple, think about the cases negative for latitude and longitude and special case the box cover equator at longitude 0. Try to use the existing library. — AustinTX, Aug 20 '19 at 20:15

Andrey Adamovich · Accepted Answer · 2011-03-03T07:55:24.090

44

You may start from this: http://en.wikipedia.org/wiki/Point_in_polygon

You also might look into JTS Topology Suite. And in particular use this function.

EDIT: Here is example using JTS:

import java.util.ArrayList;

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.LinearRing;
import com.vividsolutions.jts.geom.Point;
import com.vividsolutions.jts.geom.Polygon;
import com.vividsolutions.jts.geom.impl.CoordinateArraySequence;

public class GeoTest {

  public static void main(final String[] args) {

    final GeometryFactory gf = new GeometryFactory();

    final ArrayList<Coordinate> points = new ArrayList<Coordinate>();
    points.add(new Coordinate(-10, -10));
    points.add(new Coordinate(-10, 10));
    points.add(new Coordinate(10, 10));
    points.add(new Coordinate(10, -10));
    points.add(new Coordinate(-10, -10));
    final Polygon polygon = gf.createPolygon(new LinearRing(new CoordinateArraySequence(points
        .toArray(new Coordinate[points.size()])), gf), null);

    final Coordinate coord = new Coordinate(0, 0);
    final Point point = gf.createPoint(coord);

    System.out.println(point.within(polygon));

  }

}

Here is example using AWT (which is simpler and is part of Java SE):

import java.awt.Polygon;

public class JavaTest {

  public static void main(final String[] args) {

    final Polygon polygon = new Polygon();
    polygon.addPoint(-10, -10);
    polygon.addPoint(-10, 10);
    polygon.addPoint(10, 10);
    polygon.addPoint(10, -10);

    System.out.println(polygon.contains(0, 0));

  }

}

edited Mar 03 '11 at 07:55

answered Mar 03 '11 at 00:31

Andrey Adamovich

20,285
14
94
132

I have updated the question with an example of what I have I am totally bad with understanding math/geo by reading it It is easier for me to understand with pratical code ;( – Prix Mar 03 '11 at 02:07
thanks for taking the time compared to what I was doing it is incredible easier that way, really appreciate your help. – Prix Mar 03 '11 at 10:10
`that way`, from the examples you showed, just to clarify hehehe – Prix Mar 03 '11 at 10:18
i used this in java SE and android both.work perfectly in SE but Runtime error in android Could not find class 'com.vividsolutions.jts.geom.GeometryFactory', referenced from method ceylon.linux.geofencepolygon.MainActivity.runrun – Lahiru Prasanna Jun 27 '14 at 07:40
I don't think android supports awt classes – Andrey Adamovich Jun 27 '14 at 09:09
Old question, but since this has just bitten me: Note that for `within` and `contains`, as the JavaDoc says, "The boundary of a Geometry is not within the Geometry". If you want to check including the boundary, use `covers` instead of `contains` and `coveredBy` instead of `within`. – Dario Seidl Mar 22 '18 at 11:58

score 1 · Answer 2 · answered Mar 03 '11 at 00:56

1

I've always done it like so:

Pick a point you know to be outside the shape.
Make a line between that point and the point you're trying to find whether it's inside the shape or not.
Count the number of sides of the shape the line crosses. 

If the count is odd, the point is inside the shape.
If the count is even, the point is outside the shape.

answered Mar 03 '11 at 00:56

corsiKa

81,495
25
153
204

3

This only works if the polygon is simple, and does not intersect with itself http://en.wikipedia.org/wiki/Point_in_polygon – benathon Jan 03 '14 at 09:44
of course and therefore all or nearly all src code only deals with simple polygons. – AlexWien Jun 22 '16 at 19:32

Calculate if an object is inside a set of coordinates?

2 Answers2

Linked