Geek Answers Handbook

Find all polygons in points using MATLAB

I have a set of points on a plane, and I want to find all convex polygons without including points in them.

For example, I want to find all the triangles, all four sizes of polygons, all four five-dimensional polygons, and so on, until they cannot be found without including points in them.

In the image, line a corresponds to convex polygons of size 3. Columns 1 and 2 give the correct examples of what I want, column 3 shows a triangle that includes two points inside it, I don’t want to.

Lines b and c show examples of polygons of sizes 4 and 5.

b3 shows an example of a non-convex polygon

enter image description here

I wonder if there is a function in MATLAB or in any other language, or if someone knows about an algorithm that can do this.

The algorithm could receive, in addition to points, the size of the polygons to search, it would return all possible regular polygons or empty if it does not contain a polygon of this size.

I appreciate the help.

+6
source share
2 answers

Step 1: Perform triangular tagging of points.

Step 2:

  • For polygons of size 3: the result is triangles.
  • For size 4 polygons: select any pair of triangles that separate two corners
  • For polygons of size 5: select any polygon of size 4 and connect it to a triangle that divides exactly two angles
+2
source

You can try a naive solution if possible: -

  • select k points for k-sided polygon
  • apply a convex hull alorithm to it
  • if the size of the convex hull is k, then the set of points forms the desired polyhedron.

Time complexity: - O(2^N*N*logN)

0
source

More articles:


All Articles