Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

How can I calculate the length and with of polygons using open source tools? By "polygon length" I mean the length of the longest line within the polygon (update: to be correct, I just need the longest line within the polygon's convex hull) and the width as the longest measure perpendicular to the length measurement.

Update: I'm trying to create a non-axis aligned minimum bounding rectangle for a polygon. The length of this minimum bounding rectangle would be the polygon's diameter.

share|improve this question
    
The width is "the longest measure perpendicular to the length measurement" (as stated above). –  underdark Sep 12 '10 at 18:39
1  
I think what you are trying to do is create a non-axis aligned minimum bounding rectangle for a polygon which is first constrained by the longest segment within the polygon and afterwards expanded by the remaining vertices of the polygon. –  Dandy Sep 12 '10 at 19:09
    
@Dandy: Yes, that's what I'm looking for. –  underdark Sep 12 '10 at 19:41
    
@underdark: In light of Dandy's solution below, which proposes computing a diameter, could you clarify exactly what you mean by "the longest segment within the polygon"? –  whuber Sep 12 '10 at 19:57
1  
@underdark: OK, in that case there are two good things to know. (1) The diameter will join two vertices of the polygon, so an exhaustive check will work. (2) However, the exhaustive check takes N^2 operations for N vertices. This is terrible performance for large polygons. If you might have to deal with such things, there are relatively simple algorithms that average N*log(N) operations: that's much faster. You can find these coded in Python and Avenue on ESRI's ArcScripts site; look for Dan Patterson's contributions. The code is clear and readily ported. –  whuber Sep 12 '10 at 20:24
show 3 more comments

4 Answers 4

up vote 2 down vote accepted

JTS provides a Minimum Bounding Circle (http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/algorithm/MinimumBoundingCircle.html) and a Minimum Diameter (http://tsusiatsoftware.net/jts/javadoc/index.html) - once you have those the rectangle should be easy to calculate.

share|improve this answer
1  
Nice Java solution. Does anyone know of something similar in Python? –  underdark Sep 12 '10 at 20:23
    
A circle can also be a great bounding region. –  Dandy Sep 12 '10 at 21:01
    
GEOS may have similar functions that you could access using Python. I'm not sure how far JTS and GEOS have diverged. –  iant Sep 13 '10 at 7:08
2  
About "Does anyone know of something similar in Python?" See geoscriptblog.blogspot.com/2010/06/… –  ThomasG77 Sep 14 '10 at 18:58
    
@ThomasG77: That's great! Thanks a lot for this resource. I'll give it a try as soon as possible. –  underdark Sep 15 '10 at 9:25
add comment

FWIW, in Postgis is a function since 1.5, ST_Longestline that returns the longestline between two geometries. If you feed that function with the same geometry twice instead of two different, you will get the longest line in that geometry. http://postgis.net/docs/ST_LongestLine.html

@Whuber. you write above that the longest line doesn't have to start and end in the polygons vertexes. You use the letter I as example. I don't get it. If I is represented by a Line with two vertexes, then that line has to be the longest line itself, right?

If the I letter is represented by a thin polygon, the longestline will be a diagonal line from say left upper vertex to right lower vertex.

But I cannot understand how there could be a longest line that doesn't end and start in polygon vertexes.

Do I miss understand something?

/Nicklas

Ok, Whuber, I misunderstood you, I read your answer once more. I was talking about what you call the diameter and you were talking about something else. Sorry

/Nicklas

share|improve this answer
add comment

If you can't find a specific tool to do it you could use pgSQL and PostGIS or get a developer to implement that algorithm for you.

Many ways to do it, but here is one broken into 2 stages:

1) For each vertex find the largest distance to each other vertex within the polygon which can be done with a simple little nested loop in a SISD environment such as .NET:

for(var i=0; i<count; i++)
 for(var j=i; j<count; j++)
  find the 2 vertices with the greatest distance
construct a segment from those two points
var length = Distance(segment.Begin,segment.End);

2) for the width there are a few ways, the easiest to implement I think would be this:

// make the longest segment horizontal
transform the polygon with a rotation of the negative angle of the longest segment
for each vertex in the polygon find the highest and lowest y-coord values
// the "width" would be the max y-coord minus the min y-coord
var width = maxy-miny
share|improve this answer
3  
Good try, but (1) does not seem to address the problem: it is just an inefficient way to find the polygon's diameter. There is no guarantee the diameter actually lies wholly within the polygon. In fact, the "longest line [segment] within the polygon" need not have either of its endpoints coincident with any of the polygon's vertices. (E.g., consider the interior of a capital "I": the solutions are nearly vertical segments running up the center of the letter, terminating near the midpoints of the top and bottom edges of the letter.) –  whuber Sep 12 '10 at 19:55
    
I read it as looking for the longest segment over the polygon rather than the largest segment within the interior of the polygon. Seeing it this way you can conceptualize it as the largest segment within the convex hull of those vertices. If that is the the askers intent I think I have the idea right. –  Dandy Sep 12 '10 at 21:01
    
Given the subsequent clarifications to the question, I fully agree that you read the OP's mind correctly. –  whuber Sep 16 '10 at 23:21
add comment

Use Postgis and use ST_envelope(geometry) to get the minimum bounding box coordinates (defined with four points). From this result, you just have to calculate now length and width

A solution using pure Postgis query. It does the job but I don't do test on speed, I use some wkb for quick debug, so this script can be improve.

SELECT line1,
       line2,
       CASE WHEN line1>line2 THEN line1
            WHEN line1<=line2 THEN line2           
       END AS length,
       CASE WHEN line2>line1 THEN line1
            WHEN line2<=line1 THEN line2           
       END AS width FROM (
SELECT ST_length(ST_AsText(ST_MakeLine(ST_AsText(ST_PointN(ST_Boundary(ST_envelope(the_geom)),1)),
ST_AsText(ST_PointN(ST_Boundary(ST_envelope(the_geom)),2))))) AS line1,ST_length(ST_AsText(ST_MakeLine(ST_AsText(ST_PointN(ST_Boundary(ST_envelope(the_geom)),2)),ST_AsText(ST_PointN(ST_Boundary(ST_envelope(the_geom)),3))))) AS line2
from tm_world_borders) AS size;
share|improve this answer
    
Is ST_envelope() axis-independent? –  underdark Sep 12 '10 at 21:53
1  
After some tests; it seems not :( Sorry... –  ThomasG77 Sep 13 '10 at 8:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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