Hi Larry, Thanks for clarification (my english is not so good, and I often need a detailed explanation to grasp the problem)
I think your approach is the good one as the problem we want to solve is much more specific than the one I tried to solve in my GeoConcept parser. Try to sum up different hypothesis which are done about the shapefile input and the way to handle them 1) Polygon may have multiple outer rings Are rings described between two consecutive outer rings supposed to represent holes in the first polygon ? shapefile specification says : The order of rings in the points array is not significant. 1a) if one suppose that holes of P1 follow P1 outer ring description, one can process polygons one after the other, 1b) if one suppose that a hole in P1 may be described after the outer ring of P2 (hum, hope this does not occur in shapefile despite the lack of specification), one have to test relations between all pairs or so 2) Holes may be described in CCW or CW (polygons with CW holes are described as dirty in the spec, but this is the problem we want to solve) Depending on hypothesis 1, one have to test inclusion of current ring in the previous polygon or inclusion of the current ring in any previous polygon I think it is necessary to test inclusion of the current ring in the ongoing polygon and not only in the previous outer ring to differentiate a hole from a island inside a hole. 3) Overlapping polygons (specification says that it is not authorized : "Has no self-intersections") If one consider that the entry polygon has no self intersection, I think at least two "point in polygon" test have to be done to know if the CW polygon is a hole or an outer ring, because a hole can touch the outer ring but cannot have a colinear segment If a polygon with an island inside a hole is valid (I can't see any reason why it is not) test of point in polygon must be done with the whole polygon and not only with the outer ring. If one wants to manage self-intersection polygons (to repair them ?), may be a full intersection matrix has to be computed instead of the point in polygon test Hope that makes sense Michaël Larry Becker a écrit : > Hi Michaël, > > Thanks for the advice. I may end up doing the DE-9IM matrix, but I'd > like to start with a review and critique of what I'm currently doing. > To reiterate: > > The problem that I'm trying to fix is: support for polygon shells > with CW holes in PolygonHandler because ESRI allows this. Without the > fix, JUMP imports these as overlapping shells which is a topology error. > > I attempted to limit the scope of the change by testing for > (shells.size()>1) && (holes.size() == 0). This triggers for the case > I am trying to fix, but unfortunately my shellsOverlap() method > assumes that the first polygon found that contains another is the > shell and that the rest are holes. > > This is a serious flaw that you caught. There may be multiple shells > with holes (or not) in each. If I am going to eliminate this case, an > additional test is needed to determine if the linear ring found by > shellsOverlap() does indeed contain all of the rest. Of course, if it > turns out that it does not, I'll have to deal with the case somehow; > perhaps by just allowing the bad geometry to be build as it is now. > > I very much want to maintain the current speed of the shapefile > reader. I'm not sure how much this fix will help others, but it seems > to handle the data that I have found so far. Any comments? > > regards, > Larry > > On Thu, Apr 17, 2008 at 4:12 PM, Michaël Michaud > <[EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>> wrote: > > Hi Larry, > > I get a case somewhat similar with a parser I wrote for GeoConcept > format. > In this format, multi-polygon come as a set of linear rings with no > special order and eventually some overlaps or other bad topology I > wanted to catch. > I decided to compute the DE-9IM matrix in a double loop > Something like > List<Polygon> input = ... // the list of polygons issued from my > linear > rings > List<Polygon> result = ... // an empty list of polygons > for (Polygon pi : input) > for (Polygon pr : result) > IntersectionMatrix im = pi.relate(pr) > // then decide if pi is a new polygon, a hole in an > existing > polygon (result), an overlapping polygon... > > I must admit this approach may have an unecessary performance penalty > for a format like shapefile (in my case, correctness was more > important > than performance) > > Michaël > > ------------------------------------------------------------------------- > This SF.net email is sponsored by the 2008 JavaOne(SM) Conference > Don't miss this year's exciting event. There's still time to save > $100. > Use priority code J8TL2D2. > > http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone > _______________________________________________ > Jump-pilot-devel mailing list > Jump-pilot-devel@lists.sourceforge.net > <mailto:Jump-pilot-devel@lists.sourceforge.net> > https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel > > > > > -- > http://amusingprogrammer.blogspot.com/ > >------------------------------------------------------------------------ > >------------------------------------------------------------------------- >This SF.net email is sponsored by the 2008 JavaOne(SM) Conference >Don't miss this year's exciting event. There's still time to save $100. >Use priority code J8TL2D2. >http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone > >------------------------------------------------------------------------ > >_______________________________________________ >Jump-pilot-devel mailing list >Jump-pilot-devel@lists.sourceforge.net >https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel > > ------------------------------------------------------------------------- This SF.net email is sponsored by the 2008 JavaOne(SM) Conference Don't miss this year's exciting event. There's still time to save $100. Use priority code J8TL2D2. http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone _______________________________________________ Jump-pilot-devel mailing list Jump-pilot-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
