10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – acl Aug 14 '12 at 8:55
  • $\begingroup$ p1 = {-1, 1}; p2 = {1, 1}; p3 = {-1, -1}; p4 = {1, -1}; p5 = {0, 0}; p = {p1, p2, p4, p3, p5} would pass. $\endgroup$ – nilo de roock Aug 14 '12 at 9:05
  • $\begingroup$ 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? $\endgroup$ – nilo de roock Aug 14 '12 at 9:08
  • 2
    $\begingroup$ @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. $\endgroup$ – jVincent Aug 14 '12 at 13:23
  • 1
    $\begingroup$ 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. $\endgroup$ – rm -rf Aug 14 '12 at 16:46
9
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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]]]]]
$\endgroup$
  • $\begingroup$ Convex is not the right word, I just found out. Sorry. $\endgroup$ – nilo de roock Aug 14 '12 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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