commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
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.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


Mime
View raw message