CODEWITHSUNDEEP
javaalgorithmgeometry
Pedro Martins
Pedro Martins

Reputation: 125

Perimeter for any polygon - java

How can I efficiently find the perimeter of any given regular or irregular polygon?

I have a list that contains the points of a polygon (at least it contains 3 points) so the polygons begin can be triangle, rectangle, pentagon, hexagon and so forth

protected List<Point> coordinates = new ArrayList<Point>();

My class Point is the following:

public class Point {

    private double _x_, _y_;
    public double y;
    public double x;
    public Point() {
        _x_ = 0;
        _y_ = 0;
    }
    public Point(double x, double y) { 
        setX(x); setY(y); 
    }
    public double getX() { return _x_; }
    public double getY() { return _y_; }
    public void setX(double x) { assert x>0; _x_ = x; }
    public void setY(double y) { assert y>0; _y_ = y; }

    public double dist (Point p) { 
        double dx = getX() - p.getX();
        double dy = getY() - p.getY();
        return Math.sqrt(dx*dx + dy*dy); 
    }


    public String toString() {
        return ((int)getX()+" "+(int)getY());
    }
}

So I am looking for a general formula for the perimeter of any given polygon? Is this even possible ?

I want to implement this on a abstract Polygon class that has subclasses triangle and rectangle, but i want a general formula for all polygons.

I have tried the following:

public double perimeter() {
    double distance = 0;
    for(int i = 0; i < coordinates.size(); i++) {
        for(int j = i+1; j < coordinates.size(); j++) {
            if(j > i) {
                distance += coordinates.get(i).dist(coordinates.get(j));
            }
        }
    }
    return distance;
}

Upvotes: 0

Views: 6220

Answers (2)

user1196549
user1196549

Reputation:

Efficient computation is different for regular and irregular polygons !

For a regular inscribed polygon, the perimeter is 2nr sin(π/n), and the time to compute it does not depend on n. (By the way, for very large n the sine is quasi equal to its argument and the perimeter simplifies to 2πr.)

For an irregular polyon, you have to accumulate the Euclidean distances between pairs of consecutive vertices, which costs you n square root evaluations.

I recommend to avoid the costly modulo operation by means of two indexes:

    int len = coordinates.size();
    for(int i = len - 1, j= 0; j < len; i= j, j++) {
         distance += coordinates.get(i).dist(coordinates.get(j));
    }

Upvotes: 1

Akashdeep Saluja
Akashdeep Saluja

Reputation: 3089

Here is the code for finding perimeter if the points are ordered from first point connecting to second and second to third, ....., and last to first.

public double perimeter() {
    double distance = 0;
    int len = coordinates.size();
    for(int i = 0; i < len; i++) {
         distance += coordinates.get(i).dist(coordinates.get((i+1)%len));
    }
    return distance;
}

Upvotes: 1

Related Questions