trjhtr

Given a shape (a closed LineString, i.e. sequence of Points, where the first and the last points are equal) that contains other duplicates than the first and last point.

The algorithm finds all duplicated points and for each deletes all of them but one(or two). The tricky part is to decide which to keep: if either is equal to the first or last, keep it. Else keep the one, that has the least areal error.

object PolygonValidator 
 class LineString(val lineString: Seq[LngLat]) 
 def closeLine: Seq[LngLat] = lineString match 
 case head :: tail if head != tail.last ⇒ lineString :+ head
 case closedLine ⇒ closedLine
 

 /**
 * calculates a number representing the area surrounded of the given lineString.<br/>
 * assumes a flat interpretation, so use only for smaller geometries.
 *
 * @return <ul><li>value > zero when lineString is oriented clockwise<li>value < zero when lineString is oriented counter clockwise<li>zero when area is empty</ul>
 */
 def areaRepresentation: Double = pairwise(lineString).foldLeft(0d)((sum, line) ⇒ line match 
 case (a, b) ⇒ sum + (b.lng - a.lng) * (b.lat + a.lat)
 )
 

 implicit def seqToLineString(s: Seq[LngLat]): LineString = new LineString(s)

 def findDuplicate[C](shape: Seq[C]): Seq[C] = shape.tail.diff(shape.tail.distinct).distinct.reverse

 private def pairwise[C](linear: Seq[C]): Seq[(C, C)] = linear.zip(linear.tail)

 def removeDoublePoints(shape: Seq[LngLat]): Seq[LngLat] = 
 var pointsToDelete: Set[Int] = Set()
 for (duplicate ← findDuplicate(shape)) 
 val positionsOfDuplicate: Seq[Int] = shape.zipWithIndex.filter(_._1 == duplicate).map(_._2)
 // […]
 
 // keep original point with the smallest error
 // TODO: make nicer :)
 var start = if (positionsOfDuplicate.head == 0) 1 else 0
 var end = if (positionsOfDuplicate.last == shape.size - 1) positionsOfDuplicate.size - 1 else positionsOfDuplicate.size
 if (start == 0 && end == positionsOfDuplicate.size) 
 // we need to keep either
 val startIdx = positionsOfDuplicate.head
 val endIdx = positionsOfDuplicate.last
 val startError = shape.slice(startIdx - 1, startIdx + 2).closeLine.areaRepresentation.abs
 val endError = shape.slice(endIdx - 1, endIdx + 2).closeLine.areaRepresentation.abs
 if (startError > endError) start += 1
 else end -= 1
 
 pointsToDelete = pointsToDelete ++ positionsOfDuplicate.slice(start, end)
 
 shape.zipWithIndex.filterNot( case (_, idx) ⇒ pointsToDelete.contains(idx) ).map(_._1)
 

}

The part I am not so happy with is the big block in the removeDoublePoints function that only determines whether we should keep the first or the last of the given duplicate points.

Who has a nicer i.e. more readable or shorter version?