geometry/java problem

D

David E.

Here's somewhat of an interesting problem. I am creating a class called
Rectangle. It takes in 4 sets of Cartesian coordinates (i.e. (x,y)
coordinates.). I'm assuming that the rectangle can be rotated too when
receiving these coordinates.
How would I go about setting methods to
A>"order" them (so that when i trace the outsides, point A,B,C,D all are
continous, as opposed to crossing in the "middle"...
B> testing that they are equal sides BUT(this has been where i get stuck)
all 90 degree angles...

Just so you know that i've been thinking abou this rather than throwing it
at you, here have been my approaches..
Assuming points A, B, C, D
First i figured
if ((side AB==side DC) &&(side BC==side AD))
then it is a quadrilateral with 2 pairs of equal sides.. But a parallelogram
also fits this bill.
I figure this might get complicated. There were numerous things i thought
of. I guess my goal is to KISS, but I have a feeling it won't be that
simple... Any ideas?
This isnt for school.. just for my own.... ?entertainment?... heheheh

Thanks,
Dave
 
B

Brad BARCLAY

David said:
Here's somewhat of an interesting problem. I am creating a class called
Rectangle. It takes in 4 sets of Cartesian coordinates (i.e. (x,y)
coordinates.). I'm assuming that the rectangle can be rotated too when
receiving these coordinates.

How would I go about setting methods to
A>"order" them (so that when i trace the outsides, point A,B,C,D all are
continous, as opposed to crossing in the "middle"...

Probably the easiest way to handle this is to ensure that the values
can only be input in order. If you're storing them in an array called
"verticies", for example, just ensure that the points are in a circuit
when you move from point[k] to point[k+1].

If you need this for some sort of constructor that takes four sets of
co-ordinates to ensure the user entered them in the proper order, the
best thing to do is to calculate the points of intersection for each
pair of possible edges. There are only 6 possibile edges, two of which
will intersect for any quadrilateral. Discard these two. Having
discarded these two, you now know what edges don't exist, and can use
the remaining four to determine an ordering.

(What you're really doing here is figuring out a Hamilton Circuit for
the figure. Being a four-sided figure, there will only be 8 possible
circuits, all of which form a quadrilateral (with four different start
points travelling in each of two directions).
B> testing that they are equal sides BUT(this has been where i get stuck)
all 90 degree angles...

Try using the Pythagorean theorem in reverse. Take any three points
representing two adjacent edges of your quadrilateral. Calculate the
length of the sides this triangle would form. Using the central vertex
(the one at the corner you want to test for right-angledness), calculate
to see if the sum of the squares of its two edges is equal to the square
of the opposite side. If it is, you have a 90 degree angle. If it
isn't, you have some other angle (which, as I assume you're just testing
to see if the figure is a rectangle, should be all you care about).

Note that you'll probably want some delta in your comparison, as
rotated rectangles will probably see some rounding errors in your length
calculations. So when you calculate the squares (and the sums of the
squares), being off by a very tiny bit should be acceptable. This will
mean that some non-rectangles may wind up being considered "acceptable"
by your code, but this is probably better than having the code _reject_
proper rectangles just because of precision problems.
First i figured
if ((side AB==side DC) &&(side BC==side AD))

Be careful of your nomenclature here. What you want to check is not
that the two lines are equal (which would mean that they occupied the
exact same space) -- you want to test to see if their _lengths_ are equal.

HTH!

Brad BARCLAY
 
L

Larry A Barowski

David E. said:
Here's somewhat of an interesting problem. I am creating a class called
Rectangle. It takes in 4 sets of Cartesian coordinates (i.e. (x,y)
coordinates.). I'm assuming that the rectangle can be rotated too when
receiving these coordinates.
How would I go about setting methods to
A>"order" them (so that when i trace the outsides, point A,B,C,D all are
continous, as opposed to crossing in the "middle"...
B> testing that they are equal sides BUT(this has been where i get stuck)
all 90 degree angles...


For a simple initial test, if the two leftmost points have
the same x-coordinate, then the figure is either not a rectangle,
or is a rectangle oriented along the coordinate axes. Test for
rectangle-ness in this case is obvious.
If the two leftmost points don't have the same x-coordinate,
find the leftmost, topmost, rightmost, and bottommost points. If
this is a rotated rectangle, these points must all be different
(one point can't be both topmost and rightmost, etc.). Now
ordering the points as: leftmost, topmost, rightmost, and
bottommost will give you a clockwise order. To make sure it is
a rectangle, check that opposing sides are the same length, and
the diagonals are the same length (you can learn the diagonal
trick by watching "This Old House" reruns - no math class
needed).
Floating point coordinates are not exact, so you can not use
== to compare for sameness. Construct an "areSame" method that
computes the absolute value of the difference and returns true
if it is below some threshold. If scaling is arbitrary (the
rectangle can be very small or very large) then the threshold
must be a function of current scale - for example you could use
a fraction of the difference in x-coordinate of leftmost and
rightmost points. Otherwise, you can choose an appropriate
threshold based on the known range of possible rectangle sizes
and granularity of input.


-Larry Barowski
 
S

Sideshow Alex

For ordering, you can use the fact that for the given ordered rectangle
ABCD, the line segment AC will have the greatest length.

So, given the points P1, P2, P3, P4, arbitrarilty pick P1 as point A,
then caluclate the norms |P1P2|, |P1P3| and |P1P4|, the one that yields
the greatest value will be point C, then assign the others as B and D.

Note that this will only work if ABCD is indeed a rectangle.


-Alex
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,902
Latest member
Elena68X5

Latest Threads

Top