YouTube video: http://youtu.be/j9XmhYavnZU
Optimized Sort further -- seconds to fill ->
Blue Yellow Green Red
ASUS TF-101 1 2 3 6
NextBook 7" 3 4 5 12
Updated aia and apk files
Some times to fill areas on the above picture on my ASUS TF-101 tablet:
Blue area - 1 second
Yellow area = 2 seconds
Green area - 3 seconds
red area - 6 seconds
Tested Shell sort, insertion sort
Shell sort is about 60% faster than bubble sort, but it does not fill completely
Insertion sort is a bit slower than bubble sort
New aia source is still version 2.0
Removed the number to integer text conversion. It was not necessary.
New project version is 2.0
Some times to fill areas on the above picture on my $69 Nextbook 7" tablet:
Blue area - 3 seconds
Yellow area - 5 seconds
Green area - 7 seconds
red area - 14 seconds
'Nanobot' concept dropped in favor of simpler X, Y, H values.
Changed the method from boundary fill to flood fill -- boundary color determined by the fill procedure.
The developer must provide any x,y location inside the area to fill and a fill color.
Lookup tables for offsets to color sensors replaced with trigonometry sin and cos functions.
Nanobot redesigned - now consists of main body, left color sensor, front color sensor for detecting the boundary to the left and front;
Left color sensor was moved from diagonal left-front position to left side of the body;
logic for filling was modified and simplified to reflect the new design
performance is too slow - your help is needed to improve efficiency and speed of any of the steps outlined below
140118: 1st DRAFT
This project paints the inside of an area on the canvas that is surrounded by any other colors by:
- building a list of points along the perimeter of the area
- sorting the points
- filling the figure
Any drawn picture or BackgroundImage can be used, but the color to be filled must be a simple solid color.
If the color contains a transparency value other than 255, the new fill color will blend with the existing color in the fill area.
These 3 steps to build, sort then fill are described in detail below:
1. building a list of points inside the figure boundary
This is accomplished by using the left-hand rule of maze solving.
After the initial touch at the x,y location to be filled, the BackgroundPixelColor is determined and the canvas is scanned to the right until the color changes.
This marks the StartX, StartY of the edge of the area to be filled.
From this point on, the edge is followed in a clockwise direction by advancing X and Y and keeping track of the current heading H which is initially 270 (South).
The heading H value changes by 90 degree increments as the edge is followed.
These will always be 0 (right),90 (up),180 (left), or 270 degrees (down).
Whenever H is 270, a right point should be stored.
Whenever H is 90, a left point should be stored.
This will allow the DrawLine block to be used to fill the area later.
Two lists are used to store these points - LeftPoints and RightPoints.
When StartX, StartY and the starting H (270) have been reached again, the lists are complete and the entire perimeter has been followed.
You can skip to the Sorting section now unless you wish to understand how the edge of the area to be filled is followed below.
Following the edge of an area using BackgroundPixelColor
X and Y represent the location of the current pixel on the canvas inside the area to be filled.
Associated with this location or point are locations in front of (F) and to the left (L) of X,Y that are used to read the current BackgroundPixelColor.
In addition, these locations rotate around the X,Y position as the heading value H changes.
Using X,Y and H a routine can be used to follow the perimeter of the area to be filled.
As the perimeter is followed, the two lists of points created will later be sorted and used as arguments to the Canvas Drawline block in order to fill the figure with a specified color.
A conceptual model of the three pixels involved might look like the following:
a virtual body N, a left color sensor L, a front sensor F:
In this example, F is to the right of N so the model is facing right or 0 degrees.
It's location on the Canvas and current heading are required to know the position of it's two color sensors at any time.
These values are stored in three variables:
X, Y, H
The convention for App Inventor's canvas for sprites (ImageSprite, Ball) is that their Heading property values start at 0 degrees (right), and increase in value in a counter-clockwise direction so 0 degrees is to the right, 90 degrees is up, 180 degrees is to the left and 270 degrees is down.
These are the only angles that are required.
When the heading H changes, it is by +90 degrees (counter-clockwise) or -90 degrees (clockwise) only.
When the X,Y location changes, it is by one-pixel increments and the current heading H determines how X or Y are changed as explained below.
For the following values of H the relative locations of L and F can be seen
0: L 90: F 180: FN 270: NL
NF LN L F
This can be shown in the following example:
H = 0:
Only the location of N (X,Y) and H are known, but the locations of L and F can be derived from these as offsets from N's location:
These values can be obtained with App Inventor's Math sin(H) and cos(H) functions:
H 0 90 180 270
sin(H) 0 1 0 -1
cos(H) 1 0 -1 0
-sin(H) 0 -1 0 1
-cos(H) -1 0 1 0
If N's location is at (4,3) on the Canvas then L and F are located at the following offsets from N
H = 0
L (4 + 0,3 - 1) Lo (0,-1); -sin(0) = 0, -cos(0) = -1
F (4 + 1,3 + 0) Fo (1,0); cos(0) = 1, -sin(0) = 0
H = 90
Lo (-1,0); -sin(90) = -1, -cos(90) = 0
Fo (0,-1); cos(90) = 0, -sin(90) = -1
H = 180
Lo (0,1); -sin(180) = 0, -cos(180) = 1
Fo (-1,0); cos(180) = -1, -sin(180) = 0
H = 270
Lo (1,0); -sin(270) = 1, -cos(270) = 0
Fo (0,1); cos(270) = 0, -sin(270) = 1
The same method used to rotate the 'color sensor' L and F pixels around N's X,Y location is used to move N a pixel to the right, left, up or down by adding or subtracting pixels to the X and Y values.
To move the X,Y location one pixel based on the current H:
set X to X + cos(H)
set Y to Y - sin(H)
If X,Y is 4,3 and H = 90:
then 4 + cos(90) = 4 and 3 - sin(90) = 2
so the new X,Y location is 4,2
General logic for following the edge:
Whenever L is outside the area to be filled, then a point may need to be added to the LeftPoints (H = 90) or RightPoints (H = 270)list.
Note: in the examples below, the O's represent a different color outside of the area to fill.
N is always inside the area to fill.
Color under L is not the inside color and color under F is the inside color
(following straight edge) .
(L is over an O)
Color under L is inside color
(L is not over an O)
Color under L is outside color
(L is over an O)
Color under L is not the inside color and color under F is not the inside color.
(L and F are over Os)
(L is over an O)
END Following the edge of an area using BackgroundPixelColor
2. Sorting the LeftPoints and RightPoints lists with the procedure SortOrderedPairsByYThenX.
The two lists built in step 1 contain left and right points for the lines to fill the figure.
These lists are called LeftPoints and RightPoints as the lines will be drawn left-to-right.
When following the edge of the fill area, if H = 90 (pointing up), points are added to LeftPoints. When H = 270, (pointing down), points are added to RightPoints.
No points are added when H = 180 or 0.
Once the points have all been added to the two lists, they must be sorted first by the lowest to highest y value, then by the lowest to highest x value.
In Step 3, the sorted points will be used as arguments to the Canvas DrawLine block to fill the figure with the DrawLine.Timer block.
END Sorting the LeftPoints and RightPoints lists
3. Filling the figure with LeftPoints, RightPoints and the Canvas DrawLine block
Once all endpoints needed by the DrawLine block are sorted, a simple loop can be used to draw each line to fill the figure.
I noticed that the Right endpoint causes the lines to stop one pixel away from the right edge of a figure.
To correct this I added one pixel to the right side of each line as the Rightpoints list was being built.
END Filling the figure