2

As part of a small project I'm working on I'm using the Polygon class, but I'm having difficulty with polygons that are "touching" rather than intersecting properly.

For example, in a case where I have two polygons:

Polygon a = new Polygon(new int[] {0,0,3,3}, new int[] {0,1,0,1}, 4);
Polygon b = new Polygon(new int[] {1,1,2,2}, new int[] {1,2,1,2}, 4);

I was checking each point against the other polygon using the contains method, but the code:

System.out.print(a.contains(1,1));
System.out.print(a.contains(2,1));

returns false twice.

Is there some way to detect these "just touching" polygons?

Andrew Thompson
  • 168,117
  • 40
  • 217
  • 433
Barker404
  • 29
  • 2

2 Answers2

2

If you can accept a margin of error, try polygon.intersects()

http://docs.oracle.com/javase/6/docs/api/java/awt/Polygon.html#intersects%28double,%20double,%20double,%20double%29

It takes a rectangle as an argument, but if you make the rectangle really small, you can get the same results. Other than that, it doesn't seem that the Polygon class has exactly what you want. On the other hand, I can think of very few applications where having a specified margin of error wouldn't be better...

Andrew W
  • 4,530
  • 1
  • 16
  • 16
0

I have found a solution for checking if 2 polygons intersect, even if they have no common area. I am using the math.geom2D library (http://sourceforge.net/apps/mediawiki/geom-java/index.php?title=Main_Page) for this. I personally like it as the Polygons2D class allows you to handle operations like clip, intersection and union with relative ease.

The method uses 2 SimplePolygon2D objects as input which can be constructed from your data using addVertex(Point2D point).

There are certain cases during which this method may not work but I will post more about it as soon as I find a way of tackling them.

public static boolean checkShapeAdjacency(SimplePolygon2D polygon1, SimplePolygon2D polygon2) {
    // Buffer distance. Depends on scale / data
    final float bufferDistance = 0.2f;

    if (polygon1 == polygon2) {
        return false;
    }

    List<Point2D> intersectingPoints = new ArrayList<Point2D>();

    if (polygon1.area() > 0 && polygon2.area() > 0) {

        try {
            // Make a buffer of one polygon
            CirculinearDomain2D bufferDomain = polygon1
                    .buffer(bufferDistance);
            /*               
             * Iterate through the points of the other polygon and see if they
             * are contained within the buffer
             */
            for (Point2D p : polygon2.vertices()) {
                if (bufferDomain.contains(p)) {
                    // Increase the intersecting point count
                    if (!intersectingPoints.contains(p)) {
                        intersectingPoints.add(p);
                    }
                }
            }
        } catch (Exception e) {
            // Try/Catch to avoid degenerated line exceptions (common with math.geom2d)s
            e.printStackTrace();
            return false;
        }
    }

    // Check against the number of intersecting points
    if (intersectingPoints.size() >= 2) {

        /*
         * It is safe enough to assume that with 2 intersecting points,
         * the shape are adjacent. It will not work in the case of bad
         * geometry though. There are other methods of cleaning bad
         * geometry up.
         */
        return true;
    } else if (intersectingPoints.size() == 1) {
        /*
         * It gets tricky in the case of 1 intersecting point as one line may
         * be longer than the other. Check to see if one edge is entirely
         * in the other polygon.
         */
        for (LineSegment2D edge1 : polygon1.edges()) {
            if (polygon2.distance(edge1.firstPoint()) < 0.001 
                    && polygon2.distance(edge1.lastPoint()) < 0.001
                    && edge1.length() > 1) {

                return true;
            }
        }
        for (LineSegment2D edge2 : polygon2.edges()) {
            if (polygon1.distance(edge2.firstPoint()) < 0.001 
                    && polygon1.distance(edge2.lastPoint()) < 0.001
                    && edge2.length() > 1) {

                return true;
            }
        }
        // One common point and no common edge returns false
        return false;
    } else {
        return false;
    }
}

Please let me know if you encounter any issues with this and I will address them as best as I can.

Thank you!

MikeFot
  • 11
  • 3