Quantcast

Noding polygons

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Noding polygons

Sandro Zacchino
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Noding polygons

Martin Davis
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Noding polygons

Sandro Zacchino
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Noding polygons

Martin Davis
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
Loading...