This week's book giveaway is in the Android forum. We're giving away four copies of Head First Android and have Dawn & David Griffiths on-line! See this thread for details.

To minimally improve efficiency you can omit the call to Math.sqrt, since that is applied to both sides of the equality comparison. Also, instead of casting doubles to ints, I'd do something like "if Math.abs(diglen1 - diglen2) < EPSILON" with some appropriate bound for EPSILON. Not for efficiency, but for correctness.

A problem with this approach is that there are shapes for which "true" will be returned even though the figure is not a rectangle, e.g. (0,0) (1,1) (2,0) (1,3).

If sides of rectangle are not parallel to X/Y axes then we can check for product of slopes of adjacent sides.m1*m2 must be -1 if sides are perpendicular. and then we can check if opposite pair is of same length. If sides of rectangle are parallel to XY then no need to check for slope products.Will this be efficient? not sure [ October 29, 2007: Message edited by: Arjun Shastry ]

MH

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1888

posted

0

We need to do this by taking points clockwise/anticlokwise.

ankur rathi
Ranch Hand

Joined: Oct 11, 2004
Posts: 3830

posted

0

Originally posted by Ulf Dittmer: To minimally improve efficiency you can omit the call to Math.sqrt, since that is applied to both sides of the equality comparison.

Also, instead of casting doubles to ints, I'd do something like "if Math.abs(diglen1 - diglen2) < EPSILON" with some appropriate bound for EPSILON. Not for efficiency, but for correctness.

It's not clear.

A problem with this approach is that there are shapes for which "true" will be returned even though the figure is not a rectangle, e.g. (0,0) (1,1) (2,0) (1,3).

Most important comment. Any other way to check for rectangle?

Originally posted by Arjun Shastry: If sides of rectangle are not parallel to X/Y axes then we can check for product of slopes of adjacent sides.m1*m2 must be -1 if sides are perpendicular. and then we can check if opposite pair is of same length. If sides of rectangle are parallel to XY then no need to check for slope products.Will this be efficient? not sure

[ October 29, 2007: Message edited by: Arjun Shastry ]

Also, instead of casting doubles to ints, I'd do something like "if Math.abs(diglen1 - diglen2) < EPSILON" with some appropriate bound for EPSILON. Not for efficiency, but for correctness.

It's not clear.

Remember that in any computer, floats are (usually) not precise - they get rounded to a finite number of places. So, just because the sides are mathematically equal in lenght, your computations won't necesarily be exactly equal. Ulf's suggestion is to take the difference in lengths, and make sure that that is very small - Epsilon is the greek letter often used in math to represent some small amout. it's up to you to determine how exact it needs to be.

for example, if your rectangles are 3+ km on a side, and your measurements are in cm, then your Epsilon might be 1 cm. However, if they are around 10cm on a side, your Epsilon would probably be in something like micrometers.

Any other way to check for rectangle?

I'm not sure you really need to check the length of the sides at all. I thing you can do it by A) checking the slopes of opposite sides are equal (again, use the difference < Epsilon technique), and B) that the product of the two slope values is about -1 (there's that pesky Epsilon again). if you have a parallelagram (A), and that the sides meet at right angles (B), you have a rectangle.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

[Fred]: Remember that in any computer, floats are (usually) not precise - they get rounded to a finite number of places. So, just because the sides are mathematically equal in lenght, your computations won't necesarily be exactly equal.

That's true in general. However in this case, note that the original inputs are all ints. That means that all the addition, subtraction, and multiplication will be exact. It's not until we do either division or sqrt() that floating point comes into play. And the sqrt() is not necessary for this problem, as shown above. So it's really just division that's an issue here, which you need in order to find a slope.

Now, if two slopes are really equal, this means that the int values for things like (b1 - a1) and (b2 - a2) will be exactly equal. And when you perform the division - well, first you have to make sure the division is done as floating-point division, not integer division. That's important so that a slope of 1/3 and a slope of 2/3 don't get rounded to the same value, 0. But assuming you do that, if the slopes are "really" equal, then the inputs to the division will be exactly equal for both times you calculate the slope. Which means that, even if there's some small rounding error in the double result, it should be exactly the same error each time. Assuming the slopes are really equal to begin with. If they're different, then the rounding errors will probably be different too - but that shouldn't matter. We just need to be able to detect if the slopes are equal or not. If the slopes are really equal, the double results will be exactly equal. That's enough for us.

