蒙特利尔的麦吉尔大学:计算几何课程资料
蒙特利尔的麦吉尔大学的计算几何课程资料:
1. Introduction
(资料图片)
When talking about distances, we usually mean the shortest : for instance, if a point X is said to be at distance D of a polygon P, we generally assume that D is the distance from X to the nearest point of P. The same logic applies for polygons : if two polygons A and B are at some distance from each other, we commonly understand that distance as the shortest one between any point of A and any point of B. Formally, this is called a miniminfunction, because the distance D between A and B is given by :
(eq. 1)
This equation reads like a computer program : « for every point a of A, find its smallest distance to any point b of B ; finally, keep the smallest distance found among all points a».
That definition of distance between polygons can become quite unsatisfactory for some applications ; let"s see for example fig. 1. We could say the triangles are close to each other considering their shortest distance, shown by their red vertices. However, we would naturally expect that a small distance between these polygons means that no point of one polygon is far from the other polygon. In this sense, the two polygons shown in fig. 1 are not so close, as their furthest points, shown in blue, could actually be very far away from the other polygon. Clearly, the shortest distance is totally independent of each polygonal shape.
Figure 1 :The shortest distance doesn"t consider the whole shape.
Another example is given by fig. 2, where we have the same two triangles at the same shortest distance than in fig. 1, but in different position. It"s quite obvious that the shortest distance concept carries very low informative content, as the distance value did not change from the previous case, while somethingdid change with the objects.
Figure 2 :The shortest distance doesn"t account for the position of the objects.
As we"ll see in the next section, in spite of its apparent complexity, the Hausdorff distance does capture these subtleties, ignored by the shortest distance.
2. What is Hausdorff distance ?
Named after Felix Hausdorff (1868-1942), Hausdorff distance is the « maximum distance of a set to the nearest point in the other set » [Rote91]. More formally, Hausdorff distance from set A to set B is a maximinfunction, defined as
(eq. 2)
where a and b are points of sets A and B respectively, and d(a, b) is any metric between these points ; for simplicity, we"ll take d(a, b) as the Euclidian distance between a and b. If for instance A and B are two sets of points, a brute force algorithm would be :
Brute force algorithm :
1. h = 0 2. for every point ai of A, 2.1 shortest = Inf ; 2.2 for every point bj of B dij = d (ai , bj ) if dij < shortest then shortest = dij 2.3 if shortest > h then h = shortestFigure 3 :Hausdorff distance on point sets.
This is illustrated in fig. 3 : just click on the arrow to see the basic steps of this computation. This algorithm obviously runs in O(n m) time, with n and m the number of points in each set. It should be noted that Hausdorff distance is oriented (we couldsay asymmetricas well), which means that most of times h(A, B) is not equal to h(B, A). This general condition also holds for the example of fig. 3, as h(A, B) = d(a1, b1), while h(B, A) = d(b2, a1). This asymmetry is a property of maximin functions, while minimin functions are symmetric. A more general definition of Hausdorff distance would be :
H (A, B) = max { h (A, B), h (B, A) }(eq. 3)
which defines the Hausdorff distance betweenA and B, while eq. 2 applied to Hausdorff distance fromA toB (also called directedHausdorff distance). The two distances h(A, B) and h(B, A) are sometimes termed as forwardand backwardHausdorff distances of A to B. Although the terminology is not stable yet among authors, eq. 3 is usually meant when talking about Hausdorff distance. Unless otherwise mentionned, from now on we will also refer to eq. 3 when saying "Hausdorff distance".
If sets A and B are made of lines or polygons instead of single points, then H(A, B) applies to all defining points of these lines or polygons, and not only to their vertices. The brute force algorithm could no longer be used for computing Hausdorff distance between such sets, as they involve an infinite number of points.
So, what about the polygons of fig. 1 ?Remember, some of their points were close, but not all of them. Hausdorff distance gives an interesting measure of their mutual proximity, by indicating the maximal distance between anypoint of one polygon to the other polygon. Better than the shortest distance, which applied only to onepoint of each polygon, irrespective of all other points of the polygons.
Figure 4 :Hausdorff distance shown around extremum of each triangles of fig. 1. Each circle has a radius of H( P1 , P2).
The other concern was the insensitivity of the shortest distance to the position of the polygons. We saw that this distance doesn"t consider at all the disposition of the polygons. Here again, Hausdorff distance has the advantage of being sensitive to position, as shown in fig.5.
Figure 5 :Hausdorff distance for the triangles of fig. 4 at the same shortest distance, but in different position.
3. Computing Hausdorff distance between convex polygons
3.1 Assumptions
Throughout the rest of our discussion, we assume the following facts about polygons A and B :
Polygons A and B are simple convex polygons ; Polygons A and B are disjoint from each other, that is : - they don"t intersect together ; - no polygon contains the other.
3.2 Lemmas
The algorithm explained in the next section is based on three geometric observations, presented here. In order to simplify the text, we assume two points aand bthat belong respectively to polygons A and B, such that :
d (a, b) = h (A, B)
In simple words, ais the furthest point of polygon A relative to polygon B, while bis the closest point of polygon B relative to polygon A.
Lemma 1a :The perpendicular to abat ais a supporting line of A, and A is on the same side as B relative to that line.
Proof of lemma 1a
Lemma 1b :The perpendicular to abat bis a supporting line of B, and aand B are on different sides relative to that line.
Proof of lemma 1b
Lemma 2 :There is a vertex xof A such that the distance from xto B is equal to h (A, B).
Proof of lemma 2
Lemma 3 :Let bi be the closest point of B from a vertex a i of A. If µ is the moving direction (clockwise or counterclockwise) from bi to bi+1 then, for a complete cycle through all vertices of A, µ changes no more than twice.
Proof of lemma 3
3.3 Algorithm
The algorithm presented here was proposed by [Atallah83]. Its basic strategy is to compute successively h(A,B) and h(B, A) ; because of lemma 2, there is no need to query every point of the starting polygon, but only its vertices.
An important fact used by this algorithm is that a closest point can only be a vertex of the target polygon, or the foot zof a line perpendicular to one of its edges. This fact suggests a function to check for the existence of a possible closest point. Given a source point aand a target edge defined by a point b1 and a vertex b2 :
Function z = CheckForClosePoint (a, b1 , b2 ) :Compute the position zwhere the line that passes through b1 and b2 crosses its perpendicular through a; if zis between b1 b2 then return z; else compute at b2 a line P perpendicular to the line ab2 ; if P is a supporting line of B then return b2 ; else return NULL.
That function obviously uses lemma 1b to decide whether or not the closest point of B might be located on the target edge, that should be close to a. It also supposes that the source point aand b2 are not located on different sides of the perpendicular to [b1b2 ] at b1, accordingly to lemma 3. Now we are ready for the main algorithm ; the vertices of both polygons are presumed to be enumerated counterclockwise :
Algorithm for computing h(A, B) :
1. From a1, find the closest point b1 and compute d1 = d ( a1, b1 ) 2. h(A, B) = d1 3. for each vertex ai of A, 3.1 if ai+1 is to the left of aibi find bi+1 , scanning B counterclockwise with CheckForClosePoint from bi if ai+1 is to the right of aibi find bi+1 , scanning B clockwise with CheckForClosePoint from bi if ai+1 is anywhere on aibi bi+1 = bi 3.2 Compute di+1 = d (ai+1 , bi+1 ) 3.3 h (A, B) = max { h (A, B), di+1 }
3.4 Complexity
If polygons A and B respectively have n and m vertices, then :
Step 1 can clearly be done in O(m) time ;Step 2 takes constant time O(1) ;Step 3 will be executed (n-1) times, that is O(n) ;Step 3.1 will not be executed in totalmore than O(2m). This is a consequence of lemma 3, which guarantees that polygon B can not be scanned more than twice ;Steps 3.2 and 3.3 are done in constant time O(1) ;
So the algorithm for computing h(A, B) takes :
O(m) + O(n) + O(2m) = O(n+m)
To find H(A, B), the algorithm needs to executed twice ; the total complexity for computing Hausdorff distance then stays linear to O(n+m).
3.5 Interactive applet
This applet illustrates the algorithm for computing h(A,B). You only need to draw two polygons, and then press the "step" or "run" button. Left click to define a new vertex, and close the polygon by clicking near the first vertex. Polygon A is the first one you draw, in green, while polygon B appears next, in red. The algorithm was slightly modified to make it more appealing visually. Even if this algorithm is intended for two polygons totally separated from each other, it also works when B is inside A. However, it won"t work if A is inside of B, or when A and B are partially intersecting. You"re allowed anyway to try these cases to see what happens ! When defining your polygons, you will see a yellow area that indicates where you can add the next vertex, so the polygon keeps convex. The applet won"t let you define a non-convex polygon.
Please notice that the first time you draw the second half of a polygon, you will have to wait a few seconds until the Jama package loads.
import java.awt.*;
import java.applet.Applet;
import java.util.Vector;
import java.lang.Math;
import Jama.*;
public class Hausdorff extends Applet
{
PolyArea area;
Panel control;
Button runStop;
boolean running;
TextField comment;
public void init()
{
setLayout (new BorderLayout());
comment = new TextField ("", 60);
comment.setEditable (false);
area = new PolyArea (comment);
add ("Center", area);
control = new Panel();
control.add (new Button ("step"));
runStop = new Button ("run");
control.add (runStop);
control.add (new Button ("reset"));
control.add (comment);
add("South", control);
running = false;
}
public boolean action (Event evt, Object arg)
{
if ("step".equals(arg))
area.stepAlgo();
if ("run".equals(arg))
{
runStop.setLabel ("stop");
startAnim();
running = true;
}
if ("stop".equals(arg))
{
runStop.setLabel ("run");
stopAnim();
running = false;
}
if ("reset".equals(arg))
{
remove (area);
stopAnim();
area = new PolyArea (comment);
add ("Center", area);
runStop.setLabel ("run");
validate();
stopAnim();
running = false;
}
return true;
}
public void start()
{
if (running)
startAnim();
}
public void stop()
{
stopAnim();
}
public void startAnim()
{
if (area.animator == null)
{
area.animator = new Thread (area);
}
area.animator.start();
}
public void stopAnim()
{
area.animator = null;
}
public void paint(Graphics g) {
Dimension d = getSize();
g.setColor (Color.black);
g.drawRect(0,0, d.width - 1, d.height - 1);
}
/* This is used to leave room to the black box painted in
* the paint() method. If we don"t do that, it is overwritten.
*/
public Insets getInsets() {
return new Insets(3,3,3,3);
}
}
//=============================================================================
/*
* The PolyArea class defines an area that will hold our two polygons.
* It will first create them by catching mouse clicks events and adding
* the points to the polygons, and it will then run the algorithm on the
* polygons.
*/
class PolyArea extends Canvas implements Runnable
{
Dimension offDimension;
Image offImage;
Graphics offGraphics;
TextField comment;
public Thread animator;
FConvexPoly poly1, poly2;
int nextStep;
int currentV1;
FPoint bestV1, bestV2, currentV2;
double bestLength;
int currentRegBase;
boolean band;
Polygon currentRegion;
boolean trigo;
public PolyArea (TextField comment)
{
animator = null;
this.comment = comment;
setBackground (Color.white);
poly1 = new FConvexPoly (Color.green);
poly2 = new FConvexPoly (Color.red);
nextStep = -1;
currentV1 = currentRegBase = -1;
bestV1 = bestV2 = currentV2 = null;
band = false;
currentRegion = null;
bestLength = 0;
trigo = true;
comment.setText ("Please enter the first polygon");
comment.setBackground (new Color (220, 255, 230));
comment.setForeground (Color.black);
}
public boolean handleEvent (Event e)
{
switch (e.id)
{
case Event.MOUSE_DOWN:
if (nextStep == -1)
{
if (! poly1.isClosed())
{
poly1.addPoint (new FPoint (e.x, e.y));
if (poly1.isClosed())
{
comment.setText ("Please enter the second polygon");
comment.setBackground (new Color (255, 220, 220));
}
}
else
{
poly2.addPoint (new FPoint (e.x, e.y));
if (poly2.isClosed())
{
comment.setText ("Press step or run to see the algorithm");
comment.setBackground (new Color (255, 255, 220));
nextStep = 0;
}
}
}
repaint();
return true;
default:
return false;
}
}
/* This method performs a step in the algorithm. It is called either
* by the applet when the "step" button is clicked, or by the animator
* thread if this one is running. */
public void stepAlgo ()
{
Point p;
switch (nextStep)
{
case 0:
comment.setText ("Searching for the first vertex");
comment.setBackground (new Color (255, 235, 200));
currentV1 = 0;
currentRegBase = 0;
band = false;
makeRegion();
p = poly1.getPoint (currentV1);
if (currentRegion.inside (p.x, p.y))
nextStep = 2;
else
nextStep = 1;
repaint();
break;
case 1:
if (! band)
band = true;
else
{
currentRegBase++;
band = false;
}
makeRegion();
p = poly1.getPoint (currentV1);
if (currentRegion.inside (p.x, p.y))
nextStep = 2;
else
nextStep = 1;
repaint();
break;
case 2:
comment.setText ("Computing length");
comment.setBackground (new Color (255, 220, 255));
makeV2();
bestV1 = poly1.getFPoint (currentV1);
bestV2 = currentV2;
bestLength = new FVector (bestV1, bestV2).length();
nextStep = 3;
repaint();
break;
case 3:
comment.setText ("Searching for the next vertex");
comment.setBackground (new Color (255, 235, 200));
if (new FVector (currentV2, poly1.getFPoint (currentV1)).isTrigo
(new FVector (currentV2, poly1.getFPoint (currentV1 + 1))))
trigo = true;
else
trigo = false;
currentV1++;
currentV2 = null;
if (poly1.getFPoint (currentV1) == poly1.getFPoint (0))
nextStep = 7;
else
{
p = poly1.getPoint (currentV1);
if (currentRegion.inside (p.x, p.y))
nextStep = 5;
else
nextStep = 4;
}
repaint();
break;
case 4:
if ((trigo || !poly2.isTrigo()) && !(trigo && !poly2.isTrigo()))
if (! band)
band = true;
else
{
currentRegBase++;
band = false;
}
else
if (! band)
{
currentRegBase--;
band = true;
}
else
band = false;
makeRegion();
p = poly1.getPoint (currentV1);
if (currentRegion.inside (p.x, p.y))
nextStep = 5;
else
nextStep = 4;
repaint();
break;
case 5:
comment.setText ("Comparing this length with the previous best");
comment.setBackground (new Color (255, 220, 255));
makeV2();
if (new FVector (poly1.getFPoint (currentV1), currentV2).length() > bestLength)
nextStep = 6;
else
nextStep = 3;
repaint();
break;
case 6:
comment.setText ("This is the new best length");
comment.setBackground (new Color (220, 255, 220));
bestV1 = poly1.getFPoint (currentV1);
bestV2 = currentV2;
bestLength = new FVector (bestV1, bestV2).length();
nextStep = 3;
repaint();
break;
case 7:
comment.setText ("Hausdorff distance from poly 1 to poly 2");
comment.setBackground (new Color (220, 220, 255));
currentV1 = -1;
currentV2 = null;
currentRegion = null;
animator = null;
repaint();
break;
default:
break;
}
}
/* The paint method draws the current state of the algorithm in the
* given Graphics, including the two polygons, the yellow region and
* the important points. */
public void paint (Graphics g)
{
poly1.fill (g);
poly2.fill (g);
if (currentRegion != null)
{
g.setColor (Color.yellow);
g.fillPolygon (currentRegion);
}
poly1.draw (g);
poly2.draw (g);
if (currentV1 >= 0)
{
Point p = poly1.getPoint (currentV1);
g.setColor (Color.blue);
g.drawOval (p.x-5, p.y-5, 10, 10);
}
if (currentV2 != null)
{
Point p1 = poly1.getPoint (currentV1);
Point p2 = currentV2.getPoint();
g.setColor (Color.blue);
g.drawOval (p2.x-5, p2.y-5, 10, 10);
g.setColor (Color.blue);
g.drawLine (p1.x, p1.y, p2.x, p2.y);
}
if (bestV1 != null)
{
Point p1 = bestV1.getPoint();
Point p2 = bestV2.getPoint();
g.setColor (Color.magenta);
g.drawLine (p1.x, p1.y, p2.x, p2.y);
}
}
/* When called by the AWT, the update method clears its offscreen
* buffer, calls paint() to draw in it, and then copies the buffer to the
* screen. */
public void update (Graphics g)
{
Dimension d = size();
if ((offGraphics == null) ||
(d.width != offDimension.width) ||
(d.height != offDimension.height))
{
offDimension = d;
offImage = createImage(d.width, d.height);
offGraphics = offImage.getGraphics();
}
offGraphics.setColor (getBackground());
offGraphics.fillRect (0, 0, d.width, d.height);
paint (offGraphics);
g.drawImage (offImage, 0, 0, this);
}
/* This method is called in the algorithm to make the new
* yellow polygon that corresponds to the sweeping yellow
* region. */
void makeRegion()
{
Polygon region;
FPoint p1, p2;
FVector v1, v2, edge;
p1 = poly2.getFPoint (currentRegBase);
p2 = poly2.getFPoint (currentRegBase + 1);
edge = new FVector (p1, p2);
if (poly2.isTrigo())
v1 = edge.normal().mult(-1);
else
v1 = edge.normal();
if (band)
{
currentRegion = FConvexPoly.infiniteRegion (p1, v1, p2, v1);
}
else
{
p2 = poly2.getFPoint (currentRegBase - 1);
edge = new FVector (p2, p1);
if (poly2.isTrigo())
v2 = edge.normal().mult(-1);
else
v2 = edge.normal();
currentRegion = FConvexPoly.infiniteRegion (p1, v1, p1, v2);
}
}
/* This method creates the new end of the current smallest distance
* that"s on the red polygon. If the current vertex of the green polygon
* is in a yellow sector, it corresponds to the current vertex of the red
* polygon. If it is in a band, it is the foot of the perpendicular to the
* current edge of the red polygon that goes through the vertex. */
void makeV2()
{
if (! band)
currentV2 = poly2.getFPoint (currentRegBase);
else
{
FPoint p1, p2;
FVector vBase;
FLine baseLine, perpendicular;
p1 = poly2.getFPoint (currentRegBase);
p2 = poly2.getFPoint (currentRegBase + 1);
vBase = new FVector (p1, p2);
baseLine = new FLine (p1, vBase);
p2 = poly1.getFPoint (currentV1);
perpendicular = new FLine (p2, vBase.normal());
currentV2 = baseLine.intersect (perpendicular);
}
}
/* The run method is called by the virtual machine to perform the
* automated animation of the algorithm. It calls the stepAlgo() method
* three times per second to animate the algorithme. */
public void run()
{
Thread.currentThread().setPriority(Thread.MIN_PRIORITY);
long startTime = System.currentTimeMillis();
while (Thread.currentThread() == animator)
{
stepAlgo();
try
{
startTime += 300;
Thread.sleep (Math.max (0, startTime-System.currentTimeMillis()));
}
catch (InterruptedException e) { break; }
}
}
}
//=============================================================================
/*
* The FConvexPoly class represents a convex polygon.
*/
class FConvexPoly
{
public Vector v;
boolean closed;
boolean trigo;
Color polyColor;
public FConvexPoly (Color c)
{
v = new Vector();
closed = false;
trigo = false;
polyColor = c;
}
public boolean isClosed ()
{
return closed;
}
public boolean isTrigo ()
{
return trigo;
}
public Point getPoint (int i)
{
return ((FPoint) v.elementAt (MesMath.mod (i, v.size()))).getPoint();
}
public FPoint getFPoint (int i)
{
return (FPoint) v.elementAt (MesMath.mod (i, v.size()));
}
public void addPoint (FPoint p)
{
if (! closed)
{
if (v.size() < 3)
{
v.addElement (p);
if (v.size() == 3)
trigo = firstVector().isTrigo (lastVector());
}
else
{
if (p.equals ((FPoint) v.firstElement()))
closed = true;
else
{
if (isNextOK (p))
v.addElement (p);
}
}
}
}
public boolean isNextOK (FPoint p)
{
FVector next;
next = new FVector ((FPoint) v.firstElement(), p);
if (firstVector().isTrigo (next) != trigo)
return false;
next = new FVector ((FPoint) v.lastElement(), p);
if (lastVector().isTrigo (next) != trigo)
return false;
next = new FVector ((FPoint) v.firstElement(), p);
if (boundVector().isTrigo (next) == trigo)
return false;
else
return true;
}
public FVector firstVector()
{
return new FVector ((FPoint) v.elementAt (0),
(FPoint) v.elementAt (1));
}
public FVector lastVector()
{
return new FVector ((FPoint) v.elementAt (v.size()-2),
(FPoint) v.elementAt (v.size()-1));
}
public FVector boundVector()
{
return new FVector ((FPoint) v.elementAt (v.size()-1),
(FPoint) v.elementAt (0));
}
/* Draw the filled polygon on the given graphics. */
public void fill (Graphics g)
{
Polygon p = new Polygon();
Point pt, pt2;
FPoint fpt;
for (int a=0; a<V.SIZE(); a++)<="" code="">
{
pt = ((FPoint) v.elementAt (a)).getPoint();
p.addPoint (pt.x, pt.y);
}
g.setColor (polyColor);
g.fillPolygon (p);
if (!closed && v.size() >= 3)
{
Polygon nextReg = new Polygon();
if (lastVector().isTrigo (firstVector()) == trigo)
{
pt = ((FPoint) v.firstElement()).getPoint();
pt2 = ((FPoint) v.lastElement()).getPoint();
nextReg.addPoint (pt.x, pt.y);
nextReg.addPoint (pt2.x, pt2.y);
FLine l1 = new FLine ((FPoint) v.firstElement(),
firstVector());
FLine l2 = new FLine ((FPoint) v.lastElement(),
lastVector());
fpt = l1.intersect (l2);
pt = fpt.getPoint();
nextReg.addPoint (pt.x, pt.y);
}
else
{
FVector firstInv = firstVector().mult (-1);
nextReg = infiniteRegion ((FPoint) v.firstElement(),
firstInv,
(FPoint) v.lastElement(),
lastVector());
}
g.setColor (Color.yellow);
g.fillPolygon (nextReg);
}
}
/* Draw the outline of the polygon on the given graphics. */
public void draw (Graphics g)
{
Point pt, pt2;
g.setColor (Color.blue);
if (v.size() > 0)
{
pt = pt2 = ((FPoint) v.firstElement()).getPoint();
for (int a=0; a<V.SIZE()-1; a++)<="" code="">
{
pt2 = ((FPoint) v.elementAt (a+1)).getPoint();
g.drawLine (pt.x, pt.y, pt2.x, pt2.y);
pt = pt2;
}
pt = ((FPoint) v.firstElement()).getPoint();
if (closed)
g.drawLine (pt.x, pt.y, pt2.x, pt2.y);
else
{
g.setColor (Color.red);
g.drawOval (pt.x-5, pt.y-5, 10, 10);
}
}
}
/* This method returns a Polygon that will look infinite when
* drawn by the Graphics methods. This should not be in here, it should
* not be a static method, but it worked so I left it this way...*/
public static Polygon infiniteRegion (FPoint p1, FVector v1, FPoint p2, FVector v2)
{
Polygon p = new Polygon();
Point pt;
double length;
FVector middle;
pt = p1.getPoint();
p.addPoint (pt.x, pt.y);
if (! p1.equals (p2))
{
pt = p2.getPoint();
p.addPoint (pt.x, pt.y);
}
length = v2.length();
pt = new Point ((int) (p2.x + (v2.x / length * 2000)),
(int) (p2.y + (v2.y / length * 2000)));
p.addPoint (pt.x, pt.y);
middle = (v1.mult (1/v1.length())).add (v2.mult (1/v2.length()));
length = middle.length();
pt = new Point ((int) (middle.x + (middle.x / length * 2000)),
(int) (middle.y + (middle.y / length * 2000)));
p.addPoint (pt.x, pt.y);
length = v1.length();
pt = new Point ((int) (p1.x + (v1.x / length * 2000)),
(int) (p1.y + (v1.y / length * 2000)));
p.addPoint (pt.x, pt.y);
return p;
}
}
//=============================================================================
/*
* The FPoint class represents a point in the plane.
*/
class FPoint
{
static double EPSILON = 10;
double x;
double y;
public FPoint (double x, double y)
{
this.x = x;
this.y = y;
}
public FPoint (int x, int y)
{
this.x = (double) x;
this.y = (double) y;
}
public FPoint (Point p)
{
this.x = (double) p.x;
this.y = (double) p.y;
}
public boolean equals (FPoint p)
{
if (new FVector (this, p).length() < EPSILON)
return true;
else
return false;
}
public Point getPoint()
{
return new Point ((int) x, (int) y);
}
}
//=============================================================================
/*
* The FVector class provides a basic 2-dimensional vector type,
* along with some uselful methods.
*/
class FVector
{
double x;
double y;
public FVector (double x, double y)
{
this.x = x;
this.y = y;
}
public FVector (FPoint a, FPoint b)
{
x = b.x - a.x;
y = b.y - a.y;
}
/* Returns the dot product of the vector with v. */
public double dot (FVector v)
{
return x * v.x + y * v.y;
}
/* Returns the vector normal to this vector. */
public FVector normal()
{
return new FVector (-y, x);
}
/* Return true if v makes an angle with the vector in the
* trigonometric direction (a left turn). */
public boolean isTrigo (FVector v)
{
if (dot (v.normal()) <= 0)
return true;
else
return false;
}
public double length()
{
return Math.sqrt (x*x + y*y);
}
public FVector add (FVector v)
{
return new FVector (x + v.x, y + v.y);
}
public FVector mult (double a)
{
return new FVector (x*a, y*a);
}
}
//=============================================================================
/*
* The FLine class represents a line. Here, it is only used to call
* its intersect() method to compute the intersection of two lines.
*/
class FLine
{
/* The line is under the form ax+by=c */
double a;
double b;
double c;
/*
* Creates a new FLine that goes through p and is supported
* by v.
*/
public FLine (FPoint p, FVector v)
{
FVector vn = v.normal();
a = vn.x;
b = vn.y;
c = a * p.x + b * p.y;
}
/* Creates a new FLine that goes through both a and b. */
public FLine (FPoint a, FPoint b)
{
this (a, new FVector (a, b));
}
/*
* The methode computes the intersection point of two
* lines. We use the JAMA matrix package (see
*
* http://math.nist.gov/javanumerics/jama/
* for details).
*/
public FPoint intersect (FLine l)
{
double[][] tabA = {{ a, b},
{l.a, l.b}};
Matrix matA = new Matrix (tabA);
double[][] tabB = {{ c},
{l.c}};
Matrix matB = new Matrix (tabB);
double[][] tabX = (matA.solve (matB)).getArray();
return new FPoint (tabX[0][0], tabX[1][0]);
}
}
//=============================================================================
/*
* The MesMath class is an abstract class that is used to perform
* division related operations on integers. I haven"t been able to tell
* java that I needed my divisions to be rounded toward minus infinity
* rather than zero, so I"ve had to do it myself.
*/
abstract class MesMath
{
public static int div (int a, int b)
{
if (a >= 0)
return a / b;
else
return (a - b + 1) / b;
}
public static int mod (int a, int b)
{
return a - div (a, b) * b;
}
}
标签: 蒙特利尔
相关推荐:
最新新闻:
- 即时看!跨站脚本攻击是一种代码注入攻击
- 快消息!onekeyghost安装器一键还原重装电脑系统
- 当前视点!狄拉克:量子场论的研究方法
- 粒子群算法原理 基于numpy6.2的粒子群算法详解 当前资讯
- 蒙特利尔的麦吉尔大学:计算几何课程资料
- 《黑豹2》明日上映 漫威:接收全方位炸裂视效冲击!
- 经典摔角综合格斗游戏 《周末勇士》登陆steam:全球微速讯
- 什么是驱动程序?驱动程序和光驱有什么区别?
- 10套极好用的PS绘画笔刷工具 简直就是神器
- 优秀的企业绩效考核系统——MVC设计模式
- sqoop导入pg11常见问题及解决方法 热点在线
- java代码实现二分法查找 二分法的实现:每日消息
- 天天视点!如何登录新浪微博html5?新浪微博怎么登陆?
- 天天热门:视频编码中画面质量控制中最重要的部分——DataRate
- 最资讯丨NSM开发总结 NSM项目的技术培训
- matlab软件实验原理 matlab中的图像增强与复原实验_今亮点
- 世界热资讯!【linux系统命令大全】免费使用和自由传播的Unix系统
- 组件化元数据结构设计——PageMaker
- java命令行中的DstRpcServer怎么运行?操作步骤:天天快播报
- 今日播报!视频会员越来越贵 权益却在打折:体系很复杂 充值套路多
- 《如龙 维新!极》新情报:队士能力及编组系统介绍|当前独家
- 杀不死的「去中心化」:每日速读
- 2023年,我们需要怎样的企业家精神:世界快消息
- iPhone 14 Pro全系降价700元:苹果坐不住了
- 2023年中国汽油行业市场供需现状分析 汽油出口金额创历史峰值【组图】_天天快资讯
- 要闻:腾讯成立职业技能培训学校公司 注册资本100万元
- 环球头条:2万元的iPhone上热搜 网友:不是它疯了就是我疯了
- 环球通讯!世嘉发布神秘手游新作先行预告 2月10日正式公布
- 焦点资讯:男子礁石上钓鱼被海浪拍进石缝 垂钓别选偏僻海域
- 生活逃不过科技与狠活:世界视点
- 每日热门:微软Bing已经引入ChatGPT 搜索市场要变天?
- 特斯拉又出事故 高速撞车 每日焦点
- iPhone 14到手4899元 史低价快来捡漏 报道
- 比尔盖茨约马斯克做慈善家:咱们把钱全捐了-环球观天下
- 《阿凡达:水之道》导演卡梅隆diss流媒体:观众需要回到影院去!
- 葛优起诉哔哩哔哩网络侵权:答辩期及举证期满后第3日开庭审理。-世界时讯
- 每日热讯!为什么三体不稳定,我们的太阳系如此稳定?
- RTX4070 Ti比A卡低了60W功耗 4年能省2300多元
- 环球快看:日本政府否认雨宫正佳将接棒央行传闻,日元反弹
- 全球微头条丨生存恐怖游戏《原始预兆》新预告 红发美女打恐龙
- 四川地下皇帝:400亿黑财帝国覆灭记
- 主播说联播丨满目春光,满怀希望,奔向美好!
- 《死亡空间:重制版》暂未打算支持Mod或加入新难度模式-热点
- 路畅科技(002813.SZ)拟增发收购中联高机100%股权开拓高空作业平台业务:环球新资讯
- 全球头条:《卧龙:苍天陨落》新演示 大战魔化武将颜良文丑
- 抒写心情的短句子8个字(实用278句)
- 路痴党福音!《星战绝地:幸存者》有快速旅行
- 天天观速讯丨男子油锅炸元宵现场惨烈 网友:需要穿防护服操作
- 小米预计今年手机出货可达1.65亿部 资本市场看好
- 仍然是美国最畅销的汽车之一!特斯拉MODEL Y在美国涨价超万元:每日观察
- 最资讯丨曝RTX 3060还有新版本:2000出头
- 可运行孤岛危机!国产显卡摩尔线程MTT S80绝了-聚看点
- 苹果新iPhone将没有充电口 取消物理按键 天天时快讯
- 性能炸裂!AMD锐龙7 7840HS测试比R7 6800H快26%_快资讯
- 《黑豹2》豆瓣暴跌至5.8分:特效垃圾 剧情拖沓
- 《地平线》多人游戏可能还会登陆手机和PC|当前要闻
- 当前快报:梁朝伟被郭富城扇耳光!《风再起时》新片段释出
- 世界百事通!装机维修配网络《IT服务公司模拟器》PC版公布
- 通讯!你可以生气,但不要越想越气
- 文明6教程:文明6神级难度怎么玩
- 亚马逊的无人机送达的房屋数量比这个标题中的字数还少
- 新动态:年底促销!索尼PS5季度出货710万
- 精彩看点:南极唯一电车重新设计 因为气候过热
- 每日热点:【手慢无】小米小背包到手39元
- 【手慢无】小米磁吸收纳米家指甲刀五件套仅需39.9元_环球精选
- 支持双人《SD新假面骑士 乱舞》中文版4月27日上市
- Steam新一周销量榜 《霍格沃茨之遗》登顶:天天短讯
- 今日看点:【手慢无】2899!小米平板Book二合一电脑首发
- 国产的会跟进吗?特斯拉在美国提高Model Y价格:涨价近7000元
- 当前简讯:附带散热小风扇亮了!第一款消费级PCIe Gen5 NVMe SSD曝光
- OpenAI强化!微软推出Teams高级版|当前观点
- 世界看热讯:有钱就是可以为所欲为!苹果连续第16年成为“全球最受尊敬的公司”
- 全球快资讯丨提高市占率 高盟新材拟扩产胶粘剂新材料
- 新能源汽车比亚迪,新款车子要来了。而且属于高端车|焦点速看
- 天天观焦点:天气通_关于天气通的基本详情介绍