Sort a set of 3-D points in clockwise/counter-clockwise order

algorithmgeometrymeshsorting

In 3-D space I have an unordered set of, say, 6 points; something like this:

           (A)*
                          (C)*
(E)*
                         (F)*
     (B)*

                  (D)*

The points form a 3-D contour but they are unordered. For unordered I mean that they are stored in an

unorderedList = [A - B - C - D - E - F]

I just want to reorganize this list starting from an arbitrary location (let's say point A) and traversing the points clockwise or counter-clockwise. Something like this:

orderedList = [A - E - B - D - F - C]

orderedList = [A - C - F - D - B - E]

I'm trying to implement an algorithm as simple as possible, since the set of points in mention corresponds to a N-ring neighborhood of each vertex on a mesh of ~420000 points, and I have to do this for each point on the mesh.

Some time ago there was a similar discussion regarding points in 2-D, but for now it's not clear for me how to go from this approach to my 3-D scenario.

Best Answer

The notion of "clockwise" or "counterclockwise" is not well-defined without an axis and orientation! (proof: What if you looked at those points from the other side of your monitor screen, or flipped them, for example!)

You must define an axis and orientation, and specify it as an additional input. Ways to specify it include:

a line (1x=2y=3z), using the right-hand rule
a (unit) vector (A_x, A_y, A_z), using the right-hand rule; this is the preferred way to do so

In order to determine the orientation, you have to look deeper at your problem: You must define a "up" and "down" size of the mesh. Then for each set of points, you must take the centroid (or another "inside" point) and construct a unit vector pointing "up" which is normal to the surface. (One way to do this would be to find the least-squares-fit plane, then find the two perpendicular vectors through that point, picking the one in the "up" direction.)

You will need to use any of the above suggestions to determine your axis. This will allow you to reformulate your problem as follows:

Inputs:

the set of points {P_i}
an axis, which we shall call "the z-axis" and treat as a unit vector centered on the centroid (or somewhere "inside") of the points
an orientation (e.g. counterclockwise) chosen by one of the above methods

Setup:

For all points, pick two mutually-orthogonal unit vectors to the axis, which we shall call "the y-axis" and "the x-axis". (Just rotate the z-axis unit-vector 90 degrees in two directions, http://en.wikipedia.org/wiki/Rotation_matrix#Basic_rotations )

Algorithm:

For each point P, project P onto the x-axis and y-axis (using the dot product), then use http://en.wikipedia.org/wiki/Atan2

Once you have the angles, you can just sort them.

Related Solutions

Python – How to sort a list of dictionaries by a value of the dictionary

The sorted() function takes a key= parameter

newlist = sorted(list_to_be_sorted, key=lambda d: d['name'])

Alternatively, you can use operator.itemgetter instead of defining the function yourself

from operator import itemgetter
newlist = sorted(list_to_be_sorted, key=itemgetter('name'))

For completeness, add reverse=True to sort in descending order

newlist = sorted(list_to_be_sorted, key=itemgetter('name'), reverse=True)

Java – Sort a Map by values

Here's a generic-friendly version:

public class MapUtil {
    public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) {
        List<Entry<K, V>> list = new ArrayList<>(map.entrySet());
        list.sort(Entry.comparingByValue());

        Map<K, V> result = new LinkedHashMap<>();
        for (Entry<K, V> entry : list) {
            result.put(entry.getKey(), entry.getValue());
        }

        return result;
    }
}

Best Answer

Related Solutions

Python – How to sort a list of dictionaries by a value of the dictionary

Java – Sort a Map by values

Related Topic