replace bubble sort with a faster algorithm

[DoubleCouponDay]

The algorithm must be able to handle arrays which have no measure of inequality.

[DoubleCouponDay]

Struggles particularly with this image: link

It's evident the sorting scales badly with pixel count.

[DoubleCouponDay]

not just bubble sort. sort.c is the bottleneck, based on performance of logs.

[DoubleCouponDay]

plan:

• Extend algorithm threads into sorting.
• Append the shape lists after sorting has completed.
• Iterate from the first chunk of every border list. If the chunk is adjacent and was not used before and is in the same shape and is a boundary chunk, set that as the next chunk.
• set current chunk equal to the next boundary chunk and repeat until done.

[DoubleCouponDay]

as of 03625c5
sort.c line 53: current_list is set to null and causes null reference behaviour.

[DoubleCouponDay]

infinite loop at sort.c line 84. only occurs in thread 3.

my guess is that in some cases, next chunk never circles back around to the first chunk.

[DoubleCouponDay]

currently working on sorting in place during the algorithm, instead of sorting after all shapes created.

[DoubleCouponDay]

Sorting in place requires too many assumptions with very few indicators on the best course of action. I propose a new plan:

• Clone opencl and link with it.
• Create an opencl kernel written in opencl C.
• The kernel must perform boundary comparison matrices of each pixel with each of their adjacent pixels to create 8 2D arrays of boolean values.
• Put each of the 8 matrix computations in a separate thread.
• Put each layer in a separate thread.
• The comparisons can be done using bitwise OR operations, 32 or 64 bit long depending on the platform architecture. This will aggregate the boundary statuses into the output 2D array.
• Iterate through all boundary chunks and path find each one, checking that its Neighbours are not already in a shape.
• Do not path find a chunk if it was already used.
• Zip each boundary chunk in the direction of the angle between its two adjacent boundary chunks.

[DoubleCouponDay]

Instead of Layers, Adaptive Thresholding should be used so that the right threshold is used for each area. the chunksize variable could be repurposed for this. Chunksize will be the width of a square in which the mean magnitude in 3D is calculated.

To calculate the mean, use the following formula:
mean = Sigma(total of all magnitudes) / number of magnitudes

[DoubleCouponDay]

Getting a faster algorithm using Adaptive Thresholding requires some concessions to be made in terms of complexity. For the time being I propose that OpenCL research be discontinued until Version 3 is finalized.

• Read chunksize as int

• Divide the image into chunks

• Foreach chunk calculate the mean magnitude of the RGB pixels in the chunk
  each value is a dimension

  store each mean in a reduced 2d array of chunks where xy coords can work

• Use the mean as the threshold value for that chunk

• Split vectorizing into 8 directions, one for each direction, one thread per split

• Foreach split, perform boundary comparison between two pixels along a the split direction

• Aggregate all splits together using bitwise OR operations on rows of pixels

• Pathfind the aggregate
  do not pathfind a pixel that has already been used

• Write paths to svg file