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/07/04 23:00:39 UTC
[math] Polygon intersection vertices outside original polygon
I'm using the RegonFactory.intersection method to get the intersection of
polygons. However, I'm getting points that are outside of one of the
original polygons. See example below. Am I misinterpreting what the
intersection method does, miss-using it, or is this a bug?
Vector2D[][] vertices1 = new Vector2D[][] {
new Vector2D[] {
new Vector2D(-25.8907, 53.6079),
new Vector2D(-25.3586, 53.5214),
new Vector2D(-25.6256, 53.1507),
new Vector2D(-26.0395, 53.2562)
}
};
PolygonsSet set1 = buildSet(vertices1);
Vector2D[][] vertices2 = new Vector2D[][] {
new Vector2D[] {
new Vector2D(-25.7455, 53.3656),
new Vector2D(-25.3007, 53.2765),
new Vector2D(-25.4181, 52.9993),
new Vector2D(-25.9476, 53.0366)
}
};
PolygonsSet set2 = buildSet(vertices2);
PolygonsSet intersectionSet = (PolygonsSet) new
RegionFactory<Euclidean2D>().intersection(set1.copySelf(), set2.copySelf());
Vector2D[][] intersectionVerts = intersectionSet.getVertices();
for (Vector2D[] set : intersectionVerts) {
for (Vector2D vertex : set) {
System.out.println(vertex);
}
}
OUTPUT:
{-26.04; 53.26}
{-25.89; 53.61}
{-25.36; 53.52}
{-25.51; 53.32}
{-25.3; 53.28}
{-25.42; 53} <- OUTSIDE polygon A
{-25.72; 53.02} <- OUTSIDE polygon A
{-25.95; 53.04} <- OUTSIDE polygon A
{-25.84; 53.21}
Re: [math] Polygon intersection vertices outside original polygon
Posted by Curtis Jensen <cu...@gmail.com>.
Thanks. Changing the orientation works. I should have noticed the
orientation from the test cases. The comment about edges being in any order
did throw me off.
The only thing I can think of to make the API more simple is to have a
constructor or helper function in the PolygonSet class that creates a
PolygonSet or Edges from an array of points (or array of arrays of points),
but make the comment say that the points have to be in Counter-Clockwise
order.
--
Curtis
On Wed, Jul 13, 2011 at 6:46 AM, Luc Maisonobe <Lu...@free.fr>wrote:
> Hi Curtis,
>
> Le 05/07/2011 22:23, luc.maisonobe@free.fr a écrit :
>
>
>> ----- "Curtis Jensen"<curtis@the-jensens.org**> a écrit :
>>
>> On Mon, Jul 4, 2011 at 2:00 PM, Curtis Jensen
>>> <cu...@the-jensens.org>wrote:
>>>
>>> I'm using the RegonFactory.intersection method to get the
>>>>
>>> intersection of
>>>
>>>> polygons. However, I'm getting points that are outside of one of
>>>>
>>> the
>>>
>>>> original polygons. See example below. Am I misinterpreting what
>>>>
>>> the
>>>
>>>> intersection method does, miss-using it, or is this a bug?
>>>>
>>>
> I'm sorry for the delay.
>
> The result you get is correct. You didn't get what you expected due to
> edges orientations.
>
> As specified in the javadoc for constructor PolygonsSet(Collection<**SubHyperplane<Euclidean2D>>
> boundary), edges can be provided in any orders (i.e you get the same results
> by providing list edge1, edge2, edge3, edge4 or list edge4, edge3, edge2,
> edge1), and the interior of the polygon is defined to be on the minus side
> of edges. However, edges by themselves *are* oriented so building edge1 from
> points pair (p1, p2) is not the same as building it from points pair (p2,
> p1). The edges are instances of sublines, which themselves refer to an
> underlying Line. If you look at javadoc for the getOffset method in Line,
> you'll see that a line split the plane with the negative half plane on its
> left side (according to the direction corresponding to the pair of points
> used to build it) and the positive half plane on its right side.
>
> So basically, when you use follow edges, you turn around the polygon in
> trigonometric (i.e. counter-clockwise) orientation. Both your polygons exend
> to infinity in all directions and have a hole in their center. So the
> intersection is also an infinite polygons with a larger hole in the center.
>
> As forcing the users to take care of orientation was considered too
> difficult, a small utility has been set up: the NestedLoop class, which also
> deals with edges polygons having several separate boundary loops (i.e
> polygons that are not path-connected, or polygons with holes). This class
> uses arrays of edges and changes the orientations of all arrays *in-place*
> assuming the global polygon is not infinite. This API is really not good,
> this I would prefer to change it. In your case, you could keep your points
> just the way you built them and just add an orientation-fix layer before
> building the polygons, as follows:
>
>
> Vector2D[][] vertices1 = new Vector2D[][] {
> new Vector2D[] {
> new Vector2D(-25.8907, 53.6079),
> new Vector2D(-25.3586, 53.5214),
> new Vector2D(-25.6256, 53.1507),
> new Vector2D(-26.0395, 53.2562)
> }
> };
> NestedLoops nl1 = new NestedLoops();
> for (Vector2D[] loop : vertices1) {
> nl1.add(loop);
> }
> nl1.correctOrientation();
>
> PolygonsSet set1 = buildSet(vertices1);
> Vector2D[][] vertices2 = new Vector2D[][] {
> new Vector2D[] {
> new Vector2D(-25.7455, 53.3656),
> new Vector2D(-25.3007, 53.2765),
> new Vector2D(-25.4181, 52.9993),
> new Vector2D(-25.9476, 53.0366)
> }
> };
> NestedLoops nl2 = new NestedLoops();
> for (Vector2D[] loop : vertices2) {
> nl2.add(loop);
> }
> nl2.correctOrientation();
>
> PolygonsSet set2 = buildSet(vertices2);
> PolygonsSet intersectionSet = (PolygonsSet) new
>
> RegionFactory<Euclidean2D>().**intersection(set1.copySelf(),
> set2.copySelf());
>
> Vector2D[][] intersectionVerts = intersectionSet.getVertices();
> for (Vector2D[] set : intersectionVerts) {
> for (Vector2D vertex : set) {
> System.out.println(vertex.**getX() + " " + vertex.getY());
> }
> }
>
>
> If you have an idea how to improve the API for NestedLoops, I would be glad
> to hear about it. It should probably integrated into PolygonsSet, and it
> should not change the arrays in place but rather use separate copies.
>
> Hope this helps.
>
> Luc
>
>
>
>> I'll have a look at this in the next few days.
>>
>> Sorry for the delay.
>> Luc
>>
>>
>>>>
>>>> Vector2D[][] vertices1 = new Vector2D[][] {
>>>> new Vector2D[] {
>>>> new Vector2D(-25.8907, 53.6079),
>>>> new Vector2D(-25.3586, 53.5214),
>>>> new Vector2D(-25.6256, 53.1507),
>>>> new Vector2D(-26.0395, 53.2562)
>>>> }
>>>> };
>>>> PolygonsSet set1 = buildSet(vertices1);
>>>> Vector2D[][] vertices2 = new Vector2D[][] {
>>>> new Vector2D[] {
>>>> new Vector2D(-25.7455, 53.3656),
>>>> new Vector2D(-25.3007, 53.2765),
>>>> new Vector2D(-25.4181, 52.9993),
>>>> new Vector2D(-25.9476, 53.0366)
>>>> }
>>>> };
>>>> PolygonsSet set2 = buildSet(vertices2);
>>>> PolygonsSet intersectionSet = (PolygonsSet) new
>>>> RegionFactory<Euclidean2D>().**intersection(set1.copySelf(),
>>>>
>>> set2.copySelf());
>>>
>>>>
>>>> Vector2D[][] intersectionVerts =
>>>>
>>> intersectionSet.getVertices();
>>>
>>>> for (Vector2D[] set : intersectionVerts) {
>>>> for (Vector2D vertex : set) {
>>>> System.out.println(vertex);
>>>> }
>>>> }
>>>>
>>>>
>>>> OUTPUT:
>>>> {-26.04; 53.26}
>>>> {-25.89; 53.61}
>>>> {-25.36; 53.52}
>>>> {-25.51; 53.32}
>>>> {-25.3; 53.28}
>>>> {-25.42; 53}<- OUTSIDE polygon A
>>>> {-25.72; 53.02}<- OUTSIDE polygon A
>>>> {-25.95; 53.04}<- OUTSIDE polygon A
>>>> {-25.84; 53.21}
>>>>
>>>>
>>>
>>> I should add that the buildSet function is the same as that in the
>>> test suit
>>> of commons math:
>>> private PolygonsSet buildSet(Vector2D[][] vertices) {
>>> ArrayList<SubHyperplane<**Euclidean2D>> edges = new
>>> ArrayList<SubHyperplane<**Euclidean2D>>();
>>> for (int i = 0; i< vertices.length; ++i) {
>>> int l = vertices[i].length;
>>> for (int j = 0; j< l; ++j) {
>>> edges.add(buildSegment(**vertices[i][j], vertices[i][(j
>>> + 1) %
>>> l]));
>>> }
>>> }
>>> return new PolygonsSet(edges);
>>> }
>>>
>>
>> ------------------------------**------------------------------**---------
>> To unsubscribe, e-mail: user-unsubscribe@commons.**apache.org<us...@commons.apache.org>
>> For additional commands, e-mail: user-help@commons.apache.org
>>
>>
>>
>
> ------------------------------**------------------------------**---------
> To unsubscribe, e-mail: user-unsubscribe@commons.**apache.org<us...@commons.apache.org>
> For additional commands, e-mail: user-help@commons.apache.org
>
>
Re: [math] Polygon intersection vertices outside original polygon
Posted by Luc Maisonobe <Lu...@free.fr>.
Hi Curtis,
Le 05/07/2011 22:23, luc.maisonobe@free.fr a écrit :
>
> ----- "Curtis Jensen"<cu...@the-jensens.org> a écrit :
>
>> On Mon, Jul 4, 2011 at 2:00 PM, Curtis Jensen
>> <cu...@the-jensens.org>wrote:
>>
>>> I'm using the RegonFactory.intersection method to get the
>> intersection of
>>> polygons. However, I'm getting points that are outside of one of
>> the
>>> original polygons. See example below. Am I misinterpreting what
>> the
>>> intersection method does, miss-using it, or is this a bug?
I'm sorry for the delay.
The result you get is correct. You didn't get what you expected due to
edges orientations.
As specified in the javadoc for constructor
PolygonsSet(Collection<SubHyperplane<Euclidean2D>> boundary), edges can
be provided in any orders (i.e you get the same results by providing
list edge1, edge2, edge3, edge4 or list edge4, edge3, edge2, edge1), and
the interior of the polygon is defined to be on the minus side of edges.
However, edges by themselves *are* oriented so building edge1 from
points pair (p1, p2) is not the same as building it from points pair
(p2, p1). The edges are instances of sublines, which themselves refer to
an underlying Line. If you look at javadoc for the getOffset method in
Line, you'll see that a line split the plane with the negative half
plane on its left side (according to the direction corresponding to the
pair of points used to build it) and the positive half plane on its
right side.
So basically, when you use follow edges, you turn around the polygon in
trigonometric (i.e. counter-clockwise) orientation. Both your polygons
exend to infinity in all directions and have a hole in their center. So
the intersection is also an infinite polygons with a larger hole in the
center.
As forcing the users to take care of orientation was considered too
difficult, a small utility has been set up: the NestedLoop class, which
also deals with edges polygons having several separate boundary loops
(i.e polygons that are not path-connected, or polygons with holes). This
class uses arrays of edges and changes the orientations of all arrays
*in-place* assuming the global polygon is not infinite. This API is
really not good, this I would prefer to change it. In your case, you
could keep your points just the way you built them and just add an
orientation-fix layer before building the polygons, as follows:
Vector2D[][] vertices1 = new Vector2D[][] {
new Vector2D[] {
new Vector2D(-25.8907, 53.6079),
new Vector2D(-25.3586, 53.5214),
new Vector2D(-25.6256, 53.1507),
new Vector2D(-26.0395, 53.2562)
}
};
NestedLoops nl1 = new NestedLoops();
for (Vector2D[] loop : vertices1) {
nl1.add(loop);
}
nl1.correctOrientation();
PolygonsSet set1 = buildSet(vertices1);
Vector2D[][] vertices2 = new Vector2D[][] {
new Vector2D[] {
new Vector2D(-25.7455, 53.3656),
new Vector2D(-25.3007, 53.2765),
new Vector2D(-25.4181, 52.9993),
new Vector2D(-25.9476, 53.0366)
}
};
NestedLoops nl2 = new NestedLoops();
for (Vector2D[] loop : vertices2) {
nl2.add(loop);
}
nl2.correctOrientation();
PolygonsSet set2 = buildSet(vertices2);
PolygonsSet intersectionSet = (PolygonsSet) new
RegionFactory<Euclidean2D>().intersection(set1.copySelf(), set2.copySelf());
Vector2D[][] intersectionVerts = intersectionSet.getVertices();
for (Vector2D[] set : intersectionVerts) {
for (Vector2D vertex : set) {
System.out.println(vertex.getX() + " " + vertex.getY());
}
}
If you have an idea how to improve the API for NestedLoops, I would be
glad to hear about it. It should probably integrated into PolygonsSet,
and it should not change the arrays in place but rather use separate copies.
Hope this helps.
Luc
>
> I'll have a look at this in the next few days.
>
> Sorry for the delay.
> Luc
>
>>>
>>>
>>> Vector2D[][] vertices1 = new Vector2D[][] {
>>> new Vector2D[] {
>>> new Vector2D(-25.8907, 53.6079),
>>> new Vector2D(-25.3586, 53.5214),
>>> new Vector2D(-25.6256, 53.1507),
>>> new Vector2D(-26.0395, 53.2562)
>>> }
>>> };
>>> PolygonsSet set1 = buildSet(vertices1);
>>> Vector2D[][] vertices2 = new Vector2D[][] {
>>> new Vector2D[] {
>>> new Vector2D(-25.7455, 53.3656),
>>> new Vector2D(-25.3007, 53.2765),
>>> new Vector2D(-25.4181, 52.9993),
>>> new Vector2D(-25.9476, 53.0366)
>>> }
>>> };
>>> PolygonsSet set2 = buildSet(vertices2);
>>> PolygonsSet intersectionSet = (PolygonsSet) new
>>> RegionFactory<Euclidean2D>().intersection(set1.copySelf(),
>> set2.copySelf());
>>>
>>> Vector2D[][] intersectionVerts =
>> intersectionSet.getVertices();
>>> for (Vector2D[] set : intersectionVerts) {
>>> for (Vector2D vertex : set) {
>>> System.out.println(vertex);
>>> }
>>> }
>>>
>>>
>>> OUTPUT:
>>> {-26.04; 53.26}
>>> {-25.89; 53.61}
>>> {-25.36; 53.52}
>>> {-25.51; 53.32}
>>> {-25.3; 53.28}
>>> {-25.42; 53}<- OUTSIDE polygon A
>>> {-25.72; 53.02}<- OUTSIDE polygon A
>>> {-25.95; 53.04}<- OUTSIDE polygon A
>>> {-25.84; 53.21}
>>>
>>
>>
>> I should add that the buildSet function is the same as that in the
>> test suit
>> of commons math:
>> private PolygonsSet buildSet(Vector2D[][] vertices) {
>> ArrayList<SubHyperplane<Euclidean2D>> edges = new
>> ArrayList<SubHyperplane<Euclidean2D>>();
>> for (int i = 0; i< vertices.length; ++i) {
>> int l = vertices[i].length;
>> for (int j = 0; j< l; ++j) {
>> edges.add(buildSegment(vertices[i][j], vertices[i][(j
>> + 1) %
>> l]));
>> }
>> }
>> return new PolygonsSet(edges);
>> }
>
> ---------------------------------------------------------------------
> 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 intersection vertices outside original polygon
Posted by lu...@free.fr.
----- "Curtis Jensen" <cu...@the-jensens.org> a écrit :
> On Mon, Jul 4, 2011 at 2:00 PM, Curtis Jensen
> <cu...@the-jensens.org>wrote:
>
> > I'm using the RegonFactory.intersection method to get the
> intersection of
> > polygons. However, I'm getting points that are outside of one of
> the
> > original polygons. See example below. Am I misinterpreting what
> the
> > intersection method does, miss-using it, or is this a bug?
I'll have a look at this in the next few days.
Sorry for the delay.
Luc
> >
> >
> > Vector2D[][] vertices1 = new Vector2D[][] {
> > new Vector2D[] {
> > new Vector2D(-25.8907, 53.6079),
> > new Vector2D(-25.3586, 53.5214),
> > new Vector2D(-25.6256, 53.1507),
> > new Vector2D(-26.0395, 53.2562)
> > }
> > };
> > PolygonsSet set1 = buildSet(vertices1);
> > Vector2D[][] vertices2 = new Vector2D[][] {
> > new Vector2D[] {
> > new Vector2D(-25.7455, 53.3656),
> > new Vector2D(-25.3007, 53.2765),
> > new Vector2D(-25.4181, 52.9993),
> > new Vector2D(-25.9476, 53.0366)
> > }
> > };
> > PolygonsSet set2 = buildSet(vertices2);
> > PolygonsSet intersectionSet = (PolygonsSet) new
> > RegionFactory<Euclidean2D>().intersection(set1.copySelf(),
> set2.copySelf());
> >
> > Vector2D[][] intersectionVerts =
> intersectionSet.getVertices();
> > for (Vector2D[] set : intersectionVerts) {
> > for (Vector2D vertex : set) {
> > System.out.println(vertex);
> > }
> > }
> >
> >
> > OUTPUT:
> > {-26.04; 53.26}
> > {-25.89; 53.61}
> > {-25.36; 53.52}
> > {-25.51; 53.32}
> > {-25.3; 53.28}
> > {-25.42; 53} <- OUTSIDE polygon A
> > {-25.72; 53.02} <- OUTSIDE polygon A
> > {-25.95; 53.04} <- OUTSIDE polygon A
> > {-25.84; 53.21}
> >
>
>
> I should add that the buildSet function is the same as that in the
> test suit
> of commons math:
> private PolygonsSet buildSet(Vector2D[][] vertices) {
> ArrayList<SubHyperplane<Euclidean2D>> edges = new
> ArrayList<SubHyperplane<Euclidean2D>>();
> for (int i = 0; i < vertices.length; ++i) {
> int l = vertices[i].length;
> for (int j = 0; j < l; ++j) {
> edges.add(buildSegment(vertices[i][j], vertices[i][(j
> + 1) %
> l]));
> }
> }
> return new PolygonsSet(edges);
> }
---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
For additional commands, e-mail: user-help@commons.apache.org
Re: [math] Polygon intersection vertices outside original polygon
Posted by Curtis Jensen <cu...@the-jensens.org>.
On Mon, Jul 4, 2011 at 2:00 PM, Curtis Jensen <cu...@the-jensens.org>wrote:
> I'm using the RegonFactory.intersection method to get the intersection of
> polygons. However, I'm getting points that are outside of one of the
> original polygons. See example below. Am I misinterpreting what the
> intersection method does, miss-using it, or is this a bug?
>
>
> Vector2D[][] vertices1 = new Vector2D[][] {
> new Vector2D[] {
> new Vector2D(-25.8907, 53.6079),
> new Vector2D(-25.3586, 53.5214),
> new Vector2D(-25.6256, 53.1507),
> new Vector2D(-26.0395, 53.2562)
> }
> };
> PolygonsSet set1 = buildSet(vertices1);
> Vector2D[][] vertices2 = new Vector2D[][] {
> new Vector2D[] {
> new Vector2D(-25.7455, 53.3656),
> new Vector2D(-25.3007, 53.2765),
> new Vector2D(-25.4181, 52.9993),
> new Vector2D(-25.9476, 53.0366)
> }
> };
> PolygonsSet set2 = buildSet(vertices2);
> PolygonsSet intersectionSet = (PolygonsSet) new
> RegionFactory<Euclidean2D>().intersection(set1.copySelf(), set2.copySelf());
>
> Vector2D[][] intersectionVerts = intersectionSet.getVertices();
> for (Vector2D[] set : intersectionVerts) {
> for (Vector2D vertex : set) {
> System.out.println(vertex);
> }
> }
>
>
> OUTPUT:
> {-26.04; 53.26}
> {-25.89; 53.61}
> {-25.36; 53.52}
> {-25.51; 53.32}
> {-25.3; 53.28}
> {-25.42; 53} <- OUTSIDE polygon A
> {-25.72; 53.02} <- OUTSIDE polygon A
> {-25.95; 53.04} <- OUTSIDE polygon A
> {-25.84; 53.21}
>
I should add that the buildSet function is the same as that in the test suit
of commons math:
private PolygonsSet buildSet(Vector2D[][] vertices) {
ArrayList<SubHyperplane<Euclidean2D>> edges = new
ArrayList<SubHyperplane<Euclidean2D>>();
for (int i = 0; i < vertices.length; ++i) {
int l = vertices[i].length;
for (int j = 0; j < l; ++j) {
edges.add(buildSegment(vertices[i][j], vertices[i][(j + 1) %
l]));
}
}
return new PolygonsSet(edges);
}