I'll work on creating a better simple example and see if I can figure out what is going on. I'll submit to Jira when I get something simple.
Thanks, Curtis On Wed, Sep 7, 2011 at 1:20 PM, Luc Maisonobe <[email protected]> wrote: > 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 vertices. > > > x-x-x-x-x-x-x-x-x > | > x > | > x x-x-x-x-x-x-x-x-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. > > Luc > >> >> 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: [email protected] >> For additional commands, e-mail: [email protected] > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [email protected] > For additional commands, e-mail: [email protected] > > --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
