Home.... | log in.... | Pub my question! | Sign-up....
Java-index >> Other Topics >> Algorithms

Maximum and 2nd longest diameters of polygon

I have a polygon in the form of a Point[] of Cartesian (x, y) pairs?for the sake of argument lets just say it齭 a simple closed loop and no crossing sections and I would like to calculate the second longest perpendicular diameter based on the maximum diameter which I have obtained by the following code:

publicboolean longestDiameter(Point[] points){

Point currentPoint;

Point focusPoint;

double maxDistance = 0.0;

double currentDistance = 0.0;

boolean contains =false;

Line2D.Double diameter;

for(int i = 0; i < points.length; i++){

focusPoint = points[i];

for(int j = 0; j < points.length; j++){

currentPoint = points[j];

currentDistance = focusPoint.distance(currentPoint);

if(!focusPoint.equals(currentPoint)){

diameter =new Line2D.Double(focusPoint, currentPoint);

//System.out.println("Current Point: X " + currentPoint.getX() + " Y " + currentPoint.getY());

//System.out.println("Diameter Points: X1 " + diameter.getX1() + " Y1 " + diameter.getY1() +

//" X2 " + diameter.getX2() + " Y2 " + diameter.getY2());

//contains = checkLineContainment(diameter, points);

//contains = checkLineContainment(getLinePoints(diameter), points);

contains =true;

if((maxDistance < currentDistance) && contains){

maxDistance = currentDistance;

longestDiameterPoints[0] = focusPoint;

longestDiameterPoints[1] = currentPoint;

}

}

}

}

if(maxDistance == 0.0)

returnfalse;

returntrue;

}

You齦l notice that I have checkLineContainment as a separate function. Basically I wrote this Boolean function to check to see if the points along the variable called diameter are contained inside the polygon, but I forced it to true for now. I also wrote a getLinePoints method because to my knowledge JDK 1.4.1 doesn齮 have a built in iterator which will provide a point by point array of the individual points on a line:

Its pretty long winded but it accounts for all possible slopes that you might expect, depending on where the two points being compared lie in relation to one another. This should provide me with a point by point vector which I can then use the opposite inverse slope of the maximum line to proceed in my calculation of the second longest diameter but it doesn齮.

// Gets the integer line points from a line and stores them in a vector

public Vector getLinePoints(Line2D.Double line){

Vector linePoints =new Vector();

Point2D startPoint = line.getP1();

Point2D endPoint = line.getP2();

Point2D currentPoint = startPoint;

double deltaY = (endPoint.getY() - startPoint.getY());

double deltaX = (endPoint.getX() - startPoint.getX());

double slope = 0.0;

if(deltaX != 0){

slope = deltaY / deltaX;

System.out.println("Slope: " + slope);

}

double b = (startPoint.getY() - slope*startPoint.getX());

while(!currentPoint.equals(endPoint)){

System.out.println("CurrentPoint X: " + currentPoint.getX() +" Y: " + currentPoint.getY());

System.out.println("StartPoint X: " + startPoint.getX() +" Y: " + startPoint.getY());

System.out.println("EndPoint X: " + endPoint.getX() +" Y: " + endPoint.getY());

// Positive Slope

if((startPoint.getX() > endPoint.getX()) &

(startPoint.getY() < endPoint.getY())){

System.out.println("Positive");

double y = (slope*(currentPoint.getX()-1)+b);

//System.out.println("Y=" + slope*(currentPoint.getX()-1)+b);

System.out.println("Y=" + y);

currentPoint =new Point((int)currentPoint.getX()-1, (int)roundDouble(y));

}

elseif((startPoint.getX() < endPoint.getX()) &

(startPoint.getY() > endPoint.getY())){

System.out.println("Positive");

double y = (slope*(currentPoint.getX()+1)+b);

//System.out.println("Y=" + slope*(currentPoint.getX()+1)+b);

System.out.println("Y=" + y);

currentPoint =new Point((int)currentPoint.getX()+1, (int)roundDouble(y));

}

// Negative Slope

elseif((startPoint.getX() < endPoint.getX()) &

(startPoint.getY() < endPoint.getY())){

System.out.println("Negative");

double y = (slope*(currentPoint.getX()+1)+b);

//System.out.println("Y=" + slope*(currentPoint.getX()+1)+b);

System.out.println("Y=" + y);

currentPoint =new Point((int)currentPoint.getX()+1, (int)roundDouble(y));

}

elseif((startPoint.getX() > endPoint.getX()) &

(startPoint.getY() > endPoint.getY())){

System.out.println("Negative");

double y = (slope*(currentPoint.getX()-1)+b);

//System.out.println("Y=" + slope*(currentPoint.getX()-1)+b);

System.out.println("Y=" + y);

currentPoint =new Point((int)currentPoint.getX()-1, (int)roundDouble(y));

}

// Horizontal Line

elseif((startPoint.getX() < endPoint.getX()) &

(startPoint.getY() == endPoint.getY())){

System.out.println("Zero");

double y = currentPoint.getY();

//System.out.println("Y=" + slope*(currentPoint.getX()+1)+b);

System.out.println("Y=" + y);

currentPoint =new Point((int)currentPoint.getX()+1, (int)roundDouble(y));

}

elseif((startPoint.getX() > endPoint.getX()) &

(startPoint.getY() == endPoint.getY())){

System.out.println("Zero");

double y = currentPoint.getY();

//System.out.println("Y=" + slope*(currentPoint.getX()-1)+b);

System.out.println("Y=" + y);

currentPoint =new Point((int)currentPoint.getX()-1, (int)roundDouble(y));

}

// Vertical Line

elseif(deltaX == 0 &&

(startPoint.getX() == endPoint.getX() &

startPoint.getY() < endPoint.getY()) ){

double y = currentPoint.getY()+1;

System.out.println("Undefinded");

System.out.println("Y=" + y);

currentPoint =new Point((int)currentPoint.getX(), (int)roundDouble(y));

}

elseif(deltaX == 0 &&

(startPoint.getX() == endPoint.getX() &

startPoint.getY() > endPoint.getY()) ){

int y = (int)currentPoint.getY()-1;

System.out.println("Undefinded");

System.out.println("Y=" + y);

currentPoint =new Point((int)currentPoint.getX(), (int)roundDouble(y));

}

linePoints.addElement(currentPoint);

}

for(int i = 0; i < linePoints.size(); i++){

System.out.println("Point @ " + i +" X: " + ((Point2D)linePoints.elementAt(i)).getX() +

" Y: " + ((Point2D)linePoints.elementAt(i)).getY() +"\n");

}

return linePoints;

}

