SmallSketch
about
ss one

Let's make your drawing simple with the Ramer–Douglas–Peucker algorithm

Previous post, How to get native ss one data from SVG that is exported from ss one, I explained how to get ss one drawing native data. This post, I will try using the Ramer–Douglas–Peucker algorithm in order to make it change to (a kind of) simple.

This is a test data a-coffee-cup.svg:

a-coffe-cup

At first, create a main.kts kotlin script to convert ss one's SVG data. This script do that:

  1. pick up native ss one point list data
  2. and convert that data with SVG

main.kts

import org.xml.sax.helpers.DefaultHandler
import org.xml.sax.Attributes

import javax.xml.parsers.SAXParser
import javax.xml.parsers.SAXParserFactory

import java.io.InputStream
import java.io.File

class MyHandler(
    private val callbackStrokeData: (String)->Unit,
    private val callbackDocumentEnd: ()->Unit) : DefaultHandler() {

    private var underStrokeElement = false

    override fun startElement(
        uri: String,
        localName: String,
        qName: String,
        attrs: Attributes) {

        if( qName=="ss:stroke" ){ underStrokeElement = true }
    }

    override fun endElement(uri: String, localName: String, qName: String){
        if( qName=="ss:stroke" ){ underStrokeElement = false }
    }

    override fun characters(ch: CharArray, start: Int, length: Int) {
        if( underStrokeElement ){
            val xyParams = 0.until(length).map { index->
                "${ch[start + index]}"
            }.joinToString("")
    
            callbackStrokeData(xyParams)
        }
    }

    override fun endDocument(){
        callbackDocumentEnd()
    }
}

typealias Stroke = List<Pair<Float,Float>>

val toSVGPath: (Stroke)->String = {stroke->
    val head = stroke.first()
    val tail = stroke.drop(1)
    val data = listOf(
        listOf("M ${head.first} ${head.second}"),
        tail.map { "L ${it.first} ${it.second}" }
    ).flatten().joinToString(" ")

    "<path d=\"${data}\"/>"
}


if( args.size>1 ){
    val inputSvgFilename = args[0]
    val outputSvgFilename = args[1]

    val inputSvgFile = File(inputSvgFilename)
    val outputSvgFile = File(outputSvgFilename)
    
    val factory = SAXParserFactory.newInstance()
    val parser = factory.newSAXParser()

    val pathList = mutableListOf<String>()

    val callbackStrokeData: (String)->Unit = { xyParams->
        val xyList = xyParams.split(",").map { it.toFloat() }
        val xList  = xyList.mapIndexed { index, value-> if(index%2==0){ value } else { null } }.mapNotNull{ it }
        val yList  = xyList.mapIndexed { index, value-> if(index%2==1){ value } else { null } }.mapNotNull{ it }
    
        val ptList = xList.zip(yList)
        val path = toSVGPath(ptList)
        pathList.add(path)
    }

    val callbackDocumentEnd: ()->Unit = {
        val w = "34.882454"
        val h = "37.46071"

        val header = listOf(
            "<?xml version=\"1.0\" encoding=\"utf-8\"?>",
            "\n",
            "<!DOCTYPE svg PUBLIC ",
                "\"-//W3C//DTD SVG 1.1//EN\" ",
                "\"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">",
            "<svg ",
                "xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" ",
                "x=\"0mm\" y=\"0mm\" width=\"${w}mm\" height=\"${h}mm\" ",
                "viewBox=\"0.0 0.0 ${w} ${h}\">")

        val body = listOf(
            "<g stroke=\"rgb(76, 96, 130)\" stroke-width=\"0.254\" fill=\"none\">",
            pathList.joinToString(""),
            "</g>")
        val footer = listOf("</svg>")

        val svg = (header + body + footer).joinToString("")

        outputSvgFile.writer(Charsets.UTF_8).use { writer->
            writer.write(svg)
        }
    }

    val handler = MyHandler(callbackStrokeData, callbackDocumentEnd)
    
    inputSvgFile.inputStream().use { inputStream->
        parser.parse(inputStream, handler)
    }
}

Output SVG w and h values are hard coded for now.

Before running this code, check kotlinc version:

$ kotlinc -version
info: kotlinc-jvm 1.8.10 (JRE 17.0.7+7-Ubuntu-0ubuntu122.04.2)

Run this code:

$ kotlinc -script main.kts a-coffee-cup.svg out1.svg

This code do nothing for drawing points, so it looks no change original data.

a-coffe-cup, out1

Use the Ramer–Douglas–Peucker algorithm

Next, applying the Ramer–Douglas–Peucker algorithm to this drawing.

