I don't want to muddy this conversation, but you guys have triggered my curiousity.
Michael wrote: "Polygon may have multiple outer rings..." This is only true in the case of a polygon with holes, correct? Michael wrote: "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." This is really the problem we are trying to solve, correct? Have we thought about contacting the GeoTools programmers about this problem? I could send an e-mail to the mailing list. I don't know how much good it would do. I think the ESRI Shapefile code we are using is a lot older than what they have now. The Sunburned Surveyor On Thu, Apr 17, 2008 at 11:57 PM, Michaël Michaud <[EMAIL PROTECTED]> wrote: > 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 > > [email protected] > > <mailto:[email protected]> > > 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 > >[email protected] > >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 > [email protected] > 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 [email protected] https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