I was wondering if anyone had any insight on this or had already done something similar.

[11463 byte] By [johnkalaigiana] at [2007-9-29 0:57:26]
«« HOW TO TRANSFER FILES?
»» Maximum and 2nd longest diameters of polygon
# 1

I'm not sure what you mean by _perpendicular_ diameter. If you

mean the maximum distance between two parallel lines just

touching the polygon, the maximum diameter is the length of

the longest diagonal. That seems to be what your code calculates.

In that case, I imagine you want the length of the second longest

diagonal.

That's as simple as keeping a list of two point pairs in order

of distance between them (or just the lengths of the corresponding

diagonals if you don't need to identify the points). Go through the

point pairs in turn, dropping the third largest from the list each

time. This is essentially a partial sorting algorithm. If you want

the nth longest where n is fairly large, this isn't very efficient,

but it should be OK for the second longest.

If you have very many points, you might like to screen out

non-competitive point pairs by using a conservative distance measure

such as the sum of the x and y displacements, and only calulate

the euclidean distance if the sum is greater than the second

gtreatest distance so far. This mightn't help much if you start

with points close together. You could start with nearly opposite

points, or a few random point pairs to improve this short cut.

TerryMoorea at 2007-7-13 3:22:20 > top of Java-index,Other Topics,Algorithms...
# 2

I guess the easiest way to ask this question is with pictures - here are two images - the first is what i am looking for with the blue (maximum diameter) and red (maximum perpendicular diameter) lines being perpendicular to one another and the second is what i'm hoping too avoid, because the maximum diameter is picked but not all the points are contained inside the polygon. According to my criteria all the points on the line MUST be inside the given ROI.

#1 http://luke.mynetwork.org:89/stuff/poly1.jpg

#2 http://luke.mynetwork.org:89/stuff/poly2.jpg

thanks,

John

johnkalaigiana at 2007-7-13 3:22:20 > top of Java-index,Other Topics,Algorithms...
# 3

If I get you right, when calculating the maximum diameter (MD) you basically calculate the distances between all points in the polygon and pick the longest?

What you will need is to be able to check if a line crosses a polygon segment. Lets call it the LPC-check (line-polygon crossing). It also provides the length between a point on the line and the crossing point.

You can use this LPC-check to verify that the MD only crosses the polygon at two places. The MD is a line and if more than two polygon segment crosses it the line has been outside the polygon.

You can also use the LPC-check to find the maximum perpendicular diameter (MPD). First you need to calculate a normal vector to the MD. This normal vector will be perpendicular to the MD. The normal vector can be placed at each point in the polygon and will then define a line. Now you do a LPC-check to find all polygon segment this line crosses. (If you find more than one you know the line has passed outside the polygon). You go through all the polygon points and do the LPC-check. Then you pick the longest, the MPD.

This would work I think. To bad one cannot draw sketches -:)

UlrikaJa at 2007-7-13 3:22:20 > top of Java-index,Other Topics,Algorithms...
# 4

> I guess the easiest way to ask this question is with

> pictures - here are two images - the first is what i

> am looking for with the blue (maximum diameter) and

> red (maximum perpendicular diameter) lines being

> perpendicular to one another and the second is what

> i'm hoping too avoid

>

> #1 http://luke.mynetwork.org:89/stuff/poly1.jpg

> #2 http://luke.mynetwork.org:89/stuff/poly2.jpg

This helps a lot, but I think the question is still ambiguous. I point

out some interpretations below and make some suggestions.

For the maximum perpendicular diameter, do you want the perpendicular

diameter that corresponds to the maximum diameter? This could be very

short compared to the maximum. In that case, the one corresponding to

the second longest diameter could be longer than the one that

corresponds to the maximum. (So the second maximum is longer than the

maximum :-)

As the next reply suggests, find the second maximum diameter (perhaps

it's OK if this lies partly outside the polygon so long as its

perpendicular doesn't, or perhaps not, it's up to you). Then slide a

perpendicular across so long as it crosses the polygon exactly twice,

until you find the maximum position. The maximum must occur when one

end passes through a vertex, so you only need to draw a line through

each vertex.

What if every diameter passes outside the polygon? For example, draw

two parallel spirals, then join the inside ends and the outside ends

to form a continuous line. Would you then want the maximum of the

parts of diameters that lie inside the polygon? This also applies if

only some diameters cross the boundary of the polygon.

Alternatively, you could mean, among all diameters, find the second

longest of all the perpendicular diameters. This is just the second

maximum diameter because every diameter is perpendicular to many

others. So I guess you can't mean that.

TerryMoorea at 2007-7-13 3:22:20 > top of Java-index,Other Topics,Algorithms...
Other Topics
Algorithms

Other Topics New Topic

Other Topics Hot Topic

Other Topics

All Classified