Tell me more ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.
up vote 5 down vote favorite
1

Consider the following code which plots a triangle.

 p = {{0, 0}, {.2, 0}, {0, .2}};
 {Cyan, Polygon[Dynamic[p]]} // Graphics

Mathematica graphics

Then adding (for example) {.1, -.1} yields a non-simple polygon with intersecting lines.

AppendTo[p, {.1, -.1}]

Mathematica graphics

Question: Given a list of 2D points that are plotted as a polygon by Graphics. Is there a way to re-order the points such that Graphics plots a simple polygon after a point which has been added that resulted in plotting a non-simple polygon?

share|improve this question
to understand better what you want, suppose I had p = {{-1, 1}, {1, 1}, {-1, -1}, {1, -1}, {0, 0}}; what polygon should be plotted? – acl Aug 14 '12 at 8:55
p1 = {-1, 1}; p2 = {1, 1}; p3 = {-1, -1}; p4 = {1, -1}; p5 = {0, 0}; p = {p1, p2, p4, p3, p5} would pass. – ndroock1 Aug 14 '12 at 9:05
That one is not convex by the way. I have been using the wrong words I realized. I don't want the ones which look like connected via a single point. Does that makes sense? – ndroock1 Aug 14 '12 at 9:08
2  
@ndroock1 Polygon doesn't plot unexpected polygons, it plots exactly what you tell it to plot. The order of the points matters however as you have learned. There isn't one particular "correct" order of traversing a number of points to form a polygon, so while you can find a different order which doesn't contain intersecting lines it may not be the one you where actually expecting. I suggest posting your full problem, since I suspect you could avoid this problem completely by always inserting a new point ordered in between the two nearest already present points, rather then prepending. – jVincent Aug 14 '12 at 13:23
1  
Also, now that you know that "convex" polygon is wrong terminology, you should update your question so that others aren't misled by your incorrect question. – rm -rf♦ Aug 14 '12 at 16:46
show 5 more comments

3 Answers

up vote 6 down vote

The function you may be looking for is FindCurvePath. Its task is to find reasonable curves through disorganized point sets. It is not guaranteed to find the solution that you find most pleasing but if often gets close. You may also end up with several disconnected lines instead of a single one.

(* some points randomly drawn on a sine shape *)
pts = {#, Sin[#]} & /@ RandomReal[{0, 2 \[Pi]}, 30];

Graphics@Line@pts

Mathematica graphics

(* now with FindCurvePath *)
Graphics@GraphicsComplex[pts, Line@FindCurvePath@pts]

Mathematica graphics

In the case of your point set it finds the following:

Graphics@GraphicsComplex[p, {EdgeForm[Black], Polygon@FindCurvePath@p}]

Mathematica graphics

i.e., a polygon and a line.

share|improve this answer
up vote 3 down vote

I'm assuming from your explanation that you aren't actually just interested in the convex hull, but simply inserting points into a polygon without creating self-intersecting lines. In this case, you can simply find the closest point and insert either before or after this, depending on which of the neighboring points are closest to the new point.

 insertIntoClosestEdge[line_, p_] := 
 Module[{closest, neighbors, nearclosest},
 closest = Nearest[line -> Automatic, p][[1]];
 neighbors = closest // Mod[# + {1, -1}, Length@line, 1] &;
 nearclosest = Nearest[line[[neighbors]] -> neighbors, {.1, -.1}][[1]];
 Insert[line, p, {Mod[closest - If[nearclosest < closest, 0, -1], Length@line]}]
 ]

It may need extending to work in all cases, but it shows the gist of the suggested solution.

share|improve this answer
up vote 2 down vote

Do you mean a convex hull? This is always a convex polygon, but in general, not every point in the list will be a vertex of the convex hull.

Needs["ComputationalGeometry`"]
Graphics[Polygon[p[[ConvexHull[p]]]]]
share|improve this answer
Convex is not the right word, I just found out. Sorry. – ndroock1 Aug 14 '12 at 9:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.