Ticket #627 (assigned enhancement)

Opened 13 months ago

Last modified 7 months ago

Voronoi

Reported by: smathermather Owned by: strk
Priority: major Milestone: 3.5.0
Component: Default Version: svn-trunk
Severity: Unassigned Keywords:
Cc: hi.vishal123@…

Description

Port voronoi from JTS. Would be really nice to add ST_Voronoi to PostGIS

Possibly remove dependency of cgal for pgRouting

Allow for any number of skeletonization solutions

Thus allowing for non-polygon outputs from Raster, like an ST_PixelAsLinestring

start the process toward world peace

Change History

  Changed 13 months ago by woodbri

If/When? this is done, I'm willing to rework the pgRouting code to use it and get rid of CGAL. Ideally, we would like to care along a Z value with each point so we can generate a 3D triangulated surface and be able to then intersect that with planes in Z to generate contours.

Thanks!

  Changed 13 months ago by mdavis

Given #487 this shouldn't be too hard to do.

  Changed 13 months ago by strk

This ticket is to:

  1. Port the Voronoi classes from JTS to GEOS
  2. Write C++ testcases (port or write from scratch)
  3. Expose the function trough the C-API of GEOS
  4. Write C testcases

  Changed 13 months ago by robe

Just as an FYI - we discussed in sprint and Bborie mentioned this might be a good Google Summer of Code project since it just requires someone with C++/Java skills to port and not too much hand holding as to explanations. So probably not much mentoring involved.

  Changed 10 months ago by robe

  • milestone changed from GEOS Future to 3.5.0

  Changed 10 months ago by robe

this is currently being worked on by vishal tiwari (GSOC 2013)

 https://github.com/vishaltiwari/GSoC-GEOS

Proposal details and project plan:  https://google-melange.appspot.com/gsoc/proposal/review/google/gsoc2013/vishal_tiwari/13001

progress reports:  http://trac.osgeo.org/geos/wiki/GSoC

  Changed 7 months ago by strk

  • cc hi.vishal123@… added
  • owner changed from geos-devel@… to strk
  • status changed from new to assigned

Commits so far: r3849 r3862 r3899 r3912 r3944 r3951

  Changed 7 months ago by strk

  • version changed from 3.3.8 to svn-trunk

  Changed 7 months ago by strk

With r3953 Voronoi is also accessible via C-API. Next stop: PHP api

  Changed 7 months ago by strk

r3954 renames the C-API signature to GEOSVoronoiDiagram (from GEOSVoronoiDiagramBuilder).

  Changed 7 months ago by strk

Should we have an "only edges" parameter too ? It would match with the GEOSDelaunayTriangles interface

follow-up: ↓ 13   Changed 7 months ago by strk

Vishal: would you be interested in adding the "only edges" parameter ? It should be as simpl as calling getSubdivision()->getEdges(someGeomFactory) on the VoronoiDiagramBuilder? object. The rest would be writing the testcase :)

Once that's in place I'll do the PHP part

in reply to: ↑ 12   Changed 7 months ago by vishaltiwari

Replying to strk:

Vishal: would you be interested in adding the "only edges" parameter ? It should be as simpl as calling getSubdivision()->getEdges(someGeomFactory) on the VoronoiDiagramBuilder? object. The rest would be writing the testcase :) Once that's in place I'll do the PHP part

Sure! I will add the "only edges" parameter and the corresponding test cases. :)

  Changed 7 months ago by vishaltiwari

Added "onlyEdges" parameter. The commit can be found here:

 https://github.com/vishaltiwari/libgeos/commit/fade372f6cc21d3bc337e6cf917a358c3ec5eb87

  Changed 7 months ago by strk

Oops, you missed the change in function name (I removed the "Builder" part). Could you rebase to trunk please ? Also, git diff showed a difference in indentation between existing code and new code, could you also fix that ? Thank you !

  Changed 7 months ago by vishaltiwari

It was a big blunder. So I made a new branch:

 https://github.com/vishaltiwari/libgeos/compare/Voronoi_corrections

It should rebase now. Also fixed the indentation issue. Thanks

  Changed 7 months ago by strk

Great! r3959 ready for PHP (up for more fun? or I'll do it next week ;)

  Changed 7 months ago by vishaltiwari

I am not that much familiar with PHP, so i suggest you do it. :)

Note: See TracTickets for help on using tickets.