Change the callbackStrokeData function:

    val epsilon = 0.5.toDouble() 

    val callbackStrokeData: (String)->Unit = { xyParams->
        //val xyList = xyParams.split(",").map { it.toFloat() }

        val xyList0 = xyParams.split(",").map { it.toFloat() }
        val xyList  = LineSimple.convertPts( xyList0, epsilon )

        val xList  = xyList.mapIndexed { index, value-> if(index%2==0){ value } else { null } }.mapNotNull{ it }
        val yList  = xyList.mapIndexed { index, value-> if(index%2==1){ value } else { null } }.mapNotNull{ it }
    
        val ptList = xList.zip(yList)
        val path = toSVGPath(ptList)
        pathList.add(path)
    }

The epsilon value is key factor for how much simple it is. Here I set it 0.5. And LineSimple.convertPts function is necessary. I will show this code after. Now anyway show you this code result , the simplified coffee cup drawing.

a-coffe-cup, out2

When use epsilon value 0.5 in this drawing, data size is less about 1/10 than original.

LineSimple.convertPts Function

LineSimple.kt

data class PointD(val x: Double, val y: Double)

object LineSimple {
    private fun perpendicularDistance(
        pt: PointD,
        lineStart: PointD,
        lineEnd: PointD): Double {

        val dx0 = lineEnd.x - lineStart.x
        val dy0 = lineEnd.y - lineStart.y

        val mag: Double = Math.hypot(dx0, dy0)
        val dx = if (mag > 0f) { dx0 / mag } else { dx0 }
        val dy = if (mag > 0f) { dy0 / mag } else { dy0 }

        val pvx = pt.x - lineStart.x
        val pvy = pt.y - lineStart.y

        val pvdot = dx * pvx + dy * pvy
 
        val ax = pvx - pvdot * dx
        val ay = pvy - pvdot * dy
 
        return Math.hypot(ax, ay)
    }

    private fun ramerDouglasPeucker(
        pointList: List<PointD>,
        epsilon: Double,
        outputPointList: MutableList<PointD>){

        val pointListSize = pointList.size
        if (pointListSize < 2){
            outputPointList.addAll( pointList )
        } else {
            val firstPoint = pointList.first()
            val lastPoint  = pointList.last()

            val dList     = 1.until(pointListSize).map {
                perpendicularDistance(pointList[it], firstPoint, lastPoint)
            } 
            val indexList = 1.until(pointListSize).map { it }
    
            val result: Pair<Double, Int> = dList.zip(indexList).fold(Pair<Double,Int>(0.toDouble(), 0)) { acc, next->
                val dmax = acc.first
                val d    = next.first
                if( d > dmax ){
                    val index = next.second
                    Pair<Double,Int>(d, index)
                } else {
                    acc
                }
            }
    
            val dmax = result.first
            val index = result.second

            if ( (dmax > epsilon) && ((index+1) < pointListSize)) {
                val recResults1 = mutableListOf<PointD>()
                val recResults2 = mutableListOf<PointD>()
    
                val firstLine = pointList.subList(0, index + 1)
                val lastLine  = pointList.subList(index, pointListSize)
    
                   ramerDouglasPeucker(firstLine, epsilon, recResults1)
                   ramerDouglasPeucker(lastLine,  epsilon, recResults2)
    
                outputPointList.addAll(recResults1.subList(0, recResults1.size - 1))
                outputPointList.addAll(recResults2)
                if (outputPointList.size < 2){
                    outputPointList.addAll( pointList )
                }
            } else {
                outputPointList.clear()
                outputPointList.add(pointList.first())
                outputPointList.add(pointList.last())
            }
        }
    }

    fun convertPts(pts: List<Float>, epsilon: Double): List<Float> {
        val lenHalf = pts.size/2
        val pointList = 0.until(lenHalf).map { i->
            val pointer = i*2
            PointD(pts[pointer].toDouble(), pts[pointer+1].toDouble())
        }
    
        val outputPointList = mutableListOf<PointD>()
        LineSimple.ramerDouglasPeucker(pointList, epsilon, outputPointList)
    
        return outputPointList.map {
            listOf(it.x.toFloat(), it.y.toFloat())
        }.flatten()
    }
}

To run main.kts with LineSimple.kt together, do this:

$ kotlinc LineSimple.kt -d LineSimple.jar
$ kotlinc -cp LineSimple.jar -script main.kts a-coffee-cup.svg out.svg

or create a Makefile and do make:

INPUTSVG:=a-coffee-cup.svg
OUTPUTSVG:=out.svg

run: LineSimple.jar
	kotlinc -cp $< -script main.kts $(INPUTSVG) $(OUTPUTSVG)

LineSimple.jar: LineSimple.kt
	kotlinc $< -d $@

Wrap up

Using this points reduce way, you can shrink you data or change your drawings as a kind of simple.

More code details, see this github repository: