Repository navigation
Repaired non-robust Delaunay triangulator. - #1699
Conversation
…n of the JTS triangulator
|
@jpolchlo you made benchmarks for the old voronio, right? Is it possible to rerun those benchmarks, against the two different versions, to see if we're losing a lot of speed? |
|
You and I sat down to look at benchmarks, but I didn't write them myself, On Tue, Oct 25, 2016 at 11:08 AM, Rob Emanuele [email protected]
|
|
@jpolchlo the idea is to have a sense of how much things have slowed down. And to have an idea of how efficient this operation is...I remember that you were calculating triangulations on the nickel dataset in about 200ms. If this turns out to be a 2x vs a 10x slowdown, that would be good to understand. If it's a serious slowdown, I'd want to either try to optimize before release or at least put in an issue for future optimization. |
|
Roger, boss. I'll see what I can figure out. On Tue, Oct 25, 2016 at 10:47 PM, Rob Emanuele [email protected]
|
| val cm = ColorMap(scala.collection.immutable.Map(1 -> 0x000000ff, 255 -> 0xffffffff)) | ||
| tile.renderPng(cm).write("delaunay.png") | ||
| } | ||
| */ |
There was a problem hiding this comment.
What's going on with all the commented code here?
| } | ||
|
|
||
| it("should work on a real dataset with many collinear points") { | ||
| val allcities = ResourceReader.asString("populous_cities.txt") |
There was a problem hiding this comment.
We don't normally read test data out of resources packed in the JAR - is there an advantage you see of doing it this way, other then adding to test files similar to other tests? We would put it here https://github.com/geotrellis/geotrellis/tree/master/vector-test/data
| import java.io._ | ||
|
|
||
| object ResourceReader { | ||
| def asString(filename: String): String = { |
There was a problem hiding this comment.
This is for test functionality, not sure it's worth putting in the core utils JAR
There was a problem hiding this comment.
Had talked to Eugene about this. He suggested putting it in util, but it's not super valuable, so I'll nuke it.
…diagram (JTS requires no testing)
| * boundary(.next)*.face == None. | ||
| */ | ||
| val boundary = triangulate(0, vIx.length-1) | ||
| val triangles = _triangles.map{ poly => Polygon.jtsToPolygon(poly.asInstanceOf[JTSPolygon]) } |
There was a problem hiding this comment.
can just use Polygon(poly.asInstanceOf[JTSPolygon]
|
|
||
| import org.scalatest.{FunSpec, Matchers} | ||
|
|
||
| class DelaunaySpec extends FunSpec with Matchers { |
There was a problem hiding this comment.
Should we really scrap all these tests? I think still testing our JTS backed Delaunay class makes sense.
There was a problem hiding this comment.
As much as I would like to provide some unit tests here, I'm just at a loss for what should be tested. It seems that most anything that I could test for tests JTS's feature set, and not the features of this package. I'm not sure if that's appropriate. As it is, there is an indirect test of Delaunay and Voronoi in the EuclideanDistanceTileSpec. I'd be happy for some suggestions about what should be tested for in these classes!
There was a problem hiding this comment.
After some discussion, we've opted to re-insert some tests essentially as regression tests.
| } | ||
| private val _triangles = { | ||
| val tris = subd.getTriangles(gf) | ||
| for ( i <- 0 until tris.getNumGeometries ) yield tris.getGeometryN(i) |
There was a problem hiding this comment.
use a cfor loop for performance...also do we need the private val?
import spire.syntax.cfor._
val triangles: Seq[Polygon] = {
val arr = Array.ofDim[Polygon](tris.getNumGeometries)
val len = arr.length
cfor(0)(_ < len, _ + 1) { i =>
arr(i) = Polygon(tris.getGeometryN(i).asInstanceOf[JTSPolygon])
}
arr
}
2 participants
This PR replaces the custom, non-robust Delaunay triangulator with wrapped version of the JTS triangulator. The old triangulator did not implement robust predicates for collinearity/cocircularity which could cause failures in some real-world data sets.
The JTS triangulator was wrapped to allow a more idiomatic Scala usage. Namely, allowing for PointFeatures to be used more easily, which would facilitate the use of a triangulation for the purposes of, say, interpolating a field of numbers defined over a sample of points. This wrapped version also replaces the quad-edge structure used by JTS for a lighter-weight half-edge structure. Documentation for that structure can be found in docs/vector/voronoi.md.
This PR closes issue #1683.