This is kind of clunky, written in C++, assumes you know your centroid
and convex hull, but is a fairly straight-forward manner of getting
the minimum bounding rectangle. The rotation is in there if you want
peel it out:
// findMBR
//
// Finds the minimum bounding rectangle of the convex hull
// We know that one side of the MBR is collinear with at
// least one side of the convex hull.
//
// Works by examining each side of the hull, rotating hull
// so it's axis-aligned. Then we calculate the aabr and area.
// If this is the smallest, we save the coordinates and angle
// of rotation. Once we are done, we rotate the coordinates of
// the best aabr back based on the angle of rotation.
//
// This is O(n*n) - but n isn't terribly large
//
// The "rotating calipers" method is O(n), but it is harder to
// implement for MRVIN
//
void ConvexHull::findMBR(void) {
if (gDebug_level > 1) {
cout << " findMBR, vc = " << aVertices.size() << "\n";
cout << " Vertices: \n";
for (unsigned v = 0; v < aVertices.size(); v++) {
Vertex * pv = aVertices.at(v);
cout << " " << pv->lId << ": (" << pv->dX << ",
" << pv->dY << ")\n";
}
}
mbrArea = REALLY_BIG_NUMBER;
mbrX1 = 0; // (x2,y2) (x3,y3)
mbrY1 = 0; // +-------+
mbrX2 = 0; // | |
mbrY2 = 0; // | |
mbrX3 = 0; // | |
mbrY3 = 0; // +-------+
mbrX4 = 0; // (x1,y1) (x4,y4)
mbrY4 = 0; //
double bangle = 0, bxmin = 0, bxmax = 0, bymin = 0, bymax = 0;
Vertex * A = aVertices.at(0);
for (unsigned v = 1; v <= aVertices.size(); v++) {
Vertex * B = aVertices.at(v%aVertices.size());
double angle = atan((B->dX - A->dX)/(B->dY - A->dY) );
double xmin = REALLY_BIG_NUMBER;
double ymin = REALLY_BIG_NUMBER;
double xmax = -(REALLY_BIG_NUMBER);
double ymax = -(REALLY_BIG_NUMBER);
for (unsigned w = 0; w < aVertices.size(); w++) {
Vertex * v = aVertices.at(w);
// Rotate the point to make AB axis-aligned
double x = centroid->dX + (v->dX - centroid->dX) *
cos(angle) -
(v->dY - centroid->dY) * sin(angle);
double y = centroid->dY + (v->dX - centroid->dX) *
sin(angle) +
(v->dY - centroid->dY) * cos(angle);
// Find the aabr
if (x < xmin) xmin = x;
if (x > xmax) xmax = x;
if (y < ymin) ymin = y;
if (y > ymax) ymax = y;
}
// Get the aabr area
double area = abs((xmax - xmin) * (ymax - ymin));
// If this is the smallest aabr, save the paramters
if (area < mbrArea) {
mbrArea = area;
bangle = -(angle);
bxmin = xmin;
bxmax = xmax;
bymin = ymin;
bymax = ymax;
} // Loop throught the vertices
B = A;
} // Loop through the segments
// Now we need to rotate the aabr back to get the real mmbr
mbrX1 = centroid->dX + (bxmin - centroid->dX) * cos(bangle) - (bymin
- centroid->dY) * sin(bangle);
mbrY1 = centroid->dY + (bxmin - centroid->dX) * sin(bangle) + (bymin
- centroid->dY) * cos(bangle);
mbrX2 = centroid->dX + (bxmin - centroid->dX) * cos(bangle) - (bymax
- centroid->dY) * sin(bangle);
mbrY2 = centroid->dY + (bxmin - centroid->dX) * sin(bangle) + (bymax
- centroid->dY) * cos(bangle);
mbrX3 = centroid->dX + (bxmax - centroid->dX) * cos(bangle) - (bymax
- centroid->dY) * sin(bangle);
mbrY3 = centroid->dY + (bxmax - centroid->dX) * sin(bangle) + (bymax
- centroid->dY) * cos(bangle);
mbrX4 = centroid->dX + (bxmax - centroid->dX) * cos(bangle) - (bymin
- centroid->dY) * sin(bangle);
mbrY4 = centroid->dY + (bxmax - centroid->dX) * sin(bangle) + (bymin
- centroid->dY) * cos(bangle);
return;
}
-=--=---=----=----=---=--=-=--=---=----=---=--=-=-
Eric B. Wolf 720-334-7734
On Tue, Jan 18, 2011 at 11:02 AM, Sean Gillies <[email protected]> wrote:
> A minimalist package for affine transformations of Python geospatial
> objects (in a GeoJSON format, say) would be handy, but I'm not aware
> of one. Numpy certainly has what you need, and matplotlib has some
> higher level classes based on numpy such as
> http://matplotlib.sourceforge.net/devel/transformations.html#matplotlib.transforms.Affine2D.
>
> Cheers,
>
> On Mon, Jan 17, 2011 at 10:14 AM, simo <[email protected]> wrote:
>> Hi all,
>>
>> As preamble, I have to say I'm new to Python and don't know (much)
>> about Java - I come from a PHP world.
>>
>> Anyway, since several months I follow GiS python activity, and I was
>> waiting for the day I'll have opportunity and overall time to work
>> with shapely and others open source python projects ....
>>
>> Finally that time has come and I'm trying to adapt Julien Gaffuri's
>> SmallestSurroundingRectangle to python (available here :
>> http://opencarto.svn.sourceforge.net/viewvc/opencarto/trunk/src/main/java/org/opencarto/geomalgo/SmallestSurroundingRectangle.java?revision=168&view=markup
>> )
>>
>> His algorithm call a Rotate method and I was not able to find
>> something similar into Python.
>> Do you know if such method is included somewhere?
>>
>> the java rotation class is available at :
>> http://opencarto.svn.sourceforge.net/viewvc/opencarto/trunk/src/main/java/org/opencarto/geomalgo/Rotation.java?revision=176&view=markup
>>
>> subsidiary question : what about a scaling method ?
>>
>> the scaling class is available at :
>> http://opencarto.svn.sourceforge.net/viewvc/opencarto/trunk/src/main/java/org/opencarto/geomalgo/Scaling.java?revision=168&view=markup
>>
>> many thanks,
>>
>> simo
>
>
>
> --
> Sean
>
