Click here to Skip to main content
15,306,585 members
Please Sign up or sign in to vote.
5.00/5 (1 vote)
See more:
Hi all

Please give some good idea or piece of code to detect Adjacent Nodes in 3D Space usig C++.
For Example, enter radius , SW should identify the nodes which are with the specfici sphere.

//Input : a 3D Space with Lots of Nodes

Thanks in Advanced
Posted

Simple solution:
- calculate and store the square of the radius
- loop over all nodes
- for each node, calculate the square of the distance between the node and the center of the sphere
- compare the result to the square radius - if it's greater, then the point is outside the sphere, else inside

More complex solution:
- organize your 3D points in a geomatrical data structure, e. g. an Octree[^]
- determine which of the segments of this data structures contain part or all of the sphere
- for all those specific segments, do the simple solution search described above.

P.S.:
If performance is not an issue, you can also do the very simple solution (as suggested above):
- loop over all nodes
- for each node, calculate the distance between the node and the center of the sphere
- compare the result to the radius - if it's greater, then the point is outside the sphere, else inside

I consider that 'very' simple, but at the same time possibly better than either of the above, because it explicitely does the obvious thing. Anyone with a minimum of knowledge about geometry looking at the code will immediately understand it. This may make it more maintainable than the other solutions.
   
v2
Comments
Amir Mahfoozi 13-Dec-11 6:04am
   
+5'ed :)
tssutha03 13-Dec-11 10:06am
   
Thanks for the response, I will start from your suggestion and lets see the outcome of my app.
Thanks
If you have the reference point coordinate and other points coordinates, why don't you compute the distance between them and compare it with the radius of that sphere ? If the distance was lower than the sphere radius then its in the sphere.

to avoid computing square roots read this page :
http://freespace.virgin.net/hugo.elias/routines/r_dist.htm[^]

Hope it helps.
   
Comments
Stefan_Lang 13-Dec-11 5:35am
   
Nice link, and also my preferred way of doing it. However, I find the statement 'avoid square roots like the plague' to be overly dramatic. For one, modern processors can calculate these quite efficiently, using lookup tables. And second, whether or not you actually need to take care of performance depends on the application! You shouldn't look at performance considerations until you (a) have a running application, (b) the performance is too bad for your purposes, and (c) you've pinpointed the actual bottleneck(s). Any effort put into performance before (a), (b) or (c) are usually wasted.

P.S.: being a mathematician I don't conider comparing squares rather than square roots a wasted effort, it just comes naturally to me. I just wanted to make a point that, generally speaking, this shouldn't be a concern.
Amir Mahfoozi 13-Dec-11 6:03am
   
I agree with you, but there are some situations in realtime application development or game development that you can not consume CPU time very much and there is noway to distribute your computation between some threads, and additionally you should for example detect collision between an object and multiple other objects. In those cases you have to consider these issues. In ordinary applications as you said we can ignore these bottlenecks and do whatever we want.
tssutha03 13-Dec-11 10:05am
   
Thanks for the response, I will start from your suggestion and lets see the outcome of my app.
Thanks

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900