3 Attachment(s)
Quadrangulation of orthogonal polygons
Hello there! I am new to this forum, but I hope to receive some basic idea for my problem:
I'm right at the start of a new project, so this question is quite conceptional, but will be realized in C#. Basically, I have a two-dimensional array of boolean values representing an area of cells:
Attachment 32501
The green ones (=true) represent my "polygons". My aim is to find an algorithm, which finds the minimum amount of rectangles within the green areas and their coordinates.
My thought was to find the center of the whole area or the nearest point to it which is "free" (=green/true), cycle around that spot to find the nearest border and expand from there to the other borders:
Attachment 32503 The blue spot marks my center and he yellow one is the nearest border. From there I expand in the second step to have my rectangle in the last step.
The problem is, this algorithm isn't very clever. In more complex situations than this simple example it often produces a huge amount of unnecessary rectangles.
So, I was thinking of a whole new algorithm, but any idea failed at some point when going through more complex shapes and I don't want to apply complex triangulation solutions to my quite simple case.
Does anyone of you have a basic idea to start with? Again, this is just conceptional at the moment, so, I don't have any code yet. Neither do I expect a perfect solution to my problem. I just want to get some inspiration and hear your ideas to the problem. :D
Thanks in advance!
Re: Quadrangulation of orthogonal polygons
well im new here
im not sure i fully understand the goal
but since this has been here for some time
you said any idea's
Quote:
Basically, I have a two-dimensional array of boolean values representing an area of cells
Quote:
My aim is to find an algorithm, which finds the minimum amount of rectangles within the green areas and their coordinates.
this sounds fascinatingly similar to something one might use with
a path-finding algorithm such as
dijkstra's or A star or some other variant
the basic premise might be modified to your needs
treating each grid section as a node
instead of using it as a search for a path
you might use it as a search to tally up all valid nodes per region
much like a paint fill algorithm
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
because the way dijkstras works your basically turning everything into nodes
if you were to have one version treat green nodes as impassable and the other red
then simply perfoming a search at each unique area
would build up a list of nodes for a passable area
ie each region as if it were its own section
the length of which could be traverse and operated on
the length itself would be the amount of bools per area as stated above
http://upload.wikimedia.org/wikipedi..._animation.gif
i dunno if that helps
but it looks similar to a regular game algorithm problem for path or region finding
you will also see that these algorithms can be applied to vertices when treating them as nodes
there are videos and such that do it on you tube ect...
