commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Luc Maisonobe <>
Subject Re: [math] Polygon Difference Question
Date Wed, 07 Sep 2011 20:20:25 GMT
Le 26/08/2011 20:41, Curtis Jensen a écrit :
> Using math 3.0, I have two polygons with many points.  One is
> completely contained within the other.  When I do a difference on the
> two, I expected to get a polygon with a hole in it.  However, I get 86
> polygons, that roughly make up a polygon with a hole in it.  If I
> scale the points by a factor of 0.1, I get 7 polygons, and if I scale
> it differently in the two directions, I get a different number of
> polygons.  Sometimes the resultant polygons don't seem to make a shape
> resembling a polygon with a hole in it.
> How should I interpret the results of the difference method?  i.e. How
> do I process the 86 or 7 or however many polygons so that it resembles
> 1 polygon with 1 hole in it?

I finally had a look at this.
It seems when the outer polygon is built, it is already split in many 
sub-polygons. There are many tiny artefacts throughout the plane. This 
can be seen by reading the polygon and immediately retrieving its 
boundary. The retrieved boundary is not equal to the initial one!

As an example, you can zoom in the rectangle ranging from -10.4346 to 
-10.4344 along x and from 10.6585 to 10.6587 along y. In the original 
boundary from src_ccw.csv file, the boundary goes roughly from upper 
right to lower left of this small rectangle, with an almost rectangular 
dent in the middle. The retrieved boundary dos not have this dent but 
instead has a long boundary from upper right to lower left, and about 
four almost infinitely thin separate polygons at the dent bottom.

So their is at least a bug in the building routine. Given the very 
complex nature of this boundary, I don't know how to identify the bug 
and solve it. Here is what I think now:

We have a boundary defined by many points, most of them being aligned 
with their neighbors as depicted in the ASCII art below, where thew 
characters represent vertices and '-' and '|' represent edges between 

                   x               x-x-x-x-x-x-x-x-x
                   |               |
                   x               x
                   |               |

We use each edge to define a line, and build the BSP tree by computing 
the intersection of these lines. Here, the intersections of the top 
horizontal edges are *really* difficult to compute as they are parallel.

This is a very difficult problem because the BSP representation is 
really different from the boundary representation we start from. We 
don't ask about the connectivity of the edges (mainly because we don't 
know how to handle it ...), and in this case this lead the algorithm to 
fail miserably :-(

Could you open a Jira issue with a reduced points set reproducing a 
similar behavior (say a single polygon with less than 50 points, which 
could simply be a chopped sub-region of this one) ?

Do you have some clever idea to use connectivity information to help 
build the set (perhaps by trying to eliminate redundant intermediate 
points) ?

I guess this bug will be difficult to solve.


> Thanks,
> Curtis
> Attached are two csv files with the points in CCW order.  Also
> attached is a plot of the points in the two files.  Below is code I
> added to the org.apache.commons.math.geometry.euclidean.twod.PolygonsSetTest
> class to test with (It uses the Apache Common FileUtils too)
>     @Test
>      public void testDifferenceManyPoints() throws IOException {
>      	PolygonsSet set1 = csv2set(new File("src_ccw.csv"));
>      	PolygonsSet set2 = csv2set(new File("inner_ccw.csv"));
>      	PolygonsSet set  = (PolygonsSet) new
> RegionFactory<Euclidean2D>().difference(set1.copySelf(),
> set2.copySelf());
>      	Vector2D[][] verts = set.getVertices();
>      	System.out.println(verts.length);
>      }
>      private PolygonsSet csv2set(File file) throws IOException {
> 		List linesObj = FileUtils.readLines(file);
> 		Vector2D[][] verts = new Vector2D[1][linesObj.size()];
> 		for (int i = 0; i<  linesObj.size(); i++) {
> 			String line = (String)linesObj.get(i);
> 			String[] tokens = line.split(",");
> 			double x = Double.valueOf(tokens[0]);
> 			double y = Double.valueOf(tokens[1]);
> 			verts[0][i] = new Vector2D(x, y);
> 		}
> 		return buildSet(verts);
> 	}
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message