CODEWITHSUNDEEP
ccomputational-geometry
cdk
cdk

Reputation: 6778

Graham's Scan in 3d, finding area of a general polygon

My goal is to find the unsigned area of a 3d planar polygon with n-many vertices given the unordered vertices of the polygon as well as the equation for the plane. I already have an efficient algorithm to calculate the area once the points are sorted into clockwise or counter-clockwise order (from this site: http://softsurfer.com/Archive/algorithm_0101/algorithm_0101.htm#3D%20Polygons)

I've decided to implement Graham's scan to reorder the points, there are many examples for the 2d case but not many for the 3d. I think my best options are either to use a transformation matrix to convert the 3d points to 2d (I am unsure how to do this) or to do it in 3d using the cross product in determining whether 3 points form a counter-clockwise turn. I think the latter would be more efficient since I could sum the areas found for each cross product and compute the final answer as I re-order the points.

However I'm still unsure how to implement Graham's scan in 3d. also, can I use the fact that I already know the set of vertices are co-planar and that they all must be included in the convex hull to my advantage?

EDIT: on further consideration, do I even need to use Graham's scan here? I already know that all the points are included in the hull, so wouldn't sorting them by angle suffice? The end goal is to have the points in counter-clockwise/clockwise order so that the area can be computed, and I thought the scan would be necessary to accomplish that.

Upvotes: 2

Views: 1952

Answers (1)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 71009

The plane in which all the points line can not be parallel to all main axis so find the one the is not parallel to the plane and project all the points in it(say Ox).

No two points will swap positions or coincide as the direction of the projection is not parallel to the plane. Now perform convex hull in the 2D case - you already know how to do that. Also because of my previous statement the order of the points in 3D will be the same as the order of the projected points - voilla no added complexity and same algorithm.

EDIT: of course any other projection will do but as projecting parallel to one of the main axis is really easy(simply removing one coordinate) I suggested this approach.

Upvotes: 2

Related Questions