Geek asks and answers

Tracing a 2D polygon in 3D space - Corresponding algorithm?

I am currently working on a problem where I need to properly arrange (using something like the right rule) the nodes that make up a flat polygon in three-dimensional space. My idea so far is to build a transformation matrix to transform nodes into the xy plane, and then use Graham scanning. I need to make sure that the user enters only convex polygons, so if I find any “internal” nodes, I know that the polygon is concave and can throw an error. In addition to checking the bulge, Graham's scan sorting procedure will sort nodes for me.

I am not very familiar with optimized geometry algorithms. Does this seem like a suitable / efficient process? Or is there a better way:

1) Order the nodes of the polygon using some rule (for example, the RH rule) and 2) Make sure that the flat polygon (which cannot be in the xy plane) is convex?

+3
source share
1 answer

Yes, this is a very good solution. Here's how to implement it in order to ignore the numerical error.

- take any 3 points; these determine the plane, rotate appropriately
- check that abs(z)<THRESHOLD for all z-coordinates, now you can ignore them
- perform Graham scan which is O(n log(n)) time
- return order, else throw error if results.size < #points (non-convex)

You might want to select 3 points far enough apart, or a combination of many points (still have their problems) and make the THRESHOLD a little fraction of the maximum distance between them.

, , O(n log(n)), ( , X [X, X ^ 2] [0, max ^ 2]).

+1

More articles:


All Articles