# [math] Polygon Difference Question

9 messages
Open this post in threaded view
|

## [math] Polygon Difference Question

 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? 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().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: [hidden email] For additional commands, e-mail: [hidden email] inner_ccw.csv (11K) Download Attachment src_ccw.csv (87K) Download Attachment
Open this post in threaded view
|

## Re: [math] Polygon Difference Question

 Below is a simpler example.  Here, set2 is a polygon completely encompassed by the set1 polygon.  Yet the difference function produces a single polygon that doesn't seem to be a difference in any sense that I can understand.  How are the verticies of a polygon suppose to be interpreted? Thanks, Curtis     public void testdifferenceWithHole() {         Vector2D[][] vertices1 = new Vector2D[][] {         new Vector2D[] {                     new Vector2D(-7.2, 3.1),                     new Vector2D(-7.2, 0.1),                     new Vector2D(-4.2, 0.1),                     new Vector2D(-4.2, 3.1)                 }             };     PolygonsSet set1 = buildSet(vertices1);         Vector2D[][] vertices2 = new Vector2D[][] {         new Vector2D[] {                     new Vector2D(-5.7, 1.6),                     new Vector2D(-4.0, 1.0),                     new Vector2D(-4.0, 2.0)                 }             };     PolygonsSet set2 = buildSet(vertices2);         PolygonsSet setDiff  = (PolygonsSet) new RegionFactory().difference(set1.copySelf(), set2.copySelf());     Vector2D[][] diffVerts = setDiff.getVertices();     for (int i = 0; i < diffVerts.length; i++) {     System.out.println("Verts: " + i);         Vector2D[] set = diffVerts[i];         for (Vector2D vertex : set) {         System.out.println("\t" + vertex);         }         }     } On Fri, Aug 26, 2011 at 11:41 AM, Curtis Jensen <[hidden email]> wrote: > 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? > > 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().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: [hidden email] For additional commands, e-mail: [hidden email]
Open this post in threaded view
|

## Re: [math] Polygon Difference Question

 Le 07/09/2011 00:02, Curtis Jensen a écrit : > Below is a simpler example.  Here, set2 is a polygon completely > encompassed by the set1 polygon.  Yet the difference function produces > a single polygon that doesn't seem to be a difference in any sense > that I can understand.  How are the verticies of a polygon suppose to > be interpreted? Sorry not to answer as fast as I want, I am a little busy. I did not find the time yet to look at your example (only looked at the polygons files you provided, not how [math] handles them). Vertices have their straightforward meaning in [math]. However, the underlying representation is BSP tree, and vertices are only a converted representation. There may well be bugs in this conversion step. One way to see if the underlying representation (i.e. the BSP tree) is good is to generate a fine grained grid of points (xi, yi) and to use the checkPoint method from the top level Region class to see which points are inside and which points are outside. This could be a first step understanding where the problem lies. I'll try to have a look at this later on, I am sorry for the delay. Luc > > Thanks, > Curtis > > >      public void testdifferenceWithHole() { >       >       Vector2D[][] vertices1 = new Vector2D[][] { >           new Vector2D[] { >                      new Vector2D(-7.2, 3.1), >                      new Vector2D(-7.2, 0.1), >                      new Vector2D(-4.2, 0.1), >                      new Vector2D(-4.2, 3.1) >                  } >              }; >       PolygonsSet set1 = buildSet(vertices1); >       >       Vector2D[][] vertices2 = new Vector2D[][] { >           new Vector2D[] { >                      new Vector2D(-5.7, 1.6), >                      new Vector2D(-4.0, 1.0), >                      new Vector2D(-4.0, 2.0) >                  } >              }; >       PolygonsSet set2 = buildSet(vertices2); >       >       PolygonsSet setDiff  = (PolygonsSet) new > RegionFactory().difference(set1.copySelf(), > set2.copySelf()); >       Vector2D[][] diffVerts = setDiff.getVertices(); >       for (int i = 0; i<  diffVerts.length; i++) { >       System.out.println("Verts: " + i); >       >       Vector2D[] set = diffVerts[i]; >           for (Vector2D vertex : set) { >           System.out.println("\t" + vertex); >           } >          } >      } > > > On Fri, Aug 26, 2011 at 11:41 AM, Curtis Jensen<[hidden email]>  wrote: >> 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? >> >> 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().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: [hidden email] > For additional commands, e-mail: [hidden email] > > --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email]
Open this post in threaded view
|

