Ticket #627 (closed enhancement: fixed)

Opened 17 months ago

Last modified 3 months ago

Voronoi

Reported by: smathermather Owned by: strk
Priority: blocker Milestone: 3.5.0
Component: Default Version: svn-trunk
Severity: Unassigned Keywords: history
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 17 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 17 months ago by mdavis

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

  Changed 17 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 17 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 14 months ago by robe

  • milestone changed from GEOS Future to 3.5.0

  Changed 14 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 12 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 12 months ago by strk

  • version changed from 3.3.8 to svn-trunk

  Changed 12 months ago by strk

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

  Changed 12 months ago by strk

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

  Changed 12 months ago by strk

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

follow-up: ↓ 13   Changed 12 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 12 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 12 months ago by vishaltiwari

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

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

  Changed 12 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 12 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 12 months ago by strk

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

  Changed 12 months ago by vishaltiwari

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

  Changed 3 months ago by strk

Vishal, are you still around ? I just realized that the output for "edge only" Voronoi looks weird

  Changed 3 months ago by strk

  • priority changed from major to blocker

By passing an 'onlyEdges' flag the function returns edges of the delaunay triangulation rather than of the voronoi diagram. I saw there's no support for returning voronoi diagram as linestrings in JTS but seems straightfoward to add.

Martin, any reason why getting the diagram as edges is missing ?

Also, I think it would it make sense for the voronoi diagram functions to take a mandatory clipping extent.

  Changed 3 months ago by strk

With r3983 I've exposed methods in the VoronoiDiagramBuilder? to extract the edges of the voronoi diagram cells, as a MULTILINESTRING. That's what we get now when specifying "edgesOnly" parameter.

Commit r3984 exposes it all to the PHP APIs.

Still missing: accepting a clipping envelope. This is better accounted for now, or it'll take an additional C-API signature later... Would be nice if Vishal was still around to do this part :)

  Changed 3 months ago by strk

  • keywords history added
  • status changed from assigned to closed
  • resolution set to fixed

Envelope clipping accepted with r3985 -- consider this completed.

  Changed 3 months ago by vishaltiwari

Just saw the mail and the changes u made in the C-api and VoronoiDiagramBuilder?. Looks like you have taken care of it. :) Let me know if something comes up.

  Changed 3 months ago by strk

Hey, glad to see you're still following.

Yep, nothing more to do here, but if you're up for some more fun it would be lovely to see more triangulation classes ported (for constrained triangulation)

Note: See TracTickets for help on using tickets.