How to get the location of these Xs in the variable???

cyanblue

To put this problem simpler form...

// The first line added just to get the location... Don't mind it...

//2345678901234567890
00000000000000000000
000X11X0000000000000
0001111000000X11X000
00011110000001111000
00011110000001111000
0001111000000X11X000
00011110000000000000
00011110000000000000
000X11X0000000000000
00000000000000000000

This is the content of the whole text file imported into the variable in PHP... and I want to get the location of each 'X' characters within it via PHP if possible... Like X11.x = 4, X11.y = 1, X12.x = 7, X12.y = 1, and so on, but the Xs in one box should have the same name like X1 or X2, and the first X in X1 is going to be called X11 and such... What would be the best way of doing it??? Somebody shed some light on my brain??? 😉

Mordecai

Here's what I'd do. I'd sort by lines and use a format of $x.line.num and $y.line.num. You can loop through every line, use strstr(haystack,needle) to find the location of the character, then write the variable using $$.

Of course, it'd be better to use an array. Either way, you'll still have to know the name of the variables.

cyanblue

Thank you for the reply, Mordecai... 😉

This is what I don't get it right...

Yes... I can go over the charcters one by one, and see if it is 'X' or not and get the location of it... I have 8 Xs in the previous question, so I'll just say X1, X2, X3, X4 for the top row from left to right, and X5, X6, X7 and X8 for the bottom row...
I know that X1, X2, X5 and X6 are one group, and X3, X4, X7 and X8 are another group just by looking at it... ,But how would I know if I program it??? In this example, it will be obvious because I can check the same y value for X1 and X5 because it is vertical... But it won't work when the shape is diagonal...

So, I was thinking of some sort of algorithm, but it doesn't make much sense in my brain...
Those Xs are represented as 1 in the actual variable...
Do the character checking one by one until I see '1', and if it is 1, see if next one is 1 as well until the one after that is not 0, and go downward the same way until the 0 is met... That way I can get the location of four points of that group... But if I do this, the for loop will be messed up... 🙁

Any idea would be aprreciated... Thank you... 🙂

Mordecai

Oh, you're setting bounds for a shape... okay. I guess I didn't get the question very well.

I'm not really sure how the loop would work for that. I'll think about it.

Weedpacket

By "boxes", I take it you mean those patches of 1's, and the X's mark the corners of the boxes?

Hmm... intriguing....

Haven't got an algorithm just yet; but before I start I'd get all that two-dimensional data into a two-dimensional array.

If the boxes are always going to be rectangular, the X's aren't necessary to identify the corners: they'll the the 1's that have two 0's as immediate neighbours (all the others have 1 or 0).

It's a region-finding problem; simplified if the boxes are rectangular. Lessee - starting from top left and going across and down. The first X found will be the top-left corner of a box. The first X immediately to its right will be the top right corner, the two X's immediately below those will be the bottom corners. Once those four are found that's the first box. Continue scanning through for any unmatched X's. The next one found will be the top-left corner of the second component, and the process repeats.

So, scan through the array till an X is found. Keep a small array of "X's found for this component". Push the location of this first X into it (and maybe turn the original into a 1 to be tidy and stop you running into it again later). Scan right until another X is found. Push this onto the array. Scan down from the first X to find the third; and scan down from the second to find the fourth. This small array would end up holding the coordinates of the corners of the box in the order TL, TR, BL, BR. something like

array(         // All boxes
 array(        // First box
  array(3,4),  // Top left corner of first box
  array(3,7),  // Top right corner of first box
  array(11,4), // Bottom left corner of first box
  array(11,7)  // Bottom right corner of first box
 ),
 ....//other boxes
)

Again, I'm assuming boxes are rectangular, and never share corners (and that the X's do mark corners).

If the situation is a bit more general than that then I'll have to think about it for a bit.

Mordecai

Well, he said that they weren't always rectangular, which is what makes it so hard.

For instance, if the shape were something like this:

00000000000000000000
00000000111100000000
00000111111111100000
00011111111111111000
00111111111111110000
01111111111111000000
01111111111100000000
01111111111110000000
00111111111111000000
00011111111111111000
00000111111111100000
00000000111100000000
00000000000000000000

