Hello all, I am a biology major that is beginning to work with Java to develop tools for my lab. My question is this: Is there an established way to deal with volumes in Java? Not regular volumes, but irregular. I have a series of X, Y, and Z coordinates to work with and I was wondering if anyone knew the best/fastest way to go about this. My knowledge is limited to the few books we have around our lab and the considerable amount of time I've spent surfing the web. Any responses will be appreciated.

# 3D Volumetrics

Page 1 of 1## 11 Replies - 1082 Views - Last Post: 11 January 2013 - 01:20 AM

##
**Replies To:** 3D Volumetrics

### #2

## Re: 3D Volumetrics

Posted 28 December 2012 - 04:48 PM

### #3

## Re: 3D Volumetrics

Posted 28 December 2012 - 05:02 PM

Yes, very much like this, but that is much much more more complex than I understand. I will give it a looksee and see what I can come up with. I appreciate the quick reply greatly.

After looking at this, I realized that it is more complex than I am needing. I am looking for a simple calculator, and I really do not need the visual aspect of it. I would simply like to put in a series of coordinates and obtain a volume. Perhaps examining this will help me along.

After looking at this, I realized that it is more complex than I am needing. I am looking for a simple calculator, and I really do not need the visual aspect of it. I would simply like to put in a series of coordinates and obtain a volume. Perhaps examining this will help me along.

### #4

## Re: 3D Volumetrics

Posted 28 December 2012 - 06:22 PM

What you are asking isn't quite a simple thing.. at best you may just write some advanced calc equations in and run with that.. but no, there is nothing 'out of the box' that you can tap into immediately on the greenhorn level.

### #5

## Re: 3D Volumetrics

Posted 28 December 2012 - 08:40 PM

x,y,z...

Are you looking to find the volume under a plane?

http://www.math24.ne...-integrals.html

Are you looking to find the volume under a plane?

http://www.math24.ne...-integrals.html

This post has been edited by **BlueMelon**: 28 December 2012 - 08:42 PM

### #6

## Re: 3D Volumetrics

Posted 29 December 2012 - 07:50 AM

Here is an algorithm that you should be able to implement. I'm going to explain it conceptually rather than give you the code. The idea is really quite simple and will work in 1D, 2D, 3D, etc...

You can make the algorithm simpler by starting with the queue and adding the first box to it. The tricky part is working out if a box is inside/outside or partially inside your data set. I'll leave that to you just now. Come back if you are stuck!

Quote

1. Define a cuboid (in 3D) that encloses your entire data set. It doesn't matter if it is too big initially, the algorithm will cope. It's trivial to calculate the area of a cuboid so this is going to be the initial estimate of your volume. Obviously, it's going to be an overestimate.

2. Divide your box into smaller boxes. If you are working in 2D, cut it along the x and y axes giving 4 smaller boxes. If you are in 3D then cut along the z axis too giving 8 smaller boxes.

3. Take each box in turn. A box will fall into one of three categories:

3A. It lies entirely outside your data set. Subtract its volume from your initial estimate and discard the box. You don't need it any more.

3B. It lies entirely inside your data set. Discard the box so you don't keep dividing it but do not adjust your initial estimate.

3C. Part of the box lies inside your data set and part lies outside. Add the box to a list that need to be further divided. Don't adjust the estimated volume yet.

4. Run through the list of boxes that need to be divided (a queue is a nice data structure for this) until the estimated volume is within an acceptable error distance of the actual value. How do you know this? It's when the total volumes of the boxes in the queue is less than the error value. (This sounds imprecise but you can make the error value as small as you wish)

2. Divide your box into smaller boxes. If you are working in 2D, cut it along the x and y axes giving 4 smaller boxes. If you are in 3D then cut along the z axis too giving 8 smaller boxes.

3. Take each box in turn. A box will fall into one of three categories:

3A. It lies entirely outside your data set. Subtract its volume from your initial estimate and discard the box. You don't need it any more.

3B. It lies entirely inside your data set. Discard the box so you don't keep dividing it but do not adjust your initial estimate.

3C. Part of the box lies inside your data set and part lies outside. Add the box to a list that need to be further divided. Don't adjust the estimated volume yet.

4. Run through the list of boxes that need to be divided (a queue is a nice data structure for this) until the estimated volume is within an acceptable error distance of the actual value. How do you know this? It's when the total volumes of the boxes in the queue is less than the error value. (This sounds imprecise but you can make the error value as small as you wish)

You can make the algorithm simpler by starting with the queue and adding the first box to it. The tricky part is working out if a box is inside/outside or partially inside your data set. I'll leave that to you just now. Come back if you are stuck!

### #7

## Re: 3D Volumetrics

Posted 29 December 2012 - 08:02 AM

Just out of interest, what do sort of biology do you do?

### #8

