Detect Adjacent Nodes in 3D Space

Question

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 12-Dec-11 16:55pm

tssutha03

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Stefan_Lang · Answer 1 · 2011-12-12T23:05:00

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.

Amir Mahfoozi · Answer 2 · 2011-12-12T19:01:00

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.

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

Hope it helps.

Posted 12-Dec-11 19:01pm

Amir Mahfoozi

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