Then poor little pac-man would be ripped to shreds (and, coincidentally, 20 or so rectangles).

cyanblue

Thank you, Weedpacket, for the reply... 😉

First of all, I just want to say that I am at the stage of just starting to learn PHP... It's abit hard, but interesting one to learn... I mainly use PHP for my Flash project, and this one is one of that instance... 😉

Um... The problem is that all those 'X' are there just to explain the problem... Those are not there actually... When it is in the file, they are also all '1's...

Maybe sample will be better to tell you what I want to do...
The JPEG file has been parsed and all the black spots in the JPEG file, walls, are indicated as '1' later in the text file... I am not sure how, but maybe there is way to indicate actual 'X' in each corner via the JPEG parse routine???

Anyways... What I am trying to do is to create hotspots, walls, from the JPEG file and have that hotspots imported into Flash... and I am thinking of creating SWF file with Ming, but I cannot do it because I do not know the coordinates... 🙁

I only have one diagonal wall in that JPEG file, but I have at least one or two diagonal walls on each floor plan, so I cannot just disregard it...

Again, I'm assuming boxes are rectangular, and never share corners

Yes... and no... Actually all the walls share its corners, but I am manually removing one pixel width of the wall in Photoshop before I run the JPEG file under the PHP script... It would be wonderful if I don't have to, but I thikn it will be impossible thing to do... (At least to me it is...) So, yes... All the walls are rectangular and never share corners...

(and that the X's do mark corners)

Yes... They are corners, but that's there just for your eyes as I have mentioned already... They are all '1's actually... Maybe it will be possible to put 'X' instead of '1' if it is a corner from the script that I have and that makes things easier??? 😃

Oh, Mordecai... That's a cute pacman... 🙂 Hehe... It won't be the case though... The blocks, walls, are all rectangular, but it could be diagonal ones like this...

0000000000000000000000000000001100
0000000000000000000000000000001100
0000000000000000000000000000001100
0000000000000000000000000000001100
0000000000000000000000000000001100
0000000000000000000000000000001100
0000000000000000000000000000100000
0000000000000000000000000001110000
0000000000000000000000000011100000
0000000000000000000000000111000000
0000000000000000000000001110000000
0000000000000000000000011100000000
0000000000000000000000111000000000
0000000000000000000001110000000000
0000000000000000000011100000000000
0000000000000000000111000000000000
0000000000000000001110000000000000
0000000000000000011100000000000000
0000000000000000011000000000000000
0001111111111111000000000000000000
0001111111111111100000000000000000
0001111111111111000000000000000000
0000000000000000000000000000000000

It is 45' rotated wall at the corner... (Hm... I see that this corner will make top left to bottom right algorithm confused, I guess???)

Thank you for your time... Much appreciated... 😉

Weedpacket

Oh, yeah, didn't notice that - splitting headache right now (it's that "boxes" bit that threw me). Bounding boxes for regions, right. Gotcha now.

I've got an approach in mind.

