# commons-user mailing list archives

##### Site index · List index
Message view
Top
From Luc Maisonobe <Luc.Maison...@free.fr>
Subject Re: [math] Polygon intersection vertices outside original polygon
Date Wed, 13 Jul 2011 13:46:38 GMT
```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
>> <curtis@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.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.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
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) {
>> + 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