For comparison, I would not be certain that

1.0 / 3.0

and

1111111111.0 / 3333333333.0

give the exact same result. But I would be sure that

1.0 / 3.0

gives the exact same result whenever you repeat it with the same inputs (on the same machine, using the same JDK). That's the repeatability I'm depending on here.

With that in mind, I don't think there's any real need in this problem to worry about problems with floating-point equality and epsilon. It's good practice to consider this sort of thing in general, true. But I don't see how it can affect the results here.

Incidentally, note that for vertical lines, the slope should come out to Double.POSITIVE_INFINITY or Double.NEGATIVE_INFINITY. If you're careful, it's probably possible to handle these cases with the same code that handles other slopes. But test to be sure.

[ankur]: Any other way to check for rectangle?

[Fred]: I'm not sure you really need to check the length of the sides at all. I thing you can do it by A) checking the slopes of opposite sides are equal [...] if you have a parallelagram (A), and that the sides meet at right angles (B), you have a rectangle.

Yeah, there are several ways to do this. I think you always need to check at least one of the four angles to make sure it's a right angle. Some of the options are:

Check three of the angles to make sure they're right angles. (If they are, then the fourth must be a right angle as well.)

Check just one angle, and check that each pair of opposite sides has the same length.

Check two angles, and check that the two diagonals have the same length.

Other more complex combinations are possible. But given that you always seem to need to check at at least one angle, you need to write code to do that. And once you've done that for one angle, it's trivial to check two more angles as well. So checking three angles is probably the simplest solution.

"I'm not back." - Bill Harding, Twister

ankur rathi
Ranch Hand

Joined: Oct 11, 2004
Posts: 3830

posted

0

Originally posted by Arjun Shastry: If sides of rectangle are not parallel to X/Y axes then we can check for product of slopes of adjacent sides.m1*m2 must be -1 if sides are perpendicular. and then we can check if opposite pair is of same length. If sides of rectangle are parallel to XY then no need to check for slope products.Will this be efficient? not sure

[ October 29, 2007: Message edited by: Arjun Shastry ]

It Seems to be working. [ October 31, 2007: Message edited by: Ulf Dittmer ]

How about a solution without any calls to pow() or any division?

Obviously isRectangle() does nothing but pick apart the array of arguments and call makeRect() with the vertices in the three possible orders. The logic for identifying a rectangle is all in makeRect().

Does everyone agree that the second and third parts of the makeRect() return expression are sufficient (and necessary) to identify a parallelogram? Those combined with the perpendicularity test (which I assert without proof is complete and correct) in the first part of the expression lets only rectangles through.

Cool?

[ October 31, 2007: Message edited by: Ryan McGuire ] [ October 31, 2007: Message edited by: Ulf Dittmer ]

ankur rathi
Ranch Hand

Joined: Oct 11, 2004
Posts: 3830

posted

0

Originally posted by ankur rathi:

It Seems to be working.

[ October 31, 2007: Message edited by: Ulf Dittmer ]

Above doesn't work for sequence: [1 1 3 1 5 3 3 3] and many others...

ankur rathi
Ranch Hand

Joined: Oct 11, 2004
Posts: 3830

posted

0

Ryan,

Can you explain a bit more:

((ax==bx && by==cy) || (ay==by && bx==cx) || ((ay-by)*(by-cy) == -(ax-bx)*(bx-cx))) - two adjacent segments are perpendicular

((ay-by)*(by-cy) == -(ax-bx)*(bx-cx)) - it's clear. Why first two conditions are required: (ax==bx && by==cy) || (ay==by && bx==cx)???

(dx-cx==ax-bx) - two opposite sides have the same x range

We should have checked for length of opposite sides:

Those first two conditions ( (ax==bx && by==cy) and (ay==by && bx==cx) ) are not required at all. They're completely covered by the third condition.

But the following both report true, even though they're obviously not rectangles:

[ankur]: We should have checked for length of opposite sides:

Nah, using pow() and sqrt() is much less efficient, and not necessary. Of course it's possible to eliminate both of those, but you still end up with more multiplications or divisions than Ryan's method. Checking the x and y ranges separately is a good way to check both slope and length of two opposite sides with a minimum of calculation. Aside from a few special cases above (and the redundant conditions already mentioned), the method looks good to me.

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

