0

For calculation of centroid of quadrangle, points need to be sorted in order of their occurrence along the quadrangle's perimeter. Having 4 points p1, p2, p3, p4 with coordinate x, y for each such point, so with p1.x, p1.y, p2.x, ... what is the most efficient way to sort points along perimeter?

Formula or algorithm in any programming language is welcome, Javascript is preferred.

4

1 に答える 1

1

The answer https://stackoverflow.com/a/2122620/502144 can help to solve the problem. However, it doesn't consider the order of points, only point set. Here is the modified table with the ordering:

ABC  ABD  BCD  CAD  hull
------------------------
 +    +    +    -   ABCD
 +    +    -    +   ABDC
 +    -    +    +   ACBD

ABC, ABD, BCD, CAD are orientations of triangles. Cases with 4 points forming a convex quadrangle are only considered. In other cases any ordering is be valid resulting in non-convex quadrangle.

于 2012-07-19T16:44:54.963 に答える