Scan each cell starting from the top left.
If we see a 1, we look to its left and we look up. If we see a 1 in either of those locations, then this 1 is part of the same component. If we see a 1 in both locations, then the two components should be merged (if they're not already the same).
After all the scanning, look at each of the components remaining. Their maximum and minimum x and y values mark out the bounding box for that component.

To wasted right now to figure out a good data structure to implement that on. Maybe an auxiliary array, so that you could "paint" each cell as you go, so that each component has a distinct "colour". Then components can be merged by changing the colour of one to match that of the other (swoop through the auxiliary array and repaint the affected cells).

cyanblue

Dang... Forgot to add the file... Obviously my brain is not what I used have... 🙁

Don't blame me for crossposting, but I had an old thread here if you are interested in the whole story... But there isn't many backend people there... 🙁

Weedpacket

Using '.' instead of 0

...1..
.1.1..
.111.1
.....1

Starting the scan.
A '1' is found at [1][0]. No neighbours found, so colour it 'A' (new colour)

...[color=red]A[/color]...
.1.1...
.111..1
......1

Continuing the scan.
A '1' is found at [1][1]. No neighbours found, so colour it 'B' (new colour)

...[color=red]A[/color]..
.[color=blue]B[/color].1..
.111.1
.....1

Continuing the scan.
A '1' is found at [3][1]. Neighbour coloured 'A' found, so colour this one 'A'

...[color=red]A[/color]..
.[color=blue]B[/color].[color=red]A[/color]..
.111.1
.....1

Continuing the scan.
A '1' is found at [1][2]. Neighbour coloured 'B' found, so colour this one 'B'

...[color=red]A[/color]..
.[color=blue]B[/color].[color=red]A[/color]..
.[color=blue]B[/color]11.1
.....1

Continuing the scan.
A '1' is found at [2][2]. Neighbour coloured 'B' found, so colour this one 'B'

...[color=red]A[/color]..
.[color=blue]B[/color].[color=red]A[/color]..
.[color=blue]B[/color][color=blue]B[/color]1.1
.....1

Continuing the scan.
A '1' is found at [3][2]. Neighbours coloured 'A' and 'B' found, so colour this one 'B' and recolour 'A' cells 'B' as well.

...[color=blue]B[/color]..
.[color=blue]B[/color].[color=blue]B[/color]..
.[color=blue]B[/color][color=blue]B[/color][color=blue]B[/color].1
.....1

Continuing the scan.
A '1' is found at [5][2]. No neighbours found, so colour it 'C' (new colour)

...[color=blue]B[/color]..
.[color=blue]B[/color].[color=blue]B[/color]..
.[color=blue]B[/color][color=blue]B[/color][color=blue]B[/color].[color=green]C[/color]
.....1

Continuing the scan.
A '1' is found at [5][3]. Neighbour coloured 'C' found, so colour this one 'C'

...[color=blue]B[/color]..
.[color=blue]B[/color].[color=blue]B[/color]..
.[color=blue]B[/color][color=blue]B[/color][color=blue]B[/color].[color=green]C[/color]
.....[color=green]C[/color]

Continuing the scan.
No more '1's found.
Two colours being used, so two components.

Mordecai

Well, that is a great system (and probably the best you'll probably get for this), but I wouldn't see how to use that information. It pretty much leaves you with the exact same thing you had in the first place, didn't it?

Weedpacket

Except now you can scan through all of the cells of each component separately. The minimum and maximum x and y values of those cells mark out the bounding box for that component.

foreach cell in field:
  if(cell is coloured)
    component[cell colour][] = array(cell coordinates);

Drawback: it assumes the bounding box is always oriented orthogonally. Having bounding boxes at an angle, or rather, knowing when they're needed, is more difficult. But at least now we've separated the components from each other, so that should make things easier.

Convex Hull, perhaps? Assuming (possibly rotated) rectangular regions makes things a bit easier. The distinguishing thing about the corners of a rectangle (as opposed to any of the other cells), is that no cell is lower than the bottom corner(s), higher than the upper corner(s), further left than the leftmost corner(s), or further right than the rightmost corner(s). We can see if the cells (leftmost,uppermost), (rightmost,lowermost), etc., are occupied; in which case the rectangle is oriented orthoginally and we have the bounding box right there. If not, we look for a cell that is lowermost, a cell that is leftmost, etc., and they will be the corners of our rectangle.

Of course, if there happen to be two lowermost cells (due to quantisation errors), then it's pretty much a toss-up which one you pick. You'll be a pixel off either way, but you can't expect much better when you're trying to wrap a rectangle around an octagon!

Mordecai

Well, that depends. What type of bounding box are we using here? Is it something like an HTML image map? In that case, you'd want to use actual pixels around the pac-man itself. If it is for copying the pac-man from one image to another, then you would need to use tightest-rectangular-fit, of course.

This has really turned into an interesting concept... 🙂

cyanblue

WoW... Thanks for the thorough explanation, Weedpacket... I am having my brain wash at the moment to understand this concept better and to apply it to what I have right now... I'll be back whether I get it going abit further or not... Wish me luck.. 🙂