## Re: 3D Volumetrics

Posted 29 December 2012 - 08:15 AM

You can also do a

(If the number of sub-division -> infinity, it should give the integral)

*Riemann sum*for an approximation.(If the number of sub-division -> infinity, it should give the integral)

### #9

## Re: 3D Volumetrics

Posted 29 December 2012 - 04:18 PM

Sorry I'm so slow replying. I do structural biology, mostly protein-protein interactions. I am still working under another graduate student on their project. I appreciate all of these replies and I will mark them as helpful!

### #10

## Re: 3D Volumetrics

Posted 30 December 2012 - 09:17 AM

Riemann sum is also a good suggestion. The trick if your shape is concave to split it into convex sections.

Thinking about it, another option is triangulation. You pick any four points to start with. They make a pyramid shape, the volume of which you can calculate easily. You then loop over each of the remaining points in turn. With each, you find the three closest points that have already been used, create a pyramid and add the volume to the running total. One thing to watch out for is points being inside existing pyramids. You want to ignore those points or you will end up counting sections of the area twice. Like Riemann sums, you will also have to split your shape into convex sections.

Thinking about it, another option is triangulation. You pick any four points to start with. They make a pyramid shape, the volume of which you can calculate easily. You then loop over each of the remaining points in turn. With each, you find the three closest points that have already been used, create a pyramid and add the volume to the running total. One thing to watch out for is points being inside existing pyramids. You want to ignore those points or you will end up counting sections of the area twice. Like Riemann sums, you will also have to split your shape into convex sections.

### #11

## Re: 3D Volumetrics

Posted 08 January 2013 - 03:35 PM

Along the lines of cfoleys conceptual algorithm, can someone please suggest some classes that I should look at? I considered Point3d, but for some reason it doesn't cross platforms to our labs linux machines easily as discovered by a labmate of mine. The making of a box/plotting my points inside of it and then determining whether or not they overlap is a little over my head as of now and I would like somewhere to begin. any suggestions are helpful.

### #12

## Re: 3D Volumetrics

Posted 11 January 2013 - 01:20 AM

Hi,

Sorry, I saw the post you made in your thread but this week has been crazy with deadlines for me. A Point3D class is pretty simple to make. All you need is a constructor that takes x, y and z and three getters along the lines of:

A toString() might be useful for debugging too.

The cube is slightly more involved but the key method is:

It should obviously return true if the point lies inside the box, false otherwise.

Another key method would be one that splits it into smaller boxes. Something like this (although you could use an array instead of a list)

I've not talked about the internal representation of the box because there are a lot of options, all of which are fine. A reasonable one would be storing a Point3D for the (minX, minY, minZ) (let's call it origin) and a double for the length of a side (called length). This is the minimum needed to define a cube. You'll need more to fill in the gaps in the methods above but that should be done through methods like these (notice that they are all private):

Your containsY() and containsZ() methods will look very similar! Could that be an opportunity to eliminate duplicate code?

This should be enough for you to make a good start. The tricky part is when you have boxes that contain no points. The computer has to decide if the box is inside or outside the model. See if you can find a solution and come back for help if you need it.

I'm going to post this on your thread. It's the best place for discussions since this post might help someone else in the future and it gives others a chance to chip in with something I haven't thought of.

Sorry, I saw the post you made in your thread but this week has been crazy with deadlines for me. A Point3D class is pretty simple to make. All you need is a constructor that takes x, y and z and three getters along the lines of:

public double getX() { return x; }

A toString() might be useful for debugging too.

The cube is slightly more involved but the key method is:

public boolean contains(Point3D p) { // your code here }

It should obviously return true if the point lies inside the box, false otherwise.

Another key method would be one that splits it into smaller boxes. Something like this (although you could use an array instead of a list)

public List<Cube> split() { List<Cube> result = new ArrayList<>(); // Your code here return result; }

I've not talked about the internal representation of the box because there are a lot of options, all of which are fine. A reasonable one would be storing a Point3D for the (minX, minY, minZ) (let's call it origin) and a double for the length of a side (called length). This is the minimum needed to define a cube. You'll need more to fill in the gaps in the methods above but that should be done through methods like these (notice that they are all private):

private boolean containsX(Point3D p) { double x = p.getX(); return (x >= minX()) && (x < maxX()); } private double minX() { return origin.getX(); } private double maxX() { return minX() + length; }

Your containsY() and containsZ() methods will look very similar! Could that be an opportunity to eliminate duplicate code?

This should be enough for you to make a good start. The tricky part is when you have boxes that contain no points. The computer has to decide if the box is inside or outside the model. See if you can find a solution and come back for help if you need it.

I'm going to post this on your thread. It's the best place for discussions since this post might help someone else in the future and it gives others a chance to chip in with something I haven't thought of.

Page 1 of 1