0

I have an ArrayList of some Point-s. It's guaranteed that the Points are part of a convex polygon.

How can I calculate the perimeter of this convex polygon?

Update: The Points in the ArrayList are out of any order

Update 2: All the points are part of the convex polygon's edge

makesz1
  • 43
  • 6
  • You could convert the points into a new class of LineSegments, then sum up the length of the line segments. If the points are out of order, you could construct a matrix to determine who is connected to each other, and if you have a full polygon. – Clark Kent Apr 27 '15 at 17:09
  • Which would be the right method to find the point-pairs around the polygon? How should I order the list? – makesz1 Apr 27 '15 at 18:16
  • Are all points used in the creation of this polygon? – Clark Kent Apr 27 '15 at 18:44
  • All the points are part of the edge – makesz1 Apr 27 '15 at 19:44
  • -1: "Questions asking for homework help must include a summary of the work you've done so far to solve the problem, and a description of the difficulty you are having solving it." http://stackoverflow.com/help/on-topic – Alex Wittig Apr 27 '15 at 20:24
  • When the points are out of any order, you'll have to sort them first. Something like http://stackoverflow.com/questions/29629482/order-coordinates-around-center-coordinate-java might already be sufficient. Otherwise, you would have to do a http://en.wikipedia.org/wiki/Graham_scan , but the second Update sounds as if this should not be necessary – Marco13 Apr 27 '15 at 22:37

3 Answers3

1

Are the points in order? If so, you just need to sum up the distance from each vertex to the next

ControlAltDel
  • 33,923
  • 10
  • 53
  • 80
  • They are out of any order, so the ordering-method is my real question I guess. – makesz1 Apr 27 '15 at 18:12
  • I know how to do this, but I thought I'd challenge you with it first: Just using the points, can you find the center of the polygon? And if so, once you have the center, can you somehow use the angles of the lines made from the center to all of the points to order them? – ControlAltDel Apr 27 '15 at 18:48
1

Sum the distance between each two consecutive points.

Community
  • 1
  • 1
copeg
  • 8,290
  • 19
  • 28
0

If the points are not ordered, its impossible without determining the correct order. Thats because if there are more than 3 points there is more than one polygon they could form.

I'm not entirely sure the constraint that the points are forming a convex polygon is sufficient to determine a canonic shape from the point cloud.

My guess is that by taking a random point from the list, and then looking for the nearest remaining point you can build a canonic order. From there its just summing up the length of the lines formed by consecutive points.

Edit: On second thought, scratch that idea. It won't work for all cases. That leaves you with permuting the points and checking if the formed polygon is indeed convex.

The question on how to check if a polygon is convex has been asked and answered here: How do determine if a polygon is complex/convex/nonconvex?

Community
  • 1
  • 1
Durandal
  • 19,919
  • 4
  • 36
  • 70
  • Wouldn't it be possible to determine if the points were out of order by looking for line segments that overlap? – Clark Kent Apr 27 '15 at 18:49
  • @SaviourSelf Well, an intersection between two line segments would for sure be proof the polygon is not convex; so its a piece to help solve the puzzle. – Durandal Apr 27 '15 at 18:55
  • Right, but if all points are used, wouldn't there only be 1 circuit with no intersections? – Clark Kent Apr 27 '15 at 18:57
  • @SaviourSelf What if there is a case where a permutation exists that has no intersections but is not convex either? – Durandal Apr 27 '15 at 18:58
  • Assuming all points can form a convex polygon, is that case a possibility? I don't think it is, because it would cause an intersection. – Clark Kent Apr 27 '15 at 19:07
  • @SaviourSelf I can imagine two edge cases where there are no line intersections but the polygon can be concave: If one point coordinate appears twice or three consecutive points that form a straight line. Both allow for an indentation that may be considered "not intersecting". – Durandal Apr 27 '15 at 19:26
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/76385/discussion-between-saviour-self-and-durandal). – Clark Kent Apr 27 '15 at 19:27