## Re: [math] Polygon Difference Question

 In reply to this post by Curtis Jensen-2 Le 07/09/2011 00:02, Curtis Jensen a écrit : > Below is a simpler example.  Here, set2 is a polygon completely > encompassed by the set1 polygon.  Yet the difference function produces > a single polygon that doesn't seem to be a difference in any sense > that I can understand.  How are the verticies of a polygon suppose to > be interpreted? Using these values, I see set1 as a square and set2 as a triangle which overlaps set1 right boundary. that is to say it is partly inside set1 and partly outside set1 (for the part with x lying between -4.2 and -4.0). So the resulting polygon with one simply connected boundary which look like a dented square seems fine to me. The boundary vertices I get are: -7.2 0.10000000000000002 -4.2 0.10000000000000002 -4.2 1.0705882352941176 -5.699999999999999 1.5999999999999996 -4.2 1.9529411764705877 -4.2 3.1 -7.199999999999999 3.1000000000000005 I also tried to truncate the triangle to the right by changing the abscissas of the last to points from -4.0 to -4.3 so the triangle lies completely inside the square also gives a result I would consider correct: two loops defining a square with a triangular hole. What result do you get ? Luc > > Thanks, > Curtis > > >      public void testdifferenceWithHole() { >       >       Vector2D[][] vertices1 = new Vector2D[][] { >           new Vector2D[] { >                      new Vector2D(-7.2, 3.1), >                      new Vector2D(-7.2, 0.1), >                      new Vector2D(-4.2, 0.1), >                      new Vector2D(-4.2, 3.1) >                  } >              }; >       PolygonsSet set1 = buildSet(vertices1); >       >       Vector2D[][] vertices2 = new Vector2D[][] { >           new Vector2D[] { >                      new Vector2D(-5.7, 1.6), >                      new Vector2D(-4.0, 1.0), >                      new Vector2D(-4.0, 2.0) >                  } >              }; >       PolygonsSet set2 = buildSet(vertices2); >       >       PolygonsSet setDiff  = (PolygonsSet) new > RegionFactory().difference(set1.copySelf(), > set2.copySelf()); >       Vector2D[][] diffVerts = setDiff.getVertices(); >       for (int i = 0; i<  diffVerts.length; i++) { >       System.out.println("Verts: " + i); >       >       Vector2D[] set = diffVerts[i]; >           for (Vector2D vertex : set) { >           System.out.println("\t" + vertex); >           } >          } >      } > > > On Fri, Aug 26, 2011 at 11:41 AM, Curtis Jensen<[hidden email]>  wrote: >> 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? >> >> 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().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: [hidden email] > For additional commands, e-mail: [hidden email] > > --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email]
Open this post in threaded view
|

## Re: [math] Polygon Difference Question

Open this post in threaded view
|

## RE: [math] Polygon Difference Question

Open this post in threaded view
|

## Re: [math] Polygon Difference Question

 In reply to this post by Luc Maisonobe Ooopps, I got my signs mixed up when trying to make a simple example. This example works as expected even when I move the triangle completely in the square. Please disregard this example (user error). -- Curtis On Wed, Sep 7, 2011 at 12:15 PM, Luc Maisonobe <[hidden email]> wrote: > Le 07/09/2011 00:02, Curtis Jensen a écrit : >> >> Below is a simpler example.  Here, set2 is a polygon completely >> encompassed by the set1 polygon.  Yet the difference function produces >> a single polygon that doesn't seem to be a difference in any sense >> that I can understand.  How are the verticies of a polygon suppose to >> be interpreted? > > Using these values, I see set1 as a square and set2 as a triangle which > overlaps set1 right boundary. that is to say it is partly inside set1 and > partly outside set1 (for the part with x lying between -4.2 and -4.0). > > So the resulting polygon with one simply connected boundary which look like > a dented square seems fine to me. The boundary vertices I get are: > > -7.2 0.10000000000000002 > -4.2 0.10000000000000002 > -4.2 1.0705882352941176 > -5.699999999999999 1.5999999999999996 > -4.2 1.9529411764705877 > -4.2 3.1 > -7.199999999999999 3.1000000000000005 > > > I also tried to truncate the triangle to the right by changing the abscissas > of the last to points from -4.0 to -4.3 so the triangle lies completely > inside the square also gives a result I would consider correct: two loops > defining a square with a triangular hole. > > What result do you get ? > > Luc > >> >> Thanks, >> Curtis >> >> >>     public void testdifferenceWithHole() { >> >>        Vector2D[][] vertices1 = new Vector2D[][] { >>                        new Vector2D[] { >>                     new Vector2D(-7.2, 3.1), >>                     new Vector2D(-7.2, 0.1), >>                     new Vector2D(-4.2, 0.1), >>                     new Vector2D(-4.2, 3.1) >>                 } >>             }; >>        PolygonsSet set1 = buildSet(vertices1); >> >>        Vector2D[][] vertices2 = new Vector2D[][] { >>                        new Vector2D[] { >>                     new Vector2D(-5.7, 1.6), >>                     new Vector2D(-4.0, 1.0), >>                     new Vector2D(-4.0, 2.0) >>                 } >>             }; >>        PolygonsSet set2 = buildSet(vertices2); >> >>        PolygonsSet setDiff  = (PolygonsSet) new >> RegionFactory().difference(set1.copySelf(), >> set2.copySelf()); >>        Vector2D[][] diffVerts = setDiff.getVertices(); >>        for (int i = 0; i<  diffVerts.length; i++) { >>                System.out.println("Verts: " + i); >> >>                Vector2D[] set = diffVerts[i]; >>                for (Vector2D vertex : set) { >>                        System.out.println("\t" + vertex); >>                } >>         } >>     } >> >> >> On Fri, Aug 26, 2011 at 11:41 AM, Curtis Jensen<[hidden email]> >>  wrote: >>> >>> 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? >>> >>> 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().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: [hidden email] >> For additional commands, e-mail: [hidden email] >> >> > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [hidden email] > For additional commands, e-mail: [hidden email] > > --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email]