CODEWITHSUNDEEP
algorithmcomputational-geometryconvex-hull
pgf
pgf

Reputation: 65

get the perimeter of a 2D set of points

I have a set of points in 2D ( coordinates for x and y ), now I need to discard all the points that are not meaningful to me, and what I mean by that is that I'm only interested in the area that this points are tracing.

In short, this

enter image description here

it's supposed to produce this

enter image description here

question: what algorithm can do this kind of filtering on this points ?

Upvotes: 5

Views: 5031

Answers (2)

vidit
vidit

Reputation: 6451

You can use Graham Scan to compute Convex hull of the given points. Once you have all the points on the convex hull you can eliminate the others.

There are other algorithms as well for computing convex hull, but Graham scan is easy to implement and is O(n logn).

Upvotes: 6

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70931

I believe you are looking for a convex hull algorithm. I personally use Graham Scan algorithm to implement convex hull as it has very good complexity O(n*log(n)) and is relatively easy to implement.

Upvotes: 3

Related Questions