CODEWITHSUNDEEP
c++algorithmmathcomputational-geometry
Ziezi
Ziezi

Reputation: 6467

How to determine if a set of coordinates are vertices of a regular polygon?

I have a working class that generates regular polygons given: polygon center and polygon radius and number of sides. Implementation details of the two private member functions here.

The class interface looks like this:

class RegularPolygon: public Closed_polyline{
public:
    RegularPolygon(Point c, int r, int n)
        : center(c), radius(r), sidesNumber(n) 
    { generatePoly(); }

private:
    Point center;
    int radius;
    int sidesNumber;
    void generatePoly();
    void rotateCoordinate(Point& axisOfRotation, Point& initial, 
                          double angRads, int numberOfRotations);
};

Problem:

I am asked to implement a second way of generating regular polygons by using a set of coordinates1. The constructor needs firstly to perform a validity check of the passed coordinates:

RegularPolygon(vector<Point>& vertices)
   :center(), radius(), sideNumber()
{
   // validity check of the elements of vertices
}

My initial thought is to:

  1. Check if each pair of coordinates produces the same side length.
  2. Check for each lines'(generated by a pair of coordinates) relative orientation. (they should be at an angle 360/polygon sides, from each other)

Question:

  1. How could I check if all lines are properly oriented, i.e. their relative orientation? solved
  2. Is there any standard algorithm that can determine if a set of coordinates are vertices of a regular polygon?

Note:

After checking [1] and all the question and answers regarding generating coordinates. I didn't found what I'm searching for.

1 In clockwise sequence, passed with the vector: vertices

All the additional files for compilation could be found: here. The FLTK could be found here.

Upvotes: 1

Views: 2701

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726987

Your task would be a lot simpler if you could find the center of your polygon. Then you would be able to check the distance from that center to each vertex to verify the placement of the vertices on the circle, and also to check the angles from the center to each individual vertex.

Fortunately, there is an easy formula for finding the center of a polygon: all you need to do is averaging the coordinates in both dimensions. With the center coordinates in hand, verify that

  • The distance from the center to each vertex is the same, and
  • The angle between consecutive vertices is the same, and that angle is equal to 2π/N radians

These two checks are sufficient to ensure that you have a regular polygon. You do not need to check the distances between consecutive vertices.

Upvotes: 5

Related Questions