Traversing a irregular shape closed area with islands

[vcmohan]

Given a starting point (or a straight line) within an irregular shape closed area with islands, how can one ensure that the area, excepting the islands, is fully examined (traversed)at least once? I have tried eight directional paths but find that the examination ends after getting stuck in one tight spot, where either all adjacent pixels were already examined or area is locally only one pixel wide.
I ran into this problem while developing a plugin for Avisynth and appreciate if some one can help.

[Bidoche]

Maybe a font scanline converter logic, where it converts a shape into a 'list' of lit pixels, is what you need.

I made one for 3.0 so I can explain it to you if you want.

[Guest]

That sounds like a standard fill problem. Google for area fill algorithm.

[vcmohan]

A lot of thanks for suggestions.
Bidoche: Will appreciate if you can explain your list process.

[Fizick]

May be not directly related, but some spot detection exists in DeSpot plugin.

[Bidoche]

@vcmohan

For each y (considered) you maintain two list (of x):
a list of entering transitions and a list of exiting transitions.

Then given a filling convention, you walk the shape contours to fill those lists. (May need to split the shape into line segments)

That is to say that for each y you cross, you mark the corresponding x as a entering or exiting transition, depending if you are going up or down and the filling convention chosen.

Once it is done for all contours (islands too).
For each y, you sort the entering and exiting transitions list.
Then you just have to pair entering and exiting transition together to get horizontal spans of lit pixels. (kindof 'list')

Eventually those spans may need some merging if your shape allowed overlapping of contours.


If you want to look, 3.0 code for that is in src/text/rasterizer/(Beware intensive use of the STL)

[vcmohan]

Thanks. But I am not sure whether it works in the situation I am in. Let me explain further. On the image there are a number of complicated shaped closed ares, islands etc. Only a black line demarcates these boundaries. So if I traverse from outside the area, I may be entering and exiting a number of such areas and will not know which contiguous area I am in. My search is therefore starting from within the area. I must ensure that I traverse fully all that irregular area including tight spots etc without getting stuck.

I am employing an eight directional search, but as I explained above getting stuck in tight spots. It appears that if I alter the order of the directions I search, at different places I get stuck. One solution appears as 8! types of searches, which is terrible to code and may not result in a fast enough solution.

Well I am trying Google search. Yesterday while doing it my system suddenly slowed down and my Firefox behaved strange. Later I realised that it did an automatic update and all my bookmarks lost. This is just an aside. Sorry for it if I violated any rule of forum.

[Bidoche]

Originally posted by vcmohan
Thanks. But I am not sure whether it works in the situation I am in. Let me explain further. On the image there are a number of complicated shaped closed ares, islands etc. Only a black line demarcates these boundaries. So if I traverse from outside the area, I may be entering and exiting a number of such areas and will not know which contiguous area I am in.

That logic should always work, even with extremly complex shapes.
The only flaw is that, since it tests if the pixel center is in the area, it can miss small details avoiding pixel centers.
But then it can be solved by working at a higher precision.