My revised version, based on Ryan's algorithm:

[ November 01, 2007: Message edited by: Jim Yingst ]

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1036

4

posted

0

Originally posted by Jim Yingst: Those first two conditions ( (ax==bx && by==cy) and (ay==by && bx==cx) ) are not required at all. They're completely covered by the third condition.

Ahhh yes. I had the first two parts in there when I was going to use division to calculate the slopes to avoid dividing by zero. Since I got rid of the division by rearranging the equation, I indeed don't need those equality tests anymore.

But the following both report true, even though they're obviously not rectangles: ...Four superimposed points: ...Two superimposed lines:

Good point. I was more concerned with showing how to get rid of the sqrt(), pow() and division than worrying about degenerate cases. But you're right, EVERY case should be handled correctly.

Then again, I could argue that four superimposed points DO make a rectangle. Any two opposite sides are the same length, and the dot product of any two adjacent sides comes out to 0. Likewise for two superimposed lines. [ November 01, 2007: Message edited by: Ryan McGuire ]

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

[Ryan]: Good point. I was more concerned with showing how to get rid of the sqrt(), pow() and division than worrying about degenerate cases. But you're right, EVERY case should be handled correctly.

Yeah, I only looked carefully at that area because you'd explicitly asked if we agreed that your conditions were sufficient and necessary. Admittedly you were asking about a different part of the conditions, but "I assert without proof" was a red flag for me. And when ankur asked about the first two conditions, that got me double-checking that it was OK to eliminate them, which got me thinking about what exactly would happen if one or more of those terms were zero, etc.

[Ryan]: Then again, I could argue that four superimposed points DO make a rectangle. Any two opposite sides are the same length, and the dot product of any two adjacent sides comes out to 0. Likewise for two superimposed lines.

Hm, I think you'd have a hard time finding a definition of rectangle that refers to dot products without mentioning nonzero length. Most all definitions would depend on having a right angle, and the angle between zero-length lines (or one zero-length line and a nonzero-length line) is surely undefined, no?

Originally posted by Ryan McGuire: Then again, I could argue that four superimposed points DO make a rectangle.]

Well, they do. In mathematics the number zero is just as good as the numbers greater than zero. This rule applies to all mathematical concepts starting with the empty set and going on from there, and it always applies unless there are reasons not to apply it. For example it's true that x/x = 1 for non-zero x, but there are reasons why you can't extend that to the case where x is zero. But for the rectangle, there aren't any such reasons, so if you can have a square of side x for any positive x then you can have a square of side zero too.

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

For the points (0,0), (0,0), (0,0), (0,0), I'd be Ok with saying they form an equilateral quadrilateral - a rhombus - but how can one say that it's a square as opposed to a skewed rhombus? How does one establish that any of the angles (if we assume there's anything that can be meaningfully called an angle) are right angles? To me that seems just as problematic as assigning a value to 0/0. So far I still don't buy it.

One could argue that it's just as incorrect to say that this isn't a square as to say that it is. Returning false from the method could be seen as just as incorrect as returning true. In which case the most appropriate response might be to throw an IllegalArgumentException. Ultimately for a method like this, the correct answer will depend on what the intended use of the method is. Why does the caller care whether they have arectangle or not, and based on that context, which answer is more appropriate here? And do we want to force callers to either check their arguments or catch the exception? I don't think there's any one answer to that, but in general it seems to me that the arguments in favor of returning false are at least as strong as those for returning true. [ November 01, 2007: Message edited by: Jim Yingst ]

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1036

4

posted

0

From the Wikipedia article on Dot Product:

Two non-zero vectors a and b are perpendicular if and only if a � b = 0.

Rather than interpreting this as restricting perpendicularity to non-zero vectors, I take it to say nothing one way or the other about zero-length vectors.

From later in that same article:

In particular, two vectors are considered orthogonal if their dot product is zero

IN THE ABSENCE OF APPLICATION-SPECIFIC REQUIREMENTS, I'm going to point to this second quote and say my original code is "correct".

(If it's in Wikipedia, it MUST be right.) [ November 02, 2007: Message edited by: Ryan McGuire ]