Hi all,
I need an efficient algorithm to node all the edges of a set of overlapping geometries with the intersections found. Currently i'm following this algorithm (for two geometries) but the last step i need is how to rebuild the original geometry (including its holes): public static void noder(Geometry g1, Geometry g2){ //GeometryFactory gf = new GeometryFactory(); // add the linestrings to a list of NodedSegmentString; List list = new ArrayList(); list.add(new NodedSegmentString(g1.getCoordinates(), null)); list.add(new NodedSegmentString(g2.getCoordinates(), null)); // create a noder and computes the nodes MCIndexNoder noder = new MCIndexNoder(); noder.setSegmentIntersector(new IntersectionAdder(new RobustLineIntersector())); noder.computeNodes(list); ... At this point which is the most efficient way to recreate the original polygons (with holes) having their edges noded properly? Is MCIndexNoder the best method to get all the intersections? Thank you Sandro Zacchino _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Yes, MCIndexNoder is the most efficient way to determine the
intersections between geometries. Generally you're heading in the right direction. Where you go from there depends on exactly what you want your output to be. If I understand your use case, you want to recreate the original geometries, but with vertices inserted where the intersection points occur. This is not something which is currently directly supported by NodedSegmentString, but it's easy to add (either by extension or by external code). A NodedSegmentString contains a list of the nodes along the SegmentString, as SegmentNodes. Each SegmentNode records its location and which segment it occurs in. So all that is required is to build a new CoordinateSequence including the new nodes as vertices in the appropriate places. You can then reform your original geometry by replacing each CoordinateSequence by the corresponding noded one. One trick is to "tag" the NodedSegmentStrings you create by setting the data field to be the original CoordinateSequence. Then you can create a map from the orig CS to the noded sequence, and then use something like GeometryEditor to replace the sequences. Sandro Zacchino wrote: > Hi all, > > I need an efficient algorithm to node all the edges of a set of > overlapping geometries with the intersections found. > Currently i'm following this algorithm (for two geometries) but the > last step i need is how to rebuild the original geometry (including > its holes): > > > public static void noder(Geometry g1, Geometry g2){ > > //GeometryFactory gf = new GeometryFactory(); > > // add the linestrings to a list of NodedSegmentString; > List list = new ArrayList(); > list.add(new NodedSegmentString(g1.getCoordinates(), null)); > list.add(new NodedSegmentString(g2.getCoordinates(), null)); > > // create a noder and computes the nodes > MCIndexNoder noder = new MCIndexNoder(); > noder.setSegmentIntersector(new IntersectionAdder(new > RobustLineIntersector())); > noder.computeNodes(list); > > ... > > > > At this point which is the most efficient way to recreate the original > polygons (with holes) having their edges noded properly? > Is MCIndexNoder the best method to get all the intersections? > > Thank you > > Sandro Zacchino > > > _______________________________________________ > jts-devel mailing list > [hidden email] > http://lists.refractions.net/mailman/listinfo/jts-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Thank you Martin.
I developed the method below. I've tested it and it seems to be quite efficient. Now the input parameters are Polygons since Geometry does not have methods to know if it contains holes or not. The check on holes presence is made since Polygonizer returns both polygons with holes and holes. I will inspect the GeometryEditor you suggested to see if it is more efficient than Polygonizer. Bye Sandro Zacchino /** * This method splits edges of two (possibly) overlapping polygons for each intersection found * @param g1 Polygon * @param g2 Polygon */ public static List<Polygon> noder(Polygon g1, Polygon g2){ GeometryFactory gf = g1.getFactory(); //A list of NodedSegmentStrings to compute intersections List list = new ArrayList(); //A NodedSegmentString is added with userdata: //+1 for the 1st polygon, if it does not contain holes //-1 for the 1st polygon, if it contains holes //+2 for the 2nd polygon, if it does not contain holes //-2 for the 2nd polygon, if it contains holes Integer g1Data = new Integer(1); if (g1.getNumInteriorRing()>=1){ g1Data = new Integer(-1); } list.add(new NodedSegmentString(g1.getCoordinates(), g1Data)); Integer g2Data = new Integer(2); if (g2.getNumInteriorRing()>=1){ g2Data = new Integer(-2); } list.add(new NodedSegmentString(g2.getCoordinates(), g2Data)); //Create a noder and computes the nodes MCIndexNoder noder = new MCIndexNoder(); noder.setSegmentIntersector(new IntersectionAdder(new RobustLineIntersector())); noder.computeNodes(list); //Rebuild original polygons with splitted edges Collection nodedSegStrings = noder.getNodedSubstrings(); // Map: Key is NodedSegmentString.UserData, Value is a list of polygons // this map is used to store all the noded linestrings for a given input polygon // using the Data inside the NodedSegmentString HashMap<Integer, List<LineString>> polygons = new HashMap<Integer, List<LineString>>(); for (Iterator i = nodedSegStrings.iterator(); i.hasNext(); ){ NodedSegmentString segString = (NodedSegmentString)i.next(); Integer userData = (Integer)segString.getData(); LineString ls = gf.createLineString(segString.getCoordinates()); if (!polygons.containsKey(userData)){ polygons.put(userData, new ArrayList<LineString>()); } polygons.get(userData).add(ls); } // The polygonizer is used to build polygons from noded linestrings // if the original polygon contains holes polygonizer returns two // (or more) polygons one for polygon with holes and one for each // hole. So i use the sign of the data stored in NodedegmentStrings, // and here used as key for the map, to discard the "holes polygons" // from the polygonizer result. ArrayList<Polygon> result = new ArrayList<Polygon>(); for(Entry<Integer, List<LineString>> e: polygons.entrySet()){ Polygonizer polygonizer = new Polygonizer(); polygonizer.add(e.getValue()); for(Polygon p: (Collection<Polygon>)polygonizer.getPolygons()){ if (e.getKey()<0){ if (p.getNumInteriorRing()>=1) result.add(p); } else result.add(p); } //result.addAll(polygonizer.getPolygons()); } return result; } Martin Davis ha scritto: > Yes, MCIndexNoder is the most efficient way to determine the > intersections between geometries. > > Generally you're heading in the right direction. Where you go from > there depends on exactly what you want your output to be. If I > understand your use case, you want to recreate the original > geometries, but with vertices inserted where the intersection points > occur. This is not something which is currently directly supported by > NodedSegmentString, but it's easy to add (either by extension or by > external code). A NodedSegmentString contains a list of the nodes > along the SegmentString, as SegmentNodes. Each SegmentNode records > its location and which segment it occurs in. So all that is required > is to build a new CoordinateSequence including the new nodes as > vertices in the appropriate places. > > You can then reform your original geometry by replacing each > CoordinateSequence by the corresponding noded one. One trick is to > "tag" the NodedSegmentStrings you create by setting the data field to > be the original CoordinateSequence. Then you can create a map from > the orig CS to the noded sequence, and then use something like > GeometryEditor to replace the sequences. > > > Sandro Zacchino wrote: >> Hi all, >> >> I need an efficient algorithm to node all the edges of a set of >> overlapping geometries with the intersections found. >> Currently i'm following this algorithm (for two geometries) but the >> last step i need is how to rebuild the original geometry (including >> its holes): >> >> >> public static void noder(Geometry g1, Geometry g2){ >> >> //GeometryFactory gf = new GeometryFactory(); >> >> // add the linestrings to a list of NodedSegmentString; >> List list = new ArrayList(); >> list.add(new NodedSegmentString(g1.getCoordinates(), null)); >> list.add(new NodedSegmentString(g2.getCoordinates(), null)); >> >> // create a noder and computes the nodes >> MCIndexNoder noder = new MCIndexNoder(); >> noder.setSegmentIntersector(new IntersectionAdder(new >> RobustLineIntersector())); >> noder.computeNodes(list); >> >> ... >> >> >> >> At this point which is the most efficient way to recreate the >> original polygons (with holes) having their edges noded properly? >> Is MCIndexNoder the best method to get all the intersections? >> >> Thank you >> >> Sandro Zacchino >> >> >> _______________________________________________ >> jts-devel mailing list >> [hidden email] >> http://lists.refractions.net/mailman/listinfo/jts-devel >> > _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Polygonizer is also a possible approach. As you note, it returns
polygons "filling in" holes, so it requires a bit more work than my approach. Also, it's probably a bit less efficient than my approach, since there is a cost to doing a full-scale polygonization. But working tested code is valuable in its own right... Sandro Zacchino wrote: > Thank you Martin. > > I developed the method below. I've tested it and it seems to be quite > efficient. Now the input parameters are Polygons since Geometry does > not have methods to know if it contains holes or not. The check on > holes presence is made since Polygonizer returns both polygons with > holes and holes. I will inspect the GeometryEditor you suggested to > see if it is more efficient than Polygonizer. > > Bye > > Sandro Zacchino > > /** > * This method splits edges of two (possibly) overlapping polygons > for each intersection found > * @param g1 Polygon > * @param g2 Polygon > */ > public static List<Polygon> noder(Polygon g1, Polygon g2){ > GeometryFactory gf = g1.getFactory(); > > //A list of NodedSegmentStrings to compute intersections > List list = new ArrayList(); > //A NodedSegmentString is added with userdata: > //+1 for the 1st polygon, if it does not contain holes > //-1 for the 1st polygon, if it contains holes > //+2 for the 2nd polygon, if it does not contain holes > //-2 for the 2nd polygon, if it contains holes > Integer g1Data = new Integer(1); > if (g1.getNumInteriorRing()>=1){ > g1Data = new Integer(-1); > } > list.add(new NodedSegmentString(g1.getCoordinates(), g1Data)); > Integer g2Data = new Integer(2); > if (g2.getNumInteriorRing()>=1){ > g2Data = new Integer(-2); > } > list.add(new NodedSegmentString(g2.getCoordinates(), g2Data)); > > //Create a noder and computes the nodes > MCIndexNoder noder = new MCIndexNoder(); > noder.setSegmentIntersector(new IntersectionAdder(new > RobustLineIntersector())); > noder.computeNodes(list); > //Rebuild original polygons with splitted edges > Collection nodedSegStrings = noder.getNodedSubstrings(); > // Map: Key is NodedSegmentString.UserData, Value is a list of > polygons > // this map is used to store all the noded linestrings for a given > input polygon > // using the Data inside the NodedSegmentString > HashMap<Integer, List<LineString>> polygons = new HashMap<Integer, > List<LineString>>(); > > for (Iterator i = nodedSegStrings.iterator(); i.hasNext(); ){ > NodedSegmentString segString = (NodedSegmentString)i.next(); > Integer userData = (Integer)segString.getData(); > LineString ls = gf.createLineString(segString.getCoordinates()); > if (!polygons.containsKey(userData)){ > polygons.put(userData, new ArrayList<LineString>()); > } > polygons.get(userData).add(ls); > } > > // The polygonizer is used to build polygons from noded linestrings > // if the original polygon contains holes polygonizer returns two > // (or more) polygons one for polygon with holes and one for each > // hole. So i use the sign of the data stored in NodedegmentStrings, > // and here used as key for the map, to discard the "holes polygons" > // from the polygonizer result. > ArrayList<Polygon> result = new ArrayList<Polygon>(); > for(Entry<Integer, List<LineString>> e: polygons.entrySet()){ > Polygonizer polygonizer = new Polygonizer(); > polygonizer.add(e.getValue()); > for(Polygon p: (Collection<Polygon>)polygonizer.getPolygons()){ > if (e.getKey()<0){ > if (p.getNumInteriorRing()>=1) > result.add(p); > } > else > result.add(p); > } > //result.addAll(polygonizer.getPolygons()); > } > return result; > } > > Martin Davis ha scritto: >> Yes, MCIndexNoder is the most efficient way to determine the >> intersections between geometries. >> >> Generally you're heading in the right direction. Where you go from >> there depends on exactly what you want your output to be. If I >> understand your use case, you want to recreate the original >> geometries, but with vertices inserted where the intersection points >> occur. This is not something which is currently directly supported >> by NodedSegmentString, but it's easy to add (either by extension or >> by external code). A NodedSegmentString contains a list of the nodes >> along the SegmentString, as SegmentNodes. Each SegmentNode records >> its location and which segment it occurs in. So all that is required >> is to build a new CoordinateSequence including the new nodes as >> vertices in the appropriate places. >> >> You can then reform your original geometry by replacing each >> CoordinateSequence by the corresponding noded one. One trick is to >> "tag" the NodedSegmentStrings you create by setting the data field to >> be the original CoordinateSequence. Then you can create a map from >> the orig CS to the noded sequence, and then use something like >> GeometryEditor to replace the sequences. >> >> >> Sandro Zacchino wrote: >>> Hi all, >>> >>> I need an efficient algorithm to node all the edges of a set of >>> overlapping geometries with the intersections found. >>> Currently i'm following this algorithm (for two geometries) but the >>> last step i need is how to rebuild the original geometry (including >>> its holes): >>> >>> >>> public static void noder(Geometry g1, Geometry g2){ >>> >>> //GeometryFactory gf = new GeometryFactory(); >>> >>> // add the linestrings to a list of NodedSegmentString; >>> List list = new ArrayList(); >>> list.add(new NodedSegmentString(g1.getCoordinates(), null)); >>> list.add(new NodedSegmentString(g2.getCoordinates(), null)); >>> >>> // create a noder and computes the nodes >>> MCIndexNoder noder = new MCIndexNoder(); >>> noder.setSegmentIntersector(new IntersectionAdder(new >>> RobustLineIntersector())); >>> noder.computeNodes(list); >>> >>> ... >>> >>> >>> >>> At this point which is the most efficient way to recreate the >>> original polygons (with holes) having their edges noded properly? >>> Is MCIndexNoder the best method to get all the intersections? >>> >>> Thank you >>> >>> Sandro Zacchino >>> >>> >>> _______________________________________________ >>> jts-devel mailing list >>> [hidden email] >>> http://lists.refractions.net/mailman/listinfo/jts-devel >>> >> > > _______________________________________________ > jts-devel mailing list > [hidden email] > http://lists.refractions.net/mailman/listinfo/jts-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Free forum by Nabble | Edit this page |