{"action":"created","comment":{"url":"https://api.github.com/repos/geotrellis/geotrellis/pulls/comments/67625436","id":67625436,"diff_hunk":"@@ -0,0 +1,327 @@\n+package geotrellis.vector.voronoi\n+\n+import geotrellis.util.Constants.{DOUBLE_EPSILON => EPSILON}\n+import geotrellis.vector._\n+import scala.math.pow\n+import org.apache.commons.math3.linear._\n+import scala.collection.mutable.Map\n+//import org.apache.log4j.Logger\n+\n+object Predicates {\n+  def det3 (a11: Double, a12: Double, a13: Double,\n+            a21: Double, a22: Double, a23: Double,\n+            a31: Double, a32: Double, a33: Double): Double = {\n+    val m = MatrixUtils.createRealMatrix(Array(Array(a11,a12,a13),Array(a21,a22,a23),Array(a31,a32,a33)))\n+    (new LUDecomposition(m)).getDeterminant\n+  }\n+    \n+\n+  def isCCW(a: Point, b: Point, c: Point): Boolean = {\n+    // det [ a.x-c.x  a.y-c.y ]\n+    //     [ b.x-c.x  b.y-c.y ] > 0\n+    (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x) > EPSILON\n+  }\n+\n+  def isCCW(ai: Int, bi: Int, ci: Int)(implicit trans: Int => Point): Boolean = {\n+    val a = trans(ai)\n+    val b = trans(bi)\n+    val c = trans(ci)\n+    (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x) > EPSILON\n+  }\n+\n+  def isRightOf[T](e: HalfEdge[Int,T], p: Point)(implicit trans: Int => Point) = \n+    isCCW(p, trans(e.vert), trans(e.src))\n+\n+  def isRightOf[T](e: HalfEdge[Int,T], p: Int)(implicit trans: Int => Point) = \n+    isCCW(trans(p), trans(e.vert), trans(e.src))\n+\n+  def isLeftOf[T](e: HalfEdge[Int,T], p: Point)(implicit trans: Int => Point) = \n+    isCCW(p, trans(e.src), trans(e.vert))\n+\n+  def isLeftOf[T](e: HalfEdge[Int,T], p: Int)(implicit trans: Int => Point) = \n+    isCCW(trans(p), trans(e.src), trans(e.vert))\n+\n+  def inCircle(abc: (Point, Point, Point), d: Point): Boolean = {\n+    val (a,b,c) = abc\n+    det3(a.x-d.x, a.y-d.y, pow(a.x-d.x,2) + pow(a.y-d.y,2),\n+         b.x-d.x, b.y-d.y, pow(b.x-d.x,2) + pow(b.y-d.y,2),\n+         c.x-d.x, c.y-d.y, pow(c.x-d.x,2) + pow(c.y-d.y,2)) > EPSILON\n+  }\n+\n+  def inCircle(abc: (Int, Int, Int), di: Int)(implicit trans: Int => Point): Boolean = {\n+    val (ai,bi,ci) = abc\n+    val a = trans(ai)\n+    val b = trans(bi)\n+    val c = trans(ci)\n+    val d = trans(di)\n+    det3(a.x-d.x, a.y-d.y, pow(a.x-d.x,2) + pow(a.y-d.y,2),\n+         b.x-d.x, b.y-d.y, pow(b.x-d.x,2) + pow(b.y-d.y,2),\n+         c.x-d.x, c.y-d.y, pow(c.x-d.x,2) + pow(c.y-d.y,2)) > EPSILON\n+  }\n+\n+  def circleCenter(a: Point, b: Point, c: Point): Point = {\n+    val d = 2.0 * det3(a.x,a.y,1.0, b.x,b.y,1.0, c.x,c.y,1.0)\n+    val h = det3(a.x*a.x+a.y*a.y,a.y,1.0, b.x*b.x+b.y*b.y,b.y,1.0, c.x*c.x+c.y*c.y,c.y,1.0) / d\n+    val k = det3(a.x,a.x*a.x+a.y*a.y,1.0, b.x,b.x*b.x+b.y*b.y,1.0, c.x,c.x*c.x+c.y*c.y,1.0) / d\n+    Point(h,k)\n+  }\n+\n+  def circleCenter(ai: Int, bi: Int, ci: Int)(implicit trans: Int => Point): Point = {\n+    val a = trans(ai)\n+    val b = trans(bi)\n+    val c = trans(ci)\n+    val d = 2.0 * det3(a.x,a.y,1.0, b.x,b.y,1.0, c.x,c.y,1.0)\n+    val h = det3(a.x*a.x+a.y*a.y,a.y,1.0, b.x*b.x+b.y*b.y,b.y,1.0, c.x*c.x+c.y*c.y,c.y,1.0) / d\n+    val k = det3(a.x,a.x*a.x+a.y*a.y,1.0, b.x,b.x*b.x+b.y*b.y,1.0, c.x,c.x*c.x+c.y*c.y,1.0) / d\n+    Point(h,k)\n+  }\n+\n+  def isDelaunayEdge[T](e: HalfEdge[Int,T])(implicit trans: Int => Point): Boolean = {\n+    // Predicated on the fact that if an edge is Delaunay, then for a\n+    // point, A, to the left of edge (X,Y), and a point, B, to the\n+    // right of (X,Y), A may not be in the circle defined by points X,\n+    // Y, and B.\n+    val a = trans(e.next.vert)\n+    val b = trans(e.flip.next.vert)\n+    val x = trans(e.flip.vert)\n+    val y = trans(e.vert)\n+    !inCircle((a,x,y),b)\n+  }\n+}\n+\n+/**\n+ * A class to compute the Delaunay triangulation of a set of points.  Details can be found in\n+ * <geotrellis_home>/docs/vector/voronoi.md\n+ */\n+case class Delaunay(verts: Array[Point]) {\n+  /**\n+   * A catalog of the triangles produced by the Delaunay triangulation as a Map from (Int,Int,Int)\n+   * to HalfEdge[Int,Point].  All integers are indices of points in verts, while the Points describe\n+   * the center of the circumscribing circle for the triangle.  The Int triples give the triangle\n+   * vertices in counter-clockwise order, starting from the lowest-numbered vertex.\n+   */\n+  val triangles = Map.empty[(Int,Int,Int),HalfEdge[Int,Point]]\n+\n+  /**\n+   * A catalog of edges incident on the vertices of a Delaunay triangulation.  These half edges may\n+   * be used to navigate the faces that have a given point as a vertex.  For example, all edges\n+   * incident on vertex i may be visited by repeated application of the rotCCWDest() method of\n+   * HalfEdge on faceIncidentToVertex(i).\n+   */\n+  val faceIncidentToVertex = Map.empty[Int,HalfEdge[Int,Point]]","path":"vector/src/main/scala/geotrellis/vector/voronoi/Delaunay.scala","position":111,"original_position":111,"commit_id":"27f311a36a0ea0752afda96b7f4bb89b0065ec18","original_commit_id":"27f311a36a0ea0752afda96b7f4bb89b0065ec18","user":{"login":"lossyrob","id":2320142,"avatar_url":"https://avatars.githubusercontent.com/u/2320142?v=3","gravatar_id":"","url":"https://api.github.com/users/lossyrob","html_url":"https://github.com/lossyrob","followers_url":"https://api.github.com/users/lossyrob/followers","following_url":"https://api.github.com/users/lossyrob/following{/other_user}","gists_url":"https://api.github.com/users/lossyrob/gists{/gist_id}","starred_url":"https://api.github.com/users/lossyrob/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lossyrob/subscriptions","organizations_url":"https://api.github.com/users/lossyrob/orgs","repos_url":"https://api.github.com/users/lossyrob/repos","events_url":"https://api.github.com/users/lossyrob/events{/privacy}","received_events_url":"https://api.github.com/users/lossyrob/received_events","type":"User","site_admin":false},"body":"Shouldn't have public mutable maps (same for above)","created_at":"2016-06-19T23:01:44Z","updated_at":"2016-06-19T23:01:44Z","html_url":"https://github.com/geotrellis/geotrellis/pull/1545#discussion_r67625436","pull_request_url":"https://api.github.com/repos/geotrellis/geotrellis/pulls/1545","_links":{"self":{"href":"https://api.github.com/repos/geotrellis/geotrellis/pulls/comments/67625436"},"html":{"href":"https://github.com/geotrellis/geotrellis/pull/1545#discussion_r67625436"},"pull_request":{"href":"https://api.github.com/repos/geotrellis/geotrellis/pulls/1545"}}},"pull_request":{"url":"https://api.github.com/repos/geotrellis/geotrellis/pulls/1545","id":73586490,"html_url":"https://github.com/geotrellis/geotrellis/pull/1545","diff_url":"https://github.com/geotrellis/geotrellis/pull/1545.diff","patch_url":"https://github.com/geotrellis/geotrellis/pull/1545.patch","issue_url":"https://api.github.com/repos/geotrellis/geotrellis/issues/1545","number":1545,"state":"open","locked":false,"title":"Voronoi diagrams and Delaunay triangulations","user":{"login":"jpolchlo","id":18410961,"avatar_url":"https://avatars.githubusercontent.com/u/18410961?v=3","gravatar_id":"","url":"https://api.github.com/users/jpolchlo","html_url":"https://github.com/jpolchlo","followers_url":"https://api.github.com/users/jpolchlo/followers","following_url":"https://api.github.com/users/jpolchlo/following{/other_user}","gists_url":"https://api.github.com/users/jpolchlo/gists{/gist_id}","starred_url":"https://api.github.com/users/jpolchlo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jpolchlo/subscriptions","organizations_url":"https://api.github.com/users/jpolchlo/orgs","repos_url":"https://api.github.com/users/jpolchlo/repos","events_url":"https://api.github.com/users/jpolchlo/events{/privacy}","received_events_url":"https://api.github.com/users/jpolchlo/received_events","type":"User","site_admin":false},"body":"This PR introduces Voronoi diagrams and Delaunay triangulations to the vector package.  This includes the half-edge structure for mesh representation, and (eventually) distributed algorithms for computing Voronoi diagrams.    See the documentation provided in this PR for details.","created_at":"2016-06-13T14:38:41Z","updated_at":"2016-06-19T23:01:44Z","closed_at":null,"merged_at":null,"merge_commit_sha":"495f04b3d2344c6672924ce6ce9620713d87eff1","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/geotrellis/geotrellis/pulls/1545/commits","review_comments_url":"https://api.github.com/repos/geotrellis/geotrellis/pulls/1545/comments","review_comment_url":"https://api.github.com/repos/geotrellis/geotrellis/pulls/comments{/number}","comments_url":"https://api.github.com/repos/geotrellis/geotrellis/issues/1545/comments","statuses_url":"https://api.github.com/repos/geotrellis/geotrellis/statuses/27f311a36a0ea0752afda96b7f4bb89b0065ec18","head":{"label":"jpolchlo:feature/Voronoi","ref":"feature/Voronoi","sha":"27f311a36a0ea0752afda96b7f4bb89b0065ec18","user":{"login":"jpolchlo","id":18410961,"avatar_url":"https://avatars.githubusercontent.com/u/18410961?v=3","gravatar_id":"","url":"https://api.github.com/users/jpolchlo","html_url":"https://github.com/jpolchlo","followers_url":"https://api.github.com/users/jpolchlo/followers","following_url":"https://api.github.com/users/jpolchlo/following{/other_user}","gists_url":"https://api.github.com/users/jpolchlo/gists{/gist_id}","starred_url":"https://api.github.com/users/jpolchlo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jpolchlo/subscriptions","organizations_url":"https://api.github.com/users/jpolchlo/orgs","repos_url":"https://api.github.com/users/jpolchlo/repos","events_url":"https://api.github.com/users/jpolchlo/events{/privacy}","received_events_url":"https://api.github.com/users/jpolchlo/received_events","type":"User","site_admin":false},"repo":{"id":56542591,"name":"geotrellis","full_name":"jpolchlo/geotrellis","owner":{"login":"jpolchlo","id":18410961,"avatar_url":"https://avatars.githubusercontent.com/u/18410961?v=3","gravatar_id":"","url":"https://api.github.com/users/jpolchlo","html_url":"https://github.com/jpolchlo","followers_url":"https://api.github.com/users/jpolchlo/followers","following_url":"https://api.github.com/users/jpolchlo/following{/other_user}","gists_url":"https://api.github.com/users/jpolchlo/gists{/gist_id}","starred_url":"https://api.github.com/users/jpolchlo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jpolchlo/subscriptions","organizations_url":"https://api.github.com/users/jpolchlo/orgs","repos_url":"https://api.github.com/users/jpolchlo/repos","events_url":"https://api.github.com/users/jpolchlo/events{/privacy}","received_events_url":"https://api.github.com/users/jpolchlo/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/jpolchlo/geotrellis","description":"GeoTrellis is a geographic data processing engine for high performance applications.","fork":true,"url":"https://api.github.com/repos/jpolchlo/geotrellis","forks_url":"https://api.github.com/repos/jpolchlo/geotrellis/forks","keys_url":"https://api.github.com/repos/jpolchlo/geotrellis/keys{/key_id}","collaborators_url":"https://api.github.com/repos/jpolchlo/geotrellis/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/jpolchlo/geotrellis/teams","hooks_url":"https://api.github.com/repos/jpolchlo/geotrellis/hooks","issue_events_url":"https://api.github.com/repos/jpolchlo/geotrellis/issues/events{/number}","events_url":"https://api.github.com/repos/jpolchlo/geotrellis/events","assignees_url":"https://api.github.com/repos/jpolchlo/geotrellis/assignees{/user}","branches_url":"https://api.github.com/repos/jpolchlo/geotrellis/branches{/branch}","tags_url":"https://api.github.com/repos/jpolchlo/geotrellis/tags","blobs_url":"https://api.github.com/repos/jpolchlo/geotrellis/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/jpolchlo/geotrellis/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/jpolchlo/geotrellis/git/refs{/sha}","trees_url":"https://api.github.com/repos/jpolchlo/geotrellis/git/trees{/sha}","statuses_url":"https://api.github.com/repos/jpolchlo/geotrellis/statuses/{sha}","languages_url":"https://api.github.com/repos/jpolchlo/geotrellis/languages","stargazers_url":"https://api.github.com/repos/jpolchlo/geotrellis/stargazers","contributors_url":"https://api.github.com/repos/jpolchlo/geotrellis/contributors","subscribers_url":"https://api.github.com/repos/jpolchlo/geotrellis/subscribers","subscription_url":"https://api.github.com/repos/jpolchlo/geotrellis/subscription","commits_url":"https://api.github.com/repos/jpolchlo/geotrellis/commits{/sha}","git_commits_url":"https://api.github.com/repos/jpolchlo/geotrellis/git/commits{/sha}","comments_url":"https://api.github.com/repos/jpolchlo/geotrellis/comments{/number}","issue_comment_url":"https://api.github.com/repos/jpolchlo/geotrellis/issues/comments{/number}","contents_url":"https://api.github.com/repos/jpolchlo/geotrellis/contents/{+path}","compare_url":"https://api.github.com/repos/jpolchlo/geotrellis/compare/{base}...{head}","merges_url":"https://api.github.com/repos/jpolchlo/geotrellis/merges","archive_url":"https://api.github.com/repos/jpolchlo/geotrellis/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/jpolchlo/geotrellis/downloads","issues_url":"https://api.github.com/repos/jpolchlo/geotrellis/issues{/number}","pulls_url":"https://api.github.com/repos/jpolchlo/geotrellis/pulls{/number}","milestones_url":"https://api.github.com/repos/jpolchlo/geotrellis/milestones{/number}","notifications_url":"https://api.github.com/repos/jpolchlo/geotrellis/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/jpolchlo/geotrellis/labels{/name}","releases_url":"https://api.github.com/repos/jpolchlo/geotrellis/releases{/id}","deployments_url":"https://api.github.com/repos/jpolchlo/geotrellis/deployments","created_at":"2016-04-18T21:13:17Z","updated_at":"2016-04-18T21:13:30Z","pushed_at":"2016-06-17T19:42:31Z","git_url":"git://github.com/jpolchlo/geotrellis.git","ssh_url":"git@github.com:jpolchlo/geotrellis.git","clone_url":"https://github.com/jpolchlo/geotrellis.git","svn_url":"https://github.com/jpolchlo/geotrellis","homepage":"http://geotrellis.io","size":267907,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"geotrellis:master","ref":"master","sha":"8c0d614fe1e97065dddd75db0065d13195a1e1f1","user":{"login":"geotrellis","id":3129444,"avatar_url":"https://avatars.githubusercontent.com/u/3129444?v=3","gravatar_id":"","url":"https://api.github.com/users/geotrellis","html_url":"https://github.com/geotrellis","followers_url":"https://api.github.com/users/geotrellis/followers","following_url":"https://api.github.com/users/geotrellis/following{/other_user}","gists_url":"https://api.github.com/users/geotrellis/gists{/gist_id}","starred_url":"https://api.github.com/users/geotrellis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/geotrellis/subscriptions","organizations_url":"https://api.github.com/users/geotrellis/orgs","repos_url":"https://api.github.com/users/geotrellis/repos","events_url":"https://api.github.com/users/geotrellis/events{/privacy}","received_events_url":"https://api.github.com/users/geotrellis/received_events","type":"Organization","site_admin":false},"repo":{"id":3040675,"name":"geotrellis","full_name":"geotrellis/geotrellis","owner":{"login":"geotrellis","id":3129444,"avatar_url":"https://avatars.githubusercontent.com/u/3129444?v=3","gravatar_id":"","url":"https://api.github.com/users/geotrellis","html_url":"https://github.com/geotrellis","followers_url":"https://api.github.com/users/geotrellis/followers","following_url":"https://api.github.com/users/geotrellis/following{/other_user}","gists_url":"https://api.github.com/users/geotrellis/gists{/gist_id}","starred_url":"https://api.github.com/users/geotrellis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/geotrellis/subscriptions","organizations_url":"https://api.github.com/users/geotrellis/orgs","repos_url":"https://api.github.com/users/geotrellis/repos","events_url":"https://api.github.com/users/geotrellis/events{/privacy}","received_events_url":"https://api.github.com/users/geotrellis/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/geotrellis/geotrellis","description":"GeoTrellis is a geographic data processing engine for high performance applications.","fork":false,"url":"https://api.github.com/repos/geotrellis/geotrellis","forks_url":"https://api.github.com/repos/geotrellis/geotrellis/forks","keys_url":"https://api.github.com/repos/geotrellis/geotrellis/keys{/key_id}","collaborators_url":"https://api.github.com/repos/geotrellis/geotrellis/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/geotrellis/geotrellis/teams","hooks_url":"https://api.github.com/repos/geotrellis/geotrellis/hooks","issue_events_url":"https://api.github.com/repos/geotrellis/geotrellis/issues/events{/number}","events_url":"https://api.github.com/repos/geotrellis/geotrellis/events","assignees_url":"https://api.github.com/repos/geotrellis/geotrellis/assignees{/user}","branches_url":"https://api.github.com/repos/geotrellis/geotrellis/branches{/branch}","tags_url":"https://api.github.com/repos/geotrellis/geotrellis/tags","blobs_url":"https://api.github.com/repos/geotrellis/geotrellis/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/geotrellis/geotrellis/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/geotrellis/geotrellis/git/refs{/sha}","trees_url":"https://api.github.com/repos/geotrellis/geotrellis/git/trees{/sha}","statuses_url":"https://api.github.com/repos/geotrellis/geotrellis/statuses/{sha}","languages_url":"https://api.github.com/repos/geotrellis/geotrellis/languages","stargazers_url":"https://api.github.com/repos/geotrellis/geotrellis/stargazers","contributors_url":"https://api.github.com/repos/geotrellis/geotrellis/contributors","subscribers_url":"https://api.github.com/repos/geotrellis/geotrellis/subscribers","subscription_url":"https://api.github.com/repos/geotrellis/geotrellis/subscription","commits_url":"https://api.github.com/repos/geotrellis/geotrellis/commits{/sha}","git_commits_url":"https://api.github.com/repos/geotrellis/geotrellis/git/commits{/sha}","comments_url":"https://api.github.com/repos/geotrellis/geotrellis/comments{/number}","issue_comment_url":"https://api.github.com/repos/geotrellis/geotrellis/issues/comments{/number}","contents_url":"https://api.github.com/repos/geotrellis/geotrellis/contents/{+path}","compare_url":"https://api.github.com/repos/geotrellis/geotrellis/compare/{base}...{head}","merges_url":"https://api.github.com/repos/geotrellis/geotrellis/merges","archive_url":"https://api.github.com/repos/geotrellis/geotrellis/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/geotrellis/geotrellis/downloads","issues_url":"https://api.github.com/repos/geotrellis/geotrellis/issues{/number}","pulls_url":"https://api.github.com/repos/geotrellis/geotrellis/pulls{/number}","milestones_url":"https://api.github.com/repos/geotrellis/geotrellis/milestones{/number}","notifications_url":"https://api.github.com/repos/geotrellis/geotrellis/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/geotrellis/geotrellis/labels{/name}","releases_url":"https://api.github.com/repos/geotrellis/geotrellis/releases{/id}","deployments_url":"https://api.github.com/repos/geotrellis/geotrellis/deployments","created_at":"2011-12-23T14:56:54Z","updated_at":"2016-06-16T07:54:12Z","pushed_at":"2016-06-19T22:52:46Z","git_url":"git://github.com/geotrellis/geotrellis.git","ssh_url":"git@github.com:geotrellis/geotrellis.git","clone_url":"https://github.com/geotrellis/geotrellis.git","svn_url":"https://github.com/geotrellis/geotrellis","homepage":"http://geotrellis.io","size":283970,"stargazers_count":439,"watchers_count":439,"language":"Scala","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":128,"mirror_url":null,"open_issues_count":78,"forks":128,"open_issues":78,"watchers":439,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/geotrellis/geotrellis/pulls/1545"},"html":{"href":"https://github.com/geotrellis/geotrellis/pull/1545"},"issue":{"href":"https://api.github.com/repos/geotrellis/geotrellis/issues/1545"},"comments":{"href":"https://api.github.com/repos/geotrellis/geotrellis/issues/1545/comments"},"review_comments":{"href":"https://api.github.com/repos/geotrellis/geotrellis/pulls/1545/comments"},"review_comment":{"href":"https://api.github.com/repos/geotrellis/geotrellis/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/geotrellis/geotrellis/pulls/1545/commits"},"statuses":{"href":"https://api.github.com/repos/geotrellis/geotrellis/statuses/27f311a36a0ea0752afda96b7f4bb89b0065ec18"}}}}
{"actor":{"display_login":"lossyrob"}}