15,306,445 members
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

Posted

## Solution 2

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
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

## Solution 1

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.

http://freespace.virgin.net/hugo.elias/routines/r_dist.htm[^]

Hope it helps.
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)

Top Experts
Last 24hrsThis month
 Richard MacCutchan 135 OriginalGriff 70 Dave Kreskowiak 60 Greg Utas 45 Richard Deeming 40
 OriginalGriff 3,746 Richard MacCutchan 1,410 CPallini 1,015 Richard Deeming 773 Patrice T 705

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