2
$\begingroup$

Given a set of (X,Y) points, is it possible to create two or more polygons from the points (can be non-convex, but must use all the points exactly once), or is only one possible?

At a high level, I'm trying to figure out whether it's possible to be given a set of (X,Y) points and deterministically draw "the" polygon from them, even if the points are "unsorted". Or, whether that is ambiguous as multiple polygons are possible.

$\endgroup$
1
  • $\begingroup$ Take the vertices of a rectangle and its center, for example. $\endgroup$
    – dxiv
    Apr 5, 2018 at 1:44

2 Answers 2

Reset to default
3
$\begingroup$

Let $ABCD$ be a square and $E$ the centre of the square. Then $$AEBCD\quad\hbox{and}\quad ABECD\quad\hbox{and}\quad ABCED\quad\hbox{and}\quad ABCDE$$ are all "proper" pentagons.

$\endgroup$
1
  • $\begingroup$ I upvoted this answer, but am accepting LHF's answer because the convex hull addendum is very helpful to know. $\endgroup$
    – Tommy
    Apr 6, 2018 at 0:03
1
$\begingroup$

There is always at least one simple polygon with the given points as vertices. For instance, the polygon with least perimeter is simple, but it is hard to compute.

An easy solution is provided by Graham scan, which starts by implicitly creating a simple polygon with the given points as vertices.

If the points are all vertices of their convex hull, then there is only one simple polygon with the given points as vertices, the convex hull.

In general, there can more than one simple polygon with the given points as vertices.

The problem is called curve reconstruction and is well studied.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .