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 <[email protected]>wrote: > Hi Curtis, > > Le 05/07/2011 22:23, [email protected] a écrit : > > >> ----- "Curtis Jensen"<[email protected]**> a écrit : >> >> On Mon, Jul 4, 2011 at 2:00 PM, Curtis Jensen >>> <[email protected]>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<[email protected]> >> For additional commands, e-mail: [email protected] >> >> >> > > ------------------------------**------------------------------**--------- > To unsubscribe, e-mail: > user-unsubscribe@commons.**apache.org<[email protected]> > For additional commands, e-mail: [email protected] > >
