CODEWITHSUNDEEP
c#algorithmpolygonsnon-convex
user1701450
user1701450

Reputation: 72

order list of Lat long vertices to form a polygon in C#

I have list of Lat long that form a polygon around a center point. I would like to get ordered List of Lat-Long clockwise so as to connect Lat-Long Vertices in that ordered list and form non-convex polygon.

Upvotes: 0

Views: 764

Answers (1)

Codor
Codor

Reputation: 17595

The generation of a polygon from a set of vertices is ill-defined, as can be seen in the following example.

Let

A = ( 0, 0)
B = ( 3,-3)
C = ( 6,-1)
D = ( 4,-1)
E = ( 4, 1)
F = ( 6, 1)
G = ( 3, 3)

One possibility to form a polygon clockwise is

A-G-F-E-D-C-B-A

and the ordering

A-G-E-F-C-D-B-A

is a different one. The first polygon is concave and the second aon is convex. If A is removed and the remaining points are mirrored at the axis G-B, it is even possible to define two non-convex polygons from the given set of vertices. More precisely, the set of vertices would be

B = ( 3,-3)
C = ( 6,-1)
D = ( 4,-1)
E = ( 4, 1)
F = ( 6, 1)
G = ( 3, 3)

E' = ( 2, 1)
F' = ( 0, 1)
D' = ( 2,-1)
C' = ( 0,-1)

and the two different polygons are

G-E-F-C-D-B-C'-D'-E'-F'-G

and

G-F-E-D-C-B-D'-C'-F'-E'-G.

However, if one ins interested in the convex hull polygon (the boundary of the convex hull) of the given vertices, there are many different algorithms to compute it.

Upvotes: 2

Related Questions