CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Apr 2014
    Posts
    1

    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:
    Name:  ex01.PNG
Views: 1320
Size:  1.8 KB
    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:
    Name:  cycle.PNG
Views: 1214
Size:  8.2 KB 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.
    Thanks in advance!
    Attached Images Attached Images  

  2. #2
    Join Date
    Apr 2014
    Location
    in northeast ohio
    Posts
    94

    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

    Basically, I have a two-dimensional array of boolean values representing an area of cells
    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


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

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured