Thread: Area Perimeter

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    37

    Area Perimeter

    I have a two dimensional array with some of the elements marked, in essence like the image below. I want to calculate the points needed to draw an outline around the marked elements. In this case it would be (2,2),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4), etc.

    Using a flood fill I can put together a set of elements are on the line, either inside touching, or outside touching, however, the elements will be in an pseudorandom order, rather than in-order going around the perimeter.

    Does anyone know of a good to find the perimeter in this situation?

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    From your list of points on the perimeter, find the coordinates where the x and y values *both* differ NOT from the previous points values, but from the point before that.

    It's a "not tonight, but the night before", kind of thing, but with points coordinates.

    OK, you're at a point, the x and y values are BOTH different than they were two points back. So you're NOT at a corner now, but your point one back (which will NOT have values that differ in both x and y from their adjacent points), is the corner point. Work it out on your diagram if you don't believe me.

    Another way to view it is when you find a point where one coordinate (say X for example), has been changing, and now the Y coordinate value starts to change, and the X value is not changing, then you have just gone PAST the corner - so go back one point.

    Putting your x and y values into an array of structs with x and y int's in it, is a nice way to keep things organized, imo.
    Last edited by Adak; 11-09-2010 at 04:15 PM.

  3. #3
    Registered User
    Join Date
    Feb 2009
    Posts
    37
    I don't have a list of perimeter points, I have a list of elements (squares) from my 2d array that are touching the perimeter, and they are not in-order because I am using a recursive method to find them, so a square from one side may be followed by a square from the other side (in theory; not so much for this area, but if it were E shaped),

    I had an idea that I could compare the sides of every square outside to those inside. If two squares share a side, then that side must form part of the perimeter. That seems somewhat inefficient though, I feel like there must be a better way. But maybe it doesn't really matter.

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Seems to me this would be easier if you had all the squares that make up the shape. Then you could go through that list of squares, and count how many edges of each square are not shared with another square in the shape. Here is a graphical representation of the example you gave:

    Code:
    .......
    .xxxxx.
    .x212x.
    .x201x.
    .xx22x.
    .xxxxx.
    .......
    I have used a . to mean squares of no significance, an x to symbolize the points you were given, that lie on the outer edge of your shape, and a number to represent the "perimeter value" of each square. Corners contribute 2 units to the perimeter, edges contribute 1 unit, internal shapes contribute 0, etc.

    I hope that gets you going in the right direction.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Your squares should be in order, so you can "walk" the perimeter of your shape.

    If the word "point" doesn't appeal to you, just replace it with "square". Same concept, whatever the name being used. No difference at all.

  6. #6
    Registered User
    Join Date
    Feb 2009
    Posts
    37
    Quote Originally Posted by anduril462 View Post
    Seems to me this would be easier if you had all the squares that make up the shape. Then you could go through that list of squares, and count how many edges of each square are not shared with another square in the shape. Here is a graphical representation of the example you gave:

    Code:
    .......
    .xxxxx.
    .x212x.
    .x201x.
    .xx22x.
    .xxxxx.
    .......
    I have used a . to mean squares of no significance, an x to symbolize the points you were given, that lie on the outer edge of your shape, and a number to represent the "perimeter value" of each square. Corners contribute 2 units to the perimeter, edges contribute 1 unit, internal shapes contribute 0, etc.

    I hope that gets you going in the right direction.
    This is what I did and it ended up working good. Thanks,

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Error in printf line,,,what's wrong?
    By mft_ika in forum C Programming
    Replies: 9
    Last Post: 03-19-2010, 08:46 PM
  2. finding area of ellipse
    By dvsumosize in forum C Programming
    Replies: 4
    Last Post: 10-26-2009, 07:20 PM
  3. very weird problem (pointers I think)
    By hannibar in forum C Programming
    Replies: 2
    Last Post: 10-11-2005, 06:45 AM
  4. Need help with switch
    By 3kgt in forum C Programming
    Replies: 2
    Last Post: 02-26-2003, 12:43 PM
  5. Tab Controls - API
    By -KEN- in forum Windows Programming
    Replies: 7
    Last Post: 06-02-2002, 09:44 AM