1

I have a list of vertices in 3d, in random order. I need to construct a polygon from them.

I've found a solution for this in 2d, that uses polar coordinates: ordering shuffled points that can be joined to form a polygon (in python)

It calculates the center of the shape, then arranges the vertices by polar coordinate. Problem is, in 3d there are 2 angles involved, if I use spherical coordinates. How do I sort my list of vertices in case of sphereical coordinates?

Community
  • 1
  • 1
user1617735
  • 451
  • 5
  • 16

1 Answers1

1

Are the points lying on a plane? First find the center, then use a vector cross product on the relative positions of a couple randomly chosen points to find the normal to the plane. Analyze the coordinates of the points relative to the center into components along the normal and perpendicular. The perpendicular components are a 2D problem, for which you've already found a solution.

DarenW
  • 16,549
  • 7
  • 63
  • 102
  • 1
    The points should be on the plane, yes. So the idea is to calculate points coordinates in 2d on the plane, considering the center of shape to be (0,0)? – user1617735 Feb 08 '15 at 20:03