Splitting a polygon with a linestring

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

Splitting a polygon with a linestring

Rory Plaire
Hi all,
 
I'm solving the "splitting a polygon with a linestring" problem, and I'm trying to repurpose the geometry graph structure to give me the result. My current approach is to:
 
1) node the intersection of the linestring and polygon boundary
2) iterate the resulting edges
3) mark the both the directed edges resulting from the linestring as in the result
4) polygonize the graph
 
This has problems, though, since the machinery that exists doesn't like to use DEs where both the forward and reverse DE on an edge are in the result. So I modified the algorithm at (3) to copy the reverse DE into another DE, mark the original Sym as not in the result, and add the copy to the graph. This, however, gets canceled out when the DE is determined to have the same points as the existing DE's Sym, and the DE copy is never added to the graph's edge map.
 
So, before I plow forward, I thought I'd take a pause to see if someone might have a bit more insight into this. Apparently, it's been a problem for others, and perhaps there is some thinking on it I could benefit from. Does generating two forward DE edges, with the internal area on the right, in order to generate shells, make sense? Is the problem just that JTS doesn't support having two DEs with the same coordinates and are mirrors?
 
thanks!
-rory

_______________________________________________
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: Splitting a polygon with a linestring

azabala
This problem has been resolved some time ago by AXIOS' team (please, correct me if Im wrong).

You can access to source code in http://subversion.gvsig.org/gvSIG/trunk/libraries/libTopology/src/es/axios/udig/ui/editingtools/internal/geometryoperations/split/

2009/5/29 Rory Plaire <[hidden email]>
Hi all,
 
I'm solving the "splitting a polygon with a linestring" problem, and I'm trying to repurpose the geometry graph structure to give me the result. My current approach is to:
 
1) node the intersection of the linestring and polygon boundary
2) iterate the resulting edges
3) mark the both the directed edges resulting from the linestring as in the result
4) polygonize the graph
 
This has problems, though, since the machinery that exists doesn't like to use DEs where both the forward and reverse DE on an edge are in the result. So I modified the algorithm at (3) to copy the reverse DE into another DE, mark the original Sym as not in the result, and add the copy to the graph. This, however, gets canceled out when the DE is determined to have the same points as the existing DE's Sym, and the DE copy is never added to the graph's edge map.
 
So, before I plow forward, I thought I'd take a pause to see if someone might have a bit more insight into this. Apparently, it's been a problem for others, and perhaps there is some thinking on it I could benefit from. Does generating two forward DE edges, with the internal area on the right, in order to generate shells, make sense? Is the problem just that JTS doesn't support having two DEs with the same coordinates and are mirrors?
 
thanks!
-rory

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel




--
Alvaro Zabala Ordóñez
azabala[en]gmail[punto]com
alvaro.zabala[en]juntadeandalucia[punto]es
Tlf: 954 995 572
Gabinete de Normalización y Calidad
Servicio de Coordinación y Desarrollo de Sistemas Horizontales.
D.G. de Innovación y Administraciones Públicas.
Consejería de Innovación, Ciencia y Empresa, Junta de Andalucía


Sent from Sevilla, AN, Spain
_______________________________________________
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: Splitting a polygon with a linestring

Aron Olsen

Hi there,

 

Here is some code I have produced to perform splitting of polygons by other polygons/linestrings.

It’s Java 5 compliant.

 

/Aron

 


From: [hidden email] [mailto:[hidden email]] On Behalf Of Alvaro Zabala
Sent: 29 May 2009 08:57
To: JTS Topology Suite Development
Subject: Re: [jts-devel] Splitting a polygon with a linestring

 

This problem has been resolved some time ago by AXIOS' team (please, correct me if Im wrong).

You can access to source code in http://subversion.gvsig.org/gvSIG/trunk/libraries/libTopology/src/es/axios/udig/ui/editingtools/internal/geometryoperations/split/

2009/5/29 Rory Plaire <[hidden email]>

Hi all,

 

I'm solving the "splitting a polygon with a linestring" problem, and I'm trying to repurpose the geometry graph structure to give me the result. My current approach is to:

 

