Merging two polygons in Java

Question

Is there a clean Java method for merging the points of two given overlapping polygons into one polygon?

Merging the points, and I tried to run through the points individually, and check for intersects. But it was an extremely intensive task to run on a polygon with over 1000 points. — Ben Poulson, Jul 02 '12 at 08:51
@BenPoulson - I still did not understand. e.g. If you had two squares side by side, with some space in between, how would you merge them? If instead, they shared an edge, how would you merge them then? — ArjunShankar, Jul 02 '12 at 08:53
@ArjunShankar - I mentioned that the polygons where overlapping. — Ben Poulson, Jul 02 '12 at 08:56
This [Q&A](http://stackoverflow.com/q/9526835/230513) examines merging a number of triangles; I don't know how it scales. — trashgod, Jul 02 '12 at 08:57
@BenPoulson - In that case, what do you mean by 'overlap'? Shared edges? Or shared area? My point is: The question is not clear enough. Please do consider an edit. — ArjunShankar, Jul 02 '12 at 09:10

score 9 · Accepted Answer · answered Jul 02 '12 at 08:57

9

What you want is a Convex Hull Algorithm it will take a set of points and return a minimal set of points that encloses the original points. This can be done in n.log n time.

answered Jul 02 '12 at 08:57

Charles Keepax

2,392
1
18
19

Upon closer inspection, the convex hull algorithm is the correct way to be doing this. Thanks a lot. – Ben Poulson Oct 16 '13 at 15:11

Lars · Answer 2 · 2017-03-15T15:08:27.890

You can use JTS (Java Topology Suite) for that.

Create your Polygon objects
Use the union method which will return a Set of all points from both polygons

Simple code example:

Given Polygon 1 (as WKT): POLYGON ((0 0, 0 10, 10 10, 10 0, 0 0))

Given Polygon 2 (as WKT): POLYGON ((5 5, 15 5, 15 15, 5 15, 5 5))

// create polygons
Polygon p1 = new GeometryFactory().createPolygon(new Coordinate[]{new Coordinate(0, 0), new Coordinate(0,10), new Coordinate(10,10), new Coordinate(10,0), new Coordinate(0,0)});
Polygon p2 = new GeometryFactory().createPolygon(new Coordinate[]{new Coordinate(5,5), new Coordinate(15,5), new Coordinate(15,15), new Coordinate(5,15), new Coordinate(5,5)});
// calculate union
Geometry union = p1.union(p2);
// print as WKT
System.out.println(union.toText());

The result is a new polygon:

POLYGON ((0 0, 0 10, 5 10, 5 15, 15 15, 15 5, 10 5, 10 0, 0 0))

Thanks for this answer! Unfortunately while using this method to combine polygons, if you have polygons placed in a circular manner, the JTS really does not like that and won't overlay/union them properly. I'm not sure if I'm just doing something wrong, though. — FireController1847, Dec 18 '20 at 22:17

score 6 · Answer 3 · answered Mar 15 '13 at 14:01

6

The Area class supports addition of closed polygons.

answered Mar 15 '13 at 14:01

gmjonker

99
2
2

1

Upvoting this. Combining polygons means you have to be edge-aware, and convex hull algorithms typically just look at points. If you look at the [Area.add() javadoc](http://docs.oracle.com/javase/7/docs/api/java/awt/geom/Area.html#add(java.awt.geom.Area)), a convex hull algorithm would just produce a rectangle. – mwoodman Dec 14 '15 at 20:29

score 6 · Answer 4 · answered Oct 14 '15 at 22:28

6

Convex Hull is different from adding. Adding means making a polygon that looks like the two polygons overlapped which is not necessarily convex.

answered Oct 14 '15 at 22:28

user1712200

329
5
8

score 1 · Answer 5 · answered Mar 03 '22 at 21:12

Using the algorithm @Charles Keepax provided, you can do something like this:

public static Polygon mergePolygons(Polygon a, Polygon b) {
    // create arrays for border of each polygon
    Point[] a_pts = new Point[a.npoints];
    Point[] b_pts = new Point[b.npoints];
    // fill them in an array of Points instead of separate coords.
    Arrays.setAll(a_pts, i -> new Point(a.xpoints[i], a.ypoints[i]));
    Arrays.setAll(b_pts, i -> new Point(b.xpoints[i], b.ypoints[i]));
    // first merge 2 arrays into 1
    Point[] all_pts = (Point[]) mergeArrays(a_pts, b_pts);
    // apply Convex Hull on resulting array
    convexHull(all_pts, all_pts.length);

    // separate x and y coordinates back 
    int[] x_pts = new int[all_pts.length];
    int[] y_pts = new int[all_pts.length];
    Arrays.setAll(x_pts, i -> all_pts[i].x);
    Arrays.setAll(y_pts, i -> all_pts[i].y);
    // return polygon object using those coordinates
    return new Polygon(x_pts, y_pts, all_pts.length);
}

But of course solution by @Lars is more practical, this is how you could do it in a naive way.

Merging two polygons in Java

5 Answers5