6

I have a set of points in the plane and I want to find all convex polygons without including a point inside them.

For example I want to find all triangles, all four sized polygons, all four five sized polygons and so on until is possible to find them without including a point inside them.

In the image, row a corresponds to convex polygons of size 3. While column 1 and 2 show correct examples of what I want, column 3 shows a triangle including two points inside of it, which I dont want.

Rows b and c show examples of polygons of size 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 any other language or if someone knows about an algorithm that can do it.

The algorithm could receive, beside the points, the size of the polygons to search, it would return all possibly correct polygons or empty if does not contain any polygon of that size.

I appreciate the help.

jessica
  • 379
  • 8
  • 23
  • 3
    you can also try asking at math.stackexchange.com . Just make sure that you formulate your problem mathematically and not from MATALB programming point-of-view. – Autonomous Feb 17 '14 at 22:05
  • I'm not sure I understand your problem: "[...] all triangles, all four sized polygons, [...] until is possible to find them without including a point inside them." Can you please try and reformulate it more clearly? – fuesika Feb 17 '14 at 23:48
  • @jessica, I take it the size of the polygon is an input parameter? – Nicu Stiurca Feb 18 '14 at 00:23
  • Should the polygons be convex? I expect they should, but your example b3 tells me different. – Vincent van der Weele Feb 18 '14 at 06:41
  • Good observation Heuster, that's why I put the point in blue color, but somehow I forgot to explain that. – jessica Feb 18 '14 at 21:06

2 Answers2

2

Step 1: Perform a Delaunay-Triangulation of the points.

Step 2:

  • For polygons of size 3: resulting triangles are the result.
  • For polygons of size 4: pick any pair of triangles that share two corners
  • For polygons of size 5: pick any polygon of size 4 and pair it with a triangle that shares exactly two corners
Jonas
  • 74,690
  • 10
  • 137
  • 177
  • 1
    Small clarification: To avoid "looping" back around a corner for higher point counts the additional triangle should share *exactly* two corners with the polygon. – Florian Brucker Feb 18 '14 at 08:56
  • @Jonas I think that Delaunay-Triangulation would let me out some possible traingles, for example a1 and a2 wouldn't be returned using Delaunay. – jessica Feb 18 '14 at 21:09
0

You can try the naive solution if it is feasible :-

  1. select k points for k sided polygon
  2. apply convex hull alogrithm on it
  3. if convex hull size equal k then the set of points form desired k sided polygon.

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

Vikram Bhat
  • 6,106
  • 3
  • 20
  • 19