It looks like you're new here. If you want to get involved, click one of these buttons!

- 141K All Categories
- 103.8K Programming Languages
- 6.5K Assembler Developer
- 1.9K Basic
- 40K C and C++
- 2.9K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.7K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 551 Python
- 37 Ruby
- 4.4K VB.NET
- 1.6K VBA
- 20.9K Visual Basic
- 2.6K Game programming
- 317 Console programming
- 92 DirectX Game dev
- 1 Minecraft
- 112 Newbie Game Programmers
- 2 Oculus Rift
- 9K Applications
- 1.8K Computer Graphics
- 744 Computer Hardware
- 3.5K Database & SQL
- 535 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 258 XML Development
- 3.3K Classifieds
- 199 Co-operative Projects
- 198 For sale
- 190 FreeLance Software City
- 1.9K Jobs Available
- 604 Jobs Wanted
- 210 Wanted
- 2.9K Microsoft .NET
- 1.8K ASP.NET
- 1.1K .NET General
- 3.4K Miscellaneous
- 7 Join the Team
- 355 Comments on this site
- 70 Computer Emulators
- 2.1K General programming
- 187 New programming languages
- 628 Off topic board
- 217 Mobile & Wireless
- 89 Android
- 126 Palm Pilot
- 340 Multimedia
- 156 Demo programming
- 184 MP3 programming
- Bash scripts
- 27 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 370 MS-DOS
- Shell scripting
- 321 Windows CE & Pocket PC
- 4.1K Windows programming
- 942 Software Development
- 417 Algorithms
- 68 Object Orientation
- 92 Project Management
- 95 Quality & Testing
- 269 Security
- 7.7K WEB-Development
- 1.8K Active Server Pages
- 62 AJAX
- 5 Bootstrap Themes
- 55 CGI Development
- 28 ColdFusion
- 224 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 37 JQuery
- 308 WEB Servers
- 151 WEB-Services / SOAP

schmiley397
Member Posts: **3**

in Algorithms

hi,

does anyone out there happen to know how one would go by building a voronoi diagram on a sphere? The "sites" of the diagram are on the unit sphere. Some effort has been put into the problem, and I have actually three ideas on how to proceed :

1/ With Fortune's algorithm

I tried to transpose Fortune's line-sweep algorithm to the surface of a sphere, but I got stuck on a mathematical problem, some formula that is supposed to define the surface that separates space in two, all points of space closer to a given point on the sphere on one side, and all points closer to circle on the sphere (not a great circle, just any circle - an intersection between the sphere and a plane). It looks like this :

Ax + By + Cz + Dsqrt(1-y^2) = 0

To implement the algorithm, I need to determine an intersection between two such things and I really don't know how to manipulate them (the sqrt(1-y^2) term being the problem).

2/ Using a Delaunay triangulation instead

It seems that it would be easier to implement on a sphere since the math is more intuitive, at least in the incremental algorithms I've seen. But even though the algorithm would be of the same average complexity as Fortune's algorithm - O(n log(n)) - it seems it would be a lot slower given all the intersection tests required.

3/ Using Fortune's algorithm, but this time on a 2D stereographic projection of the sphere

I think the idea is cool but I need some proof that it would give the same output. The stereographic projection doesn't preserve distances which is kind of a central theme in Voronoi diagrams. On the other hand, I get the feeling that it should work on a Delauney triangulation, and if it works for one, it works for the other... I just lack the math "intuition" to prove one way or the other.

Well, I hope someone can help me out, and I hope this is posted in the right place.

cheers

does anyone out there happen to know how one would go by building a voronoi diagram on a sphere? The "sites" of the diagram are on the unit sphere. Some effort has been put into the problem, and I have actually three ideas on how to proceed :

1/ With Fortune's algorithm

I tried to transpose Fortune's line-sweep algorithm to the surface of a sphere, but I got stuck on a mathematical problem, some formula that is supposed to define the surface that separates space in two, all points of space closer to a given point on the sphere on one side, and all points closer to circle on the sphere (not a great circle, just any circle - an intersection between the sphere and a plane). It looks like this :

Ax + By + Cz + Dsqrt(1-y^2) = 0

To implement the algorithm, I need to determine an intersection between two such things and I really don't know how to manipulate them (the sqrt(1-y^2) term being the problem).

2/ Using a Delaunay triangulation instead

It seems that it would be easier to implement on a sphere since the math is more intuitive, at least in the incremental algorithms I've seen. But even though the algorithm would be of the same average complexity as Fortune's algorithm - O(n log(n)) - it seems it would be a lot slower given all the intersection tests required.

3/ Using Fortune's algorithm, but this time on a 2D stereographic projection of the sphere

I think the idea is cool but I need some proof that it would give the same output. The stereographic projection doesn't preserve distances which is kind of a central theme in Voronoi diagrams. On the other hand, I get the feeling that it should work on a Delauney triangulation, and if it works for one, it works for the other... I just lack the math "intuition" to prove one way or the other.

Well, I hope someone can help me out, and I hope this is posted in the right place.

cheers

Terms of use / Privacy statement / Publisher: Lars Hagelin

Programmers Heaven articles / Programmers Heaven files / Programmers Heaven uploaded content / Programmers Heaven C Sharp ebook / Operated by CommunityHeaven

© 1997-2017 Programmersheaven.com - All rights reserved.