You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@commons.apache.org by Curtis Jensen <cu...@the-jensens.org> on 2011/08/26 20:41:08 UTC
[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<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);
}
Re: [math] Polygon Difference Question
Posted by Curtis Jensen <cu...@gmail.com>.
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 <Lu...@free.fr> 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<Euclidean2D>().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<cu...@the-jensens.org>
>> 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<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
Re: [math] Polygon Difference Question
Posted by Luc Maisonobe <Lu...@free.fr>.
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<Euclidean2D>().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<cu...@the-jensens.org> 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<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
Re: [math] Polygon Difference Question
Posted by Curtis Jensen <cu...@the-jensens.org>.
No worries on being busy. I understand.
Thanks for the help,
Curtis
On Wed, Sep 7, 2011 at 12:50 AM, Luc Maisonobe <Lu...@free.fr> 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?
>
> 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<Euclidean2D>().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<cu...@the-jensens.org>
>> 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<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
Re: [math] Polygon Difference Question
Posted by Luc Maisonobe <Lu...@free.fr>.
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<Euclidean2D>().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<cu...@the-jensens.org> 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<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
Re: [math] Polygon Difference Question
Posted by Curtis Jensen <cu...@gmail.com>.
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<Euclidean2D>().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 <cu...@the-jensens.org> 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<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
Re: [math] Polygon Difference Question
Posted by Curtis Jensen <cu...@the-jensens.org>.
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 <Lu...@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
RE: [math] Polygon Difference Question
Posted by Andy Turner <A....@leeds.ac.uk>.
Hi
There is considerable experience with these sorts of issues from the geospatial domain. It might be worth asking for instance on the geotools or JTS java topology suite lists if they can help.
I've not looked into this, but I suspect perhaps a rounding/precision issue, or something to do with whether the boundary segment is handled as something computed as clockwise or anti-clockwise.
Best wishes,
Andy
http://www.geog.leeds.ac.uk/people/a.turner/
________________________________________
From: Luc Maisonobe [Luc.Maisonobe@free.fr]
Sent: 07 September 2011 21:20
To: Commons Users List
Subject: Re: [math] Polygon Difference Question
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
Re: [math] Polygon Difference Question
Posted by Luc Maisonobe <Lu...@free.fr>.
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