commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Curtis Jensen <curtis.jen...@gmail.com>
Subject Re: [math] Polygon intersection vertices outside original polygon
Date Tue, 19 Jul 2011 17:42:16 GMT
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 <Luc.Maisonobe@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
>>> <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<user-unsubscribe@commons.apache.org>
>> For additional commands, e-mail: user-help@commons.apache.org
>>
>>
>>
>
> ------------------------------**------------------------------**---------
> To unsubscribe, e-mail: user-unsubscribe@commons.**apache.org<user-unsubscribe@commons.apache.org>
> For additional commands, e-mail: user-help@commons.apache.org
>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message