CODEWITHSUNDEEP
algorithmsorting
Yuchen
Yuchen

Reputation: 33056

Compute the Cross Section of a Cube

As is indicated in the following images, the cross section of a cube can be:

  1. Triangle
  2. Rectangle
  3. Pentagon (NOT DREW)
  4. Hexagon

Assume that we are getting a hexagon. We can get the intersection points of the cross plane with each side of the cube and get the hexagon ABCDEF. The question is: how do we sort the intersection points so that the hexagon ABCDEF can be divided into 4 triangles ABC, ACD, ADE and AEF.

enter image description here

Notice that the order of the points is very important because if I get the order wrong, I won't be able to draw it out. I want to divide them into triangles because I want to visualized them in OpenGL.

Thanks so much for @HugoRune's answer. Here some result that I want to share with you guys. Left image is the cross section of a 3D volume (from an arbitrary angle). Right image is the result of maximum intensity projection of the 3D volume. Cross Section of A Box (Real Data)

Upvotes: 11

Views: 3716

Answers (2)

HugoRune
HugoRune

Reputation: 13809

the intersection is a convex polygon, so any sorting that works for convex polygons will work here as well.

In particular:

  • calculate the centroid Z = (A+B+C+...) / numPoints
  • calculate the normal n = AB cross BC
  • get the Vector from the centroid to the first point: ZA
  • order all points P by the signed angle ZA to ZP with normal n
    (signed angle == angle(ZA,ZP) * sign (n dot (ZA cross ZP) )

Upvotes: 7

fuesika
fuesika

Reputation: 3330

Without loss of generality, I assume that the edges of the cube are aligned along cartesian axes (if this is not the case, the algorithm can be adjusted to use the respective main axes).

You can then exploit the special property of two adjacent points: they have one (and only one) coordinate in common, e.g. A and B both lie in the upper plane that bounds the cube (say, same z), B and C share another common plane, D and E share the same z but it is different from the value that A and B have in common. Using this information helps you to sort the points.

As far as I can see, the described procedure should apply to all cases of intersections. There is always an edge within a plane of the cube's sides which connects two points on the edges of the cube.

Upvotes: 1

Related Questions