decompose rectilinear polygon

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

decompose rectilinear polygon

mbedward
Hi folks,

I need an algorithm to decompose a rectilinear polygon into a set of
non-overlapping rectangles.  I've looked in JTS but haven't spotted
such a method - if I've overlooked it I'd appreciate someone pointing
me in the right direction.

If I need to code something myself I was planning to base it on the
algorithm described here: http://portal.acm.org/citation.cfm?id=322985
 Once again, if anyone knows of a better approach please let me know.

cheers
Michael
_______________________________________________
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: decompose rectilinear polygon

mbedward
2008/12/17 Michael Bedward <[hidden email]>:
> Hi folks,
>
> I need an algorithm to decompose a rectilinear polygon into a set of
> non-overlapping rectangles.

I now have this working.  No doubt there is a much easier and more
elegant solution, but here is my approach:

1. Get polygon vertices

2. Tag each vertex as convex or concave

3. Find a concave vertex that is proceeded by 3 or more convex
vertices; form a rectangle R using the closest 3 vertices; add R to
output list

4. P = difference of R and P

5. If P contains more than 4 unique vertices go to (1); otherwise P is
last rectangle

Michael
_______________________________________________
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: decompose rectilinear polygon

mbedward
> 3. Find a concave vertex that is proceeded by 3 or more convex
> vertices;

sorry, that should read "preceded by 3 or more..."
_______________________________________________
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: decompose rectilinear polygon

mbedward
Apologies for all the self-replies on the this thread...

I now have code that seems to work - slightly more involved than I
previously described after I realized that many configurations will
not have 3 consecutive convex vertices and that I needed to guard
against colinear point in the polygon's boundary.

In case it's of use to anyone, here is the code.  I'd also still be
keen to hear how this task should really be done !

Michael

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

OrthoPolygonDecomposer.java (8K) Download Attachment
EditablePolygon.java (2K) Download Attachment
Loading...