1) node the intersection of the linestring and polygon boundary

2) iterate the resulting edges

3) mark the both the directed edges resulting from the linestring as in the result

4) polygonize the graph

 

This has problems, though, since the machinery that exists doesn't like to use DEs where both the forward and reverse DE on an edge are in the result. So I modified the algorithm at (3) to copy the reverse DE into another DE, mark the original Sym as not in the result, and add the copy to the graph. This, however, gets canceled out when the DE is determined to have the same points as the existing DE's Sym, and the DE copy is never added to the graph's edge map.

 

So, before I plow forward, I thought I'd take a pause to see if someone might have a bit more insight into this. Apparently, it's been a problem for others, and perhaps there is some thinking on it I could benefit from. Does generating two forward DE edges, with the internal area on the right, in order to generate shells, make sense? Is the problem just that JTS doesn't support having two DEs with the same coordinates and are mirrors?

 

thanks!

-rory


_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel




--
Alvaro Zabala Ordóñez
azabala[en]gmail[punto]com
alvaro.zabala[en]juntadeandalucia[punto]es
Tlf: 954 995 572
Gabinete de Normalización y Calidad
Servicio de Coordinación y Desarrollo de Sistemas Horizontales.
D.G. de Innovación y Administraciones Públicas.
Consejería de Innovación, Ciencia y Empresa, Junta de Andalucía


Sent from Sevilla, AN, Spain


_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel

PolygonSplitter.java (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Splitting a polygon with a linestring

Rory Plaire
Thanks Aron - I'm looking at it now.
 
Also, thanks, Alvaro, I hadn't found that, even after a search of this list's archives.
 
-r

On Fri, May 29, 2009 at 1:39 AM, Aron Olsen (ARO) <[hidden email]> wrote:

Hi there,

 

Here is some code I have produced to perform splitting of polygons by other polygons/linestrings.

It’s Java 5 compliant.

 

/Aron

 


From: [hidden email] [mailto:[hidden email]] On Behalf Of Alvaro Zabala
Sent: 29 May 2009 08:57
To: JTS Topology Suite Development
Subject: Re: [jts-devel] Splitting a polygon with a linestring

 

This problem has been resolved some time ago by AXIOS' team (please, correct me if Im wrong).

You can access to source code in http://subversion.gvsig.org/gvSIG/trunk/libraries/libTopology/src/es/axios/udig/ui/editingtools/internal/geometryoperations/split/

2009/5/29 Rory Plaire <[hidden email]>

Hi all,

 

I'm solving the "splitting a polygon with a linestring" problem, and I'm trying to repurpose the geometry graph structure to give me the result. My current approach is to:

 

1) node the intersection of the linestring and polygon boundary

2) iterate the resulting edges

3) mark the both the directed edges resulting from the linestring as in the result

4) polygonize the graph

 

This has problems, though, since the machinery that exists doesn't like to use DEs where both the forward and reverse DE on an edge are in the result. So I modified the algorithm at (3) to copy the reverse DE into another DE, mark the original Sym as not in the result, and add the copy to the graph. This, however, gets canceled out when the DE is determined to have the same points as the existing DE's Sym, and the DE copy is never added to the graph's edge map.

 

So, before I plow forward, I thought I'd take a pause to see if someone might have a bit more insight into this. Apparently, it's been a problem for others, and perhaps there is some thinking on it I could benefit from. Does generating two forward DE edges, with the internal area on the right, in order to generate shells, make sense? Is the problem just that JTS doesn't support having two DEs with the same coordinates and are mirrors?

 

thanks!

-rory


_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel




--
Alvaro Zabala Ordóñez
azabala[en]gmail[punto]com
alvaro.zabala[en]juntadeandalucia[punto]es
Tlf: 954 995 572
Gabinete de Normalización y Calidad
Servicio de Coordinación y Desarrollo de Sistemas Horizontales.
D.G. de Innovación y Administraciones Públicas.
Consejería de Innovación, Ciencia y Empresa, Junta de Andalucía


Sent from Sevilla, AN, Spain


_______________________________________________
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
Loading...