Skip to content

Commit

Permalink
PR 1873 Review Comments
Browse files Browse the repository at this point in the history
  • Loading branch information
James McClain committed Dec 7, 2016
1 parent 75cab0d commit 30af5a3
Show file tree
Hide file tree
Showing 3 changed files with 127 additions and 87 deletions.
108 changes: 78 additions & 30 deletions ...er-test/src/test/scala/geotrellis/raster/rasterize/polygon/FractionalRasterizerSpec.scala
View file
Original file line number Diff line number Diff line change
Expand Up @@ -35,111 +35,159 @@ class FractionalRasterizerSpec extends FunSpec with Matchers {
val poly = Polygon(Point(1,1), Point(1,2), Point(2,2), Point(2,1), Point(1,1))
var actual = Double.NaN
val expected = 1.0

FractionalRasterizer.foreachCellByPolygon(poly, re) { (col: Int, row: Int, p: Double) =>
if (col == 1 && row == 1) actual = p
val cb = new FractionCallback {
def callback(col: Int, row: Int, p: Double): Unit =
if (col == 1 && row == 1) actual = p
}

FractionalRasterizer.foreachCellByPolygon(poly, re)(cb)

actual should be (expected)
}

it("should correctly not report disjoint pixels") {
val poly = Polygon(Point(1,1), Point(1,2), Point(2,2), Point(2,1), Point(1,1))
var actual = 0.0
val expected = 0.0

FractionalRasterizer.foreachCellByPolygon(poly, re) { (col: Int, row: Int, p: Double) =>
if (col != 1 && row != 1) actual += p
val cb = new FractionCallback {
def callback(col: Int, row: Int, p: Double): Unit =
if (col != 1 && row != 1) actual += p
}

FractionalRasterizer.foreachCellByPolygon(poly, re)(cb)

actual should be (expected)
}

it("should correctly report partial pixels") {
val poly = Polygon(Point(1,1), Point(1,2), Point(2,2), Point(1,1))
var actual = Double.NaN
val expected = 0.5

FractionalRasterizer.foreachCellByPolygon(poly, re) { (col: Int, row: Int, p: Double) =>
if (col == 1 && row == 1) actual = p
val cb = new FractionCallback {
def callback(col: Int, row: Int, p: Double): Unit =
if (col == 1 && row == 1) actual = p
}

FractionalRasterizer.foreachCellByPolygon(poly, re)(cb)

actual should be (expected)
}

it("should handle sub-pixel activity") {
val poly = Polygon(Point(1.2,1.2), Point(1.2,1.8), Point(1.8,1.8), Point(1.8,1.2), Point(1.2,1.2))
var actual = Double.NaN
val expected = 0.36

FractionalRasterizer.foreachCellByPolygon(poly, re) { (col: Int, row: Int, p: Double) =>
if (col == 1 && row == 1) actual = p
val cb = new FractionCallback {
def callback(col: Int, row: Int, p: Double): Unit =
if (col == 1 && row == 1) actual = p
}

FractionalRasterizer.foreachCellByPolygon(poly, re)(cb)

round(actual * 1000000) should be (round(expected * 1000000))
}

it("should handle a mix of partial and complete pixels") {
val poly = Polygon(Point(0.1,0.1), Point(0.1,2.9), Point(2.9,2.9), Point(2.9,0.1), Point(0.1,0.1))
var actual = 0.0
val expected = 2.8 * 2.8

FractionalRasterizer.foreachCellByPolygon(poly, re) { (col: Int, row: Int, p: Double) =>
actual += p
val cb = new FractionCallback {
def callback(col: Int, row: Int, p: Double): Unit =
actual += p
}

FractionalRasterizer.foreachCellByPolygon(poly, re)(cb)

round(actual * 1000000) should be (round(expected * 1000000))
}

it("should efficiently handle a long diagonal line (1/4)") {
it("should efficiently handle a long diagonal line (1/6)") {
val re = RasterExtent(e, 30, 30)
val poly = Polygon(Point(0,0), Point(3,0), Point(3,3), Point(0,0))
var actual = 0.0
val expected = (30*30)/2.0

FractionalRasterizer.foreachCellByPolygon(poly, re) { (col: Int, row: Int, p: Double) =>
actual += p
val cb = new FractionCallback {
def callback(col: Int, row: Int, p: Double): Unit =
actual += p
}

FractionalRasterizer.foreachCellByPolygon(poly, re)(cb)

round(actual * 1000000) should be (round(expected * 1000000))
}

it("should efficiently handle a long diagonal line (2/4)") {
it("should efficiently handle a long diagonal line (2/6)") {
val re = RasterExtent(e, 30, 30)
val poly = Polygon(Point(0,0), Point(3,0), Point(0,3), Point(0,0))
var actual = 0.0
val expected = (30*30)/2.0

FractionalRasterizer.foreachCellByPolygon(poly, re) { (col: Int, row: Int, p: Double) =>
actual += p
val cb = new FractionCallback {
def callback(col: Int, row: Int, p: Double): Unit =
actual += p
}

FractionalRasterizer.foreachCellByPolygon(poly, re)(cb)

round(actual * 1000000) should be (round(expected * 1000000))
}

it("should efficiently handle a long diagonal line (3/4)") {
it("should efficiently handle a long diagonal line (3/6)") {
val re = RasterExtent(Extent(0, 0, 3, 3.1), 30, 30)
val poly = Polygon(Point(0,0), Point(3,0), Point(0,3), Point(0,0))
var actual = 0.0
val expected = 435.483871

FractionalRasterizer.foreachCellByPolygon(poly, re) { (col: Int, row: Int, p: Double) =>
actual += p
val cb = new FractionCallback {
def callback(col: Int, row: Int, p: Double): Unit =
actual += p
}

FractionalRasterizer.foreachCellByPolygon(poly, re)(cb)

round(actual * 1000000) should be (round(expected * 1000000))
}

it("should efficiently handle a long diagonal line (4/4)") {
it("should efficiently handle a long diagonal line (4/6)") {
val re = RasterExtent(Extent(0, 0, 3.1, 3), 30, 30)
val poly = Polygon(Point(0,0), Point(3,0), Point(0,3), Point(0,0))
var actual = 0.0
val expected = 435.483871
val cb = new FractionCallback {
def callback(col: Int, row: Int, p: Double): Unit =
actual += p
}

FractionalRasterizer.foreachCellByPolygon(poly, re) { (col: Int, row: Int, p: Double) =>
actual += p
FractionalRasterizer.foreachCellByPolygon(poly, re)(cb)

round(actual * 1000000) should be (round(expected * 1000000))
}

it("should efficiently handle a long diagonal line (5/6)") {
val re = RasterExtent(Extent(0, 0, 3, 3.1), 30, 30)
val poly = Polygon(Point(0,0), Point(3,0), Point(0,3.1), Point(0,0))
var actual = 0.0
val expected = (30*30)/2.0
val cb = new FractionCallback {
def callback(col: Int, row: Int, p: Double): Unit =
actual += p
}

FractionalRasterizer.foreachCellByPolygon(poly, re)(cb)

round(actual * 1000000) should be (round(expected * 1000000))
}

it("should efficiently handle a long diagonal line (6/6)") {
val re = RasterExtent(Extent(0, 0, 3.1, 3), 30, 30)
val poly = Polygon(Point(0,0), Point(3.1,0), Point(0,3), Point(0,0))
var actual = 0.0
val expected = (30*30)/2.0
val cb = new FractionCallback {
def callback(col: Int, row: Int, p: Double): Unit =
actual += p
}

FractionalRasterizer.foreachCellByPolygon(poly, re)(cb)

round(actual * 1000000) should be (round(expected * 1000000))
}

Expand Down
4 changes: 3 additions & 1 deletion raster/src/main/scala/geotrellis/raster/rasterize/package.scala
View file
Original file line number Diff line number Diff line change
Expand Up @@ -26,5 +26,7 @@ package object rasterize {
* fraction is the fraction of the pixel which is covered by the
* query object.
*/
type FractionCallback = (Int, Int, Double) => Unit
trait FractionCallback {
def callback(col: Int, row: Int, fraction: Double): Unit
}
}
102 changes: 46 additions & 56 deletions raster/src/main/scala/geotrellis/raster/rasterize/polygon/FractionalRasterizer.scala
View file
Original file line number Diff line number Diff line change
Expand Up @@ -65,97 +65,88 @@ object FractionalRasterizer {
re: RasterExtent,
poly: Polygon,
set: mutable.Set[(Int, Int)],
fn: FractionCallback
cb: FractionCallback
): Unit = {
// Screen coordinates
val (x0, y0, x1, y1) = edge
val xmin = min(x0, x1)
val ymin = min(y0, y1)
val xmax = max(x0, x1)
val ymax = max(y0, y1)
val m = (y1 - y0) / (x1 - x0)

// Integral screen coordinates
val xminint = floor(xmin).toInt
val yminint = floor(ymin).toInt
val xmaxint = ceil(xmax).toInt
val ymaxint = ceil(ymax).toInt
// Grid coordinates
val colMin = floor(min(x0, x1)).toInt
val rowMin = floor(min(y0, y1)).toInt
val colMax = ceil(max(x0, x1)).toInt
val rowMax = ceil(max(y0, y1)).toInt

// Map coordinates
val xminmap = re.gridColToMap(xminint) - re.cellwidth/2
val yminmap = re.gridRowToMap(ymaxint) + re.cellheight/2
val xmaxmap = re.gridColToMap(xmaxint) - re.cellwidth/2
val ymaxmap = re.gridRowToMap(yminint) + re.cellheight/2
val xmin = re.gridColToMap(colMin) - re.cellwidth/2
val ymin = re.gridRowToMap(rowMax) + re.cellheight/2
val xmax = re.gridColToMap(colMax) - re.cellwidth/2
val ymax = re.gridRowToMap(rowMin) + re.cellheight/2

// Envelope around the edge (in map space)
val envelope = Polygon(
Point(xminmap, yminmap),
Point(xminmap, ymaxmap),
Point(xmaxmap, ymaxmap),
Point(xmaxmap, yminmap),
Point(xminmap, yminmap)
Point(xmin, ymin),
Point(xmin, ymax),
Point(xmax, ymax),
Point(xmax, ymin),
Point(xmin, ymin)
).jtsGeom

// Intersection of envelope and polygon (in map space)
val localPoly = poly.jtsGeom.intersection(envelope)

if (abs(m) <= 1) { // Mostly horizontal
var x = xminint; while (x <= xmaxint) {
if (abs(m) <= 1) { // The edge is mostly horizontal
var x = colMin; while (x <= colMax) {
val _y = floor(m * (x + 0.5 - x0) + y0).toInt
var i = -1; while (i <= 1) {
val y = _y + i
val pair = (x, y)
val xmap0 = re.gridColToMap(x+0) - re.cellwidth/2
val xmap1 = re.gridColToMap(x+1) - re.cellwidth/2
val ymap0 = re.gridRowToMap(y+0) + re.cellheight/2
val ymap1 = re.gridRowToMap(y+1) + re.cellheight/2
val pixelMinX = re.gridColToMap(x+0) - re.cellwidth/2
val pixelMaxX = re.gridColToMap(x+1) - re.cellwidth/2
val pixelMinY = re.gridRowToMap(y+0) + re.cellheight/2
val pixelMaxY = re.gridRowToMap(y+1) + re.cellheight/2
val pixel = Polygon(
Point(xmap0, ymap0),
Point(xmap0, ymap1),
Point(xmap1, ymap1),
Point(xmap1, ymap0),
Point(xmap0, ymap0)
Point(pixelMinX, pixelMinY),
Point(pixelMinX, pixelMaxY),
Point(pixelMaxX, pixelMaxY),
Point(pixelMaxX, pixelMinY),
Point(pixelMinX, pixelMinY)
).jtsGeom
val fraction = (pixel.intersection(localPoly)).getArea / pixel.getArea

if (fraction > 0.0) {
synchronized {
if (!set.contains(pair)) {
fn(x, y, fraction)
set += ((x, y))
}
if (!set.contains(pair)) {
set += ((x, y))
cb.callback(x, y, fraction)
}
}
i += 1
}
x += 1
}
} else { // Mostly vertical
} else { // The edge is mostly vertical
val m = (x1 - x0) / (y1 - y0)
var y = yminint; while (y <= ymaxint) {
var y = rowMin; while (y <= rowMax) {
val _x = floor(m * (y + 0.5 - y0) + x0).toInt
var i = -1; while (i <= 1) {
val x = _x + i
val pair = (x, y)
val xmap0 = re.gridColToMap(x+0) - re.cellwidth/2
val xmap1 = re.gridColToMap(x+1) - re.cellwidth/2
val ymap0 = re.gridRowToMap(y+0) + re.cellheight/2
val ymap1 = re.gridRowToMap(y+1) + re.cellheight/2
val pixelMinX = re.gridColToMap(x+0) - re.cellwidth/2
val pixelMaxX = re.gridColToMap(x+1) - re.cellwidth/2
val pixelMinY = re.gridRowToMap(y+0) + re.cellheight/2
val pixelMaxY = re.gridRowToMap(y+1) + re.cellheight/2
val pixel = Polygon(
Point(xmap0, ymap0),
Point(xmap0, ymap1),
Point(xmap1, ymap1),
Point(xmap1, ymap0),
Point(xmap0, ymap0)
Point(pixelMinX, pixelMinY),
Point(pixelMinX, pixelMaxY),
Point(pixelMaxX, pixelMaxY),
Point(pixelMaxX, pixelMinY),
Point(pixelMinX, pixelMinY)
).jtsGeom
val fraction = (pixel.intersection(localPoly)).getArea / pixel.getArea

if (fraction > 0.0) {
synchronized {
if (!set.contains(pair)) {
fn(x, y, fraction)
set += ((x, y))
}
if (!set.contains(pair)) {
set += ((x, y))
cb.callback(x, y, fraction)
}
}
i += 1
Expand All @@ -168,17 +159,16 @@ object FractionalRasterizer {
def foreachCellByPolygon(
poly: Polygon,
re: RasterExtent
)(fn: FractionCallback): Unit = {
)(cb: FractionCallback): Unit = {
val seen = mutable.Set.empty[(Int, Int)]
val option = Rasterizer.Options(includePartial = false, sampleType = PixelIsArea)

polygonToEdges(poly, re)
.par
.foreach({ edge => renderEdge(edge, re, poly, seen, fn) })
.foreach({ edge => renderEdge(edge, re, poly, seen, cb) })

PolygonRasterizer.foreachCellByPolygon(poly, re) {(col: Int, row: Int) =>
val pair = (col, row)
if (!seen.contains(pair)) fn(col, row, 1.0)
if (!seen.contains(pair)) cb.callback(col, row, 1.0)
}
}

Expand Down

0 comments on commit 30af5a3

Please sign in to comment.