# commons-user mailing list archives

##### Site index · List index
Message view
Top
From Curtis Jensen <cur...@the-jensens.org>
Subject Re: [math] Polygon Difference Question
Date Fri, 09 Sep 2011 20:28:31 GMT
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
> 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: user-unsubscribe@commons.apache.org
>> For additional commands, e-mail: user-help@commons.apache.org
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
> For additional commands, e-mail: user-help@commons.apache.org
>
>

---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
For additional commands, e-mail: user-help@commons.apache.org

Mime
View raw message