History of Trigonometry/APISupport

Robo Home | 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

	Revision 14 . . December 23, 2003 23:09 EST by PEZ
	Revision 13 . . December 23, 2003 22:07 EST by Tango