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 <Luc.Maisonobe@free.fr> 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
> subpolygons. 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.
>
>
> xxxxxxxxx
> 
> x
> 
> x xxxxxxxxx
>  
> x x
>  
> xxxxxxxxx
>
> 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 subregion 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, email: userunsubscribe@commons.apache.org
>> For additional commands, email: userhelp@commons.apache.org
>
>
> 
> To unsubscribe, email: userunsubscribe@commons.apache.org
> For additional commands, email: userhelp@commons.apache.org
>
>

To unsubscribe, email: userunsubscribe@commons.apache.org
For additional commands, email: userhelp@commons.apache.org
