Trigonometry/APISupport

Robo Home | Trigonometry | Changes | Preferences | AllPages

Difference (from prior major revision) (no other diffs)

Changed: 6,76c6,9

You're right, i've just looked and there doesn't seem to be a lot of help in there. Does the rounded nature of the rectangle matter? If it doesn't then i would suggest making Line2Ds of each line of the rectangle, then calculate the equations of the lines ( (y-y1)/(y2-y1)=(x-x1)/(x2-x1) and simplify), and then solve them simultaneously. All in code. Should be a bit of fun! ;-) That's the only way i can see of doing it, and it isn't very practical. I suggest searching the net for something more useful (or possibly just someone who's already done what i suggest). -- Tango

Ok, i've done a little search for you, and the first page google found had this lovely bit of code:


 // Return a point as the intersection of two lines -- called from a Line object
 Point intersects(final Line line1) {
   Point localPoint = new Point(0, 0);
 
   double num = (this.end.y--this.start.y)*(this.start.x--line1.start.x) -
                (this.end.x--this.start.x)*(this.start.y--line1.start.y);
 
   double denom = (this.end.y--this.start.y)*(line1.end.x--line1.start.x) -
                  (this.end.x--this.start.x)*(line1.end.y--line1.start.y);
 
   localPoint.x = line1.start.x + (line1.end.x--line1.start.x)*num/denom;
   localPoint.y = line1.start.y + (line1.end.y--line1.start.y)*num/denom;
 
   return localPoint;
 }

It's a method for a Line object, and returns a Point object. I'm bored so i'll rewrite it for Java2D. Hang on. -- Tango


 // Return a point as the intersection of two lines
 Point2D intersects(Line2D line1, Line2D line2) {
   Point2D localPoint = new Point2D.Double(0, 0);
 
   double num =   (line1.getY2()--line1.getY1())*(line1.getX1()--line2.getX1()) -
                  (line1.getX2()--line1.getX1())*(line1.getY1()--line2.getY1());
 
   double denom = (line1.getY2()--line1.getY1())*(line2.getX2()--line2.getX1()) -
                  (line1.getX2()--line1.getX1())*(line2.getY2()--line2.getY1());
 
   localPoint.x = line2.getX1() + (line2.getX2()--line2.getX1())*num/denom;
   localPoint.y = line2.getY1() + (line2.getY2()--line2.getY1())*num/denom;
 
   return localPoint;
 }

There you go. I haven't tested it, or even compiled it, but it should work. -- Tango

Edit conflict! While Tango found the above answer I coded this:

private static final int TRACE_DEPTH = 16;

public Point2D findIntersection(Line2D line, Shape shape) {
return findIntersection(line, shape, 0);
}

private Point2D findIntersection(Line2D line, Shape shape, int depth) {
Point2D middle = new Point2D.Double((line.getX1() + line.getX2()) / 2, (line.getY1() + line.getY2()) / 2);
Point2D temp;

if (shape.contains(line.getP1()) == shape.contains(line.getP2()))
return null;

if (depth >= TRACE_DEPTH)
return middle;

temp = findIntersection(new Line2D.Double(line.getP1(), middle), shape, depth + 1);

if (temp != null)
return temp;
else
return findIntersection(new Line2D.Double(middle, line.getP2()), shape, depth + 1);
}

This is completely untested, but at least you will probably be able to fix it where it is broken. It should provide reasonable accuracy, though with a high computational cost, as it is merely a binary search. It should recurse 0 times if the line lies entirely inside or outside the shape, and should recurse between TRACE_DEPTH and 2 * TRACE_DEPTH times otherwise, with an average of 1.5 * TRACE_DEPTH (that is, 3 * TRACE_DEPTH calls to contains()). -- nano

He who asked shall have answers it seems. =)
* /LineIntersection
* /Intersection

Removed: 79,112d11

Indeed, a very clever solution, Nano. :-) I can't wait to see what this new movement is like, it looks like it is going to be very original. -- Tango

In my computer graphics class, we actually discussed an algorithm like nano's for line clipping. Of course, it can just as easily be done iteratively. -- Kawigi

So true, and the iterative version can use half of the calls to Shape.contains(). It should be quite a bit faster:

private static final int TRACE_DEPTH = 16;

public Point2D findIntersection(Line2D line, Shape shape) {
Point2D middle;
boolean p1, p2, ptemp;

if ((p1 = shape.contains(line.getP1())) == (p2 = shape.contains(line.getP2())))
return null;

for (int i = 0; i < TRACE_DEPTH; i++) {
middle = new Point2D.Double((line.getX1() + line.getX2()) / 2, (line.getY1() + line.getY2()) / 2);

if (p1 != (ptemp = shape.contains(middle))) {
p2 = ptemp;
line = new Line2D.Double(line.getP1(), middle);
} else if ((ptemp = shape.contains(middle)) != p2) {
p1 = ptemp;
line = new Line2D.Double(middle, line.getP2());
}
}

return new Point2D.Double((line.getX1() + line.getX2()) / 2, (line.getY1() + line.getY2()) / 2);
}

Again, it's untested. The best I can say is that I read through it quickly after I finished it and it seems to be all there. :) -- nano

Looks like it should work to me. I think your use of p1, p2 and ptemp could be simplified, but i'd have to think about it to be sure, and it's too late for thinking (9 o'clock seems a little early to be using that excuse, but it is xmas, after all). -- Tango

Is it just I who think the JavaAPI support for trigonometry stuff is a bit lame? I often find it hard to do simple stuff with it. Like finding out where two lines meet. Or where any two shapes meet for that matter. This happens to be what I am trying to figure out right now:

Suppose you have a RoundedRectangle2D? and a Line2D such that the line starts somewhere inside the rounded rectangle and stops somewhere outside it.
How can I determine the coordinates where the line crosses the rounded rectangle?

-- PEZ

He who asked shall have answers it seems. =)

Wow, thank you. I think I will have use for both of the functions. Wonderful approach to the problem Nano! To answer Tango's question above; Yes, the rounded nature of the rectangle matters. A lot. -- PEZ