Bounding Rectangle of a Polygon - Android /Java

Question

I am creating an Android application , Here I want to make bounding rectangle of polygon shapes (concave / convex ) . I have coordinates of each polygon , I have no idea about this I tried for it but didn't satisfy .How will I create a generalized code to make bounding rectangle of each polygon .

score 2 · Accepted Answer · answered Jul 30 '14 at 13:07

2

If you iterate over all the points and calculate the minimum and maximum point in each coordinate axis, you can then take the extremes and form a rectangle.

void CalculateBoundingBox( Polygon p, Point lowerRight, Point upperLeft )
{
    //Method to calculate the bounding box of this polyline
    int size = p.size();
    double xmin = /*infinity*/;
    double xmax = /*negative infinity*/;
    double ymin = xmin, ymax = xmax;

    for ( int i = 0; i < size; ++i )
    {
        if ( p[i].x < xmin )
            xmin = p[i].x;

        if ( p[i].y < ymin )
            ymin = p[i].y;

        if ( p[i].x > xmax )
            xmax = p[i].x;

        if ( p[i].y > ymax )
            ymax = p[i].y;
    }

    lowerRight.set( xmax, ymin );
    upperLeft.set( xmin, ymax );
}

answered Jul 30 '14 at 13:07

Brandon Kohn

1,612
8
18

1

This code would be both cleaner, and faster if you set the min/max to the first point and then used Math.min and max. Thus removing the if statements. – Chris K Jul 30 '14 at 13:11
The method you describe is certainly equivalent, but why would it be faster? – Brandon Kohn Jul 30 '14 at 13:20
2

The quick answer is because it reduces CPU stalls. When repeating the same instructions over and over again, as is common in graphics processing then any CPU stall can be very expensive. conditional branches (if statements) are worth avoiding where one can as they can cause a CPU cache miss. Math.min/max are often implemented on modern JVMs using an intrinsic, that is the JVM swaps the java implementation of the method out for a platform specific version that can use CPU instructions not otherwise available to the Java language. – Chris K Jul 30 '14 at 13:28
Both Math.min and Math.max use conditionals. – Brandon Kohn Jul 30 '14 at 13:31
are you sure? See http://stackoverflow.com/questions/19892322/when-will-jvm-use-intrinsics and http://hg.openjdk.java.net/jdk7/jdk7/hotspot/file/0a2ecf4cc384/src/share/vm/classfile/vmSymbols.hpp – Chris K Jul 30 '14 at 13:32
In otherwords, you are correct that the Java implementation of Math.min and Math.max use conditionals, however Hotspot will swap those versions out for other versions (on platforms that support it) that do not need to. – Chris K Jul 30 '14 at 13:33
Yeah, at some level the CPU has to decide which of the two arguments is the min or max and return it. – Brandon Kohn Jul 30 '14 at 13:34
exactly. So the question is how efficiently can it do it, which with a bit of hardware knowledge comes down to can it do it without a branch prediction miss. x86 can if it uses cmovge, which Hotspot will be able to use if Math.max was used via the intrinsic. Otherwise the if would be done using conditional jumps, more instructions and misses; thus slower. See page 15 of https://www.cs.cmu.edu/~fp/courses/15213-s07/misc/asm64-handout.pdf. – Chris K Jul 30 '14 at 13:43
@BrandonKohn , thanks for your answer . It seems a good solution , I will try for it . – Jul 31 '14 at 05:22
@BrandonKohn , Please don't forgot to upvote the question , It can be good question for others too. – Jul 31 '14 at 05:26
Isn't this technically the "Axis Aligned Bounding Box"? The real bounding rectangle is called the "Oriented Bounding Box"... – kenyee Nov 10 '18 at 04:01
It is an AABB. OBB is another kind of bounding box which may have tighter bounds, but is more complex to calculate. They are both real. – Brandon Kohn Nov 13 '18 at 15:46

Bounding Rectangle of a Polygon - Android /Java

1 Answers1