环球新动态:蒙特利尔的麦吉尔大学:计算几何课程资料
蒙特利尔的麦吉尔大学的计算几何课程资料:
(资料图片)
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;
}
}
标签: 蒙特利尔
精彩放送:
- []环球新动态:蒙特利尔的麦吉尔大学:计算几何课程资料
- []全球速讯:视频编码中画面质量控制中最重要的部分——DataRate
- []粒子群算法原理 基于numpy6.2的粒子群算法详解
- []世界热议:NSM开发总结 NSM项目的技术培训
- []世界讯息:什么是驱动程序?驱动程序和光驱有什么区别?
- []今日播报!三星i458怎么样?报价多少?三星i458市场报价及测评
- []当前最新:mac卡巴斯基激活码怎么用?免费领取教程来了
- []【天天时快讯】神州行幸福卡是什么?神州行幸福卡详情介绍
- []天天观热点:华侨城西部投资挂牌剑门关华侨城旅游公司2亿股股份 底价4.75亿元
- []环球快消息!美高梅国际酒店集团2022年度收益净额6.74亿美元 同比减少44%
- []女演员长相有多重要?看《我们的日子》里李小冉和齐欢就知道了
- []美物科技(WNW.US)收到纳斯达克股价不合规通知
- []观速讯丨社保基数1万多什么水平(社保基数8000是什么档次)
- []信用卡2万额度算高吗(信用卡2万额度算高吗)
- []天天通讯!交强险9月19日新规
- []焦点速递!港财政司副司长黄伟纶对香港保持国际金融中心地位充满信心?
- []环球快看:哈工智能重组预案出炉 拟收购宜春锂企切入新能源业务
- []微速讯:2020年车险保费新政策
- []环球新消息丨出险一次第二年保费怎么算2020
- []天天资讯:关于春天的味道作文600字汇总5篇
- []江苏自贸区板块2月8日跌1.42%,连云港领跌,主力资金净流出9927.05万元
- []微信昵称妇女简单大方 女人简单大方的微信网名汇总
- []2022教师节手抄报简单好看字少
- []观焦点:鄂台青年武当文化研学营开营
- []当前速读:有房贷的房子可以拍卖吗?(房贷没还完可以拍卖吗)
- []全球快看点丨单位为什么不给员工上生育险(单位不给男职工交生育险)
- []贝因美大股东权益再现变动 4.44%持股签署表决权委托协议
- []环球快消息!交通信用卡改还款日期怎么改(交通信用卡怎么改还款日期)
- []全球微头条丨营业外支出和管理费用的区别(营业外支出和管理费用的区别)
- []头条焦点:中际旭创:2月7日公司高管王军减持公司股份合计10000股
- []天天简讯:澄天伟业:2月7日公司高管景在军减持公司股份合计14万股
- []环球今日讯!南网能源:截至2023年1月31日,公司合并普通账户和融资融券信用账户的持有人数为156,602
- []速讯:北京2023年首场土拍收官:央国企仍是主角,越秀“再北上”59亿元拿下两宗
- []世界热议:中建智地17.2亿元底价拍得北京房山良乡大学城地块
- []观察:科拓生物:2月7日公司高管刘晓军减持公司股份合计8万股
- []游族网络(002174)股东林漓、林芮璟、林小溪合计质押5494.94万股,占总股本6%
- []电饭锅做面包的方法
- []焦点播报:合肥泰康人寿保险公司怎么样(合肥泰康人寿保险公司怎么样)
- []环球热资讯!谢杨春等:优质供应带动,杭州土拍迎“小阳春”
- []世界观焦点:越秀2023开年狂飙北京,59亿激进补仓,石景山死磕中海
- []半数地块溢价成交 北京第五批集中供地收官
- []大元泵业:2月6日公司高管崔朴乐减持公司股份合计2万股
- []每日头条!山西太原:公积金贷款首房首付比例为20%
- []璞泰来:2月8日公司高管陈卫增持公司股份合计9.25万股
- []越秀以33.12亿元+4.5万平现房销售面积竞得北京昌平回龙观地块
- []天马科技:2月7日公司高管何腾飞、曾丽莉增持公司股份合计3.52万股
- []当前头条:力合科技:公司主营业务为环境监测系统研发、生产和销售及运营服务
- []天天短讯!和医保卡绑定的银行卡丢了怎么办理(和医保卡绑定的银行卡丢了怎么办)
- []最资讯丨青岛东李世园板块万竹云峰项目再流拍 底价已降至3.56亿
- []厦门钨业等三方加强战略合作 推进大湖塘钨矿开发
- []世界观焦点:华侨城调整“18侨城06”票面利率至1.5% 并开启回售
- []捷安高科:公司暂未涉及ChatGPT的产品和技术
- []快看:外地人在长沙买房怎么交社保(外地人怎么在长沙买房)
- []世界快看点丨职工医保补缴会返还吗(补缴医保有返钱吗)
- []免费安全工作总结(优选9篇)
- []全球热点!“20荣盛地产MTN002”持有人会议通过变更债券本息兑付安排等议案
- []重点聚焦!深圳重启积分入户 专家预计未来住房需求会明显增加
- []全球快讯:华大九天:公司主要从事EDA工具软件的开发、销售及相关服务
- []茂业商业子公司与关联方签合计700万元物业服务协议
- []杭州网络零售额首次突破万亿 直播相关企业注册量全国第一
- []环球关注:红星美凯龙为常州子公司7.07亿债务提供担保
- []全球信息:中电兴发:公司作为智慧城市全面解决方案提供商和运营服务商,被纳入深证人工智能(AI)50指数
- []【全球独家】志特新材:公司的定期报告会对股东总人数进行披露,届时请关注披露公告
- []今日热搜:医保卡不在红名单怎么解决(医保卡黑名单如何补救)
- []信用卡第一次还款日期怎么算的(信用卡还款日怎么算年限)
- []全球热资讯!用京医通挂号医保卡还能报销吗(京医通绑定社保卡能不能报销住院)
- []全球头条:多少人的信用卡额度达到30万以上(多少人的信用卡额度达到30万)
- []全球百事通!新地NOVO LAND 2B期最快下星期上载楼书
- []观察:石嘴山新型冠状病毒肺炎疫情:2月8日石嘴山疫情最新消息今天数据统计情况通报
- []环球热文:双杰电气: “东数西算”工程是国家重点发展战略之一,也会用到12kV的配电设备
- []百盛商业确认租赁四川绵阳科技城新区物业 用作经营购物中心等
- []需要进一步核实及完善 海航投资延期回复深交所关注函
- []新湖中宝:控股股东之一致行动人900万股解除质押
- []世界热消息:中国银河:公司坚持服务国家战略、服务中小微企业与提高业务核心竞争力相结合
- []【环球快播报】博世科:(1)公司暂无微生物燃料电池相关领域的规划
- []奋达科技:公司与首航签署了战略合作协议,具体请参考以往公告
- []天天快报!多晶硅价格上涨!
- []全球最资讯丨数字信号处理技术论文
- []四连涨!硅料最高价至249元/kg
- []环球视讯!海量项目信息!光伏行业最新报告出炉
- []当前热讯:再下一城!越秀以33.12亿+现房销售4.5万平竞得昌平信息园二期地块
- []新动态:西方制裁打击俄罗斯石油收入的背后:巨额利润究竟流向了哪?
- []全球焦点!2月8日豪鹏科技涨停分析:锂电池,动力电池回收,新能源汽车概念热股
- []环球时讯:建发股份申请发行不超过45亿元公司债 获发改委同意注册
- []2月8日真视通涨停分析:应急产业,东数西算,军民融合概念热股
- []世界快报:温州城建30亿私募债项目状态更新为“已受理”
- []短讯!哈药股份:道圣康膜不是本公司生产的产品,黑龙江大众安泰药业有限公司不是本公司的下属企业
- []湖州安吉6宗地均以底价成交 两山国有控股6.58亿连拿2宗
- []“老撕鸡防骗”挂羊头卖狗肉,误导投资客户,30亿客户资金打水漂
- []2月8日新纶新材涨停分析:固态电池,锂电池,宁德时代概念股概念热股
- []全球热头条丨2月8日鸿博股份涨停分析:包装印刷,小家电,体育产业概念热股
- []天天微动态丨中原:一手私楼开放式及一房货尾量比例共占逾三成
- []如何简单的自制黑椒牛排?自制黑椒牛排的方法步骤?
- []腾讯开心鼠英语是腾讯旗下吗?腾讯开心鼠英语介绍
- []天天要闻:左立熊小玥还在一起吗?左立个人资料介绍?
- []环球播报:博大考神职称计算机软件破解版,博大考神职称计算机考试
- []当前头条:诗曼芬是几线品牌?诗曼芬品牌资料介绍?
- []绵阳美食有哪些?绵阳美食分享?
- []世界即时看!网易smtp的25端口可以使用ssl端口?操作步骤
- []世界看点:深圳杨梅坑在哪里?杨梅坑好不好玩?
- B站注册资本增幅400%至5亿 目前由陈睿全资持股
- 光源资本出任独家财务顾问 沐曦集成电路10亿元A轮融资宣告完成
- 巨轮智能2021年上半年营收11.24亿元 期内研发费用投入增长19.05%
- 红枣期货尾盘拉升大涨近6% 目前红枣市场总库存约30万吨
- 嘉银金科发布2021年Q2财报 期内净利润达1.27亿元同比增长208%
- 成都银行2021上半年净利33.89亿元 期内实现营收同比增长17.27亿元
- 汽车之家发布2021年第二季度业绩 期内新能源汽车品牌收入增长238%
- 中信银行上半年实现净利润290.31亿元 期末不良贷款余额706.82亿元
- 光伏概念掀起涨停潮交易价格创新高 全天成交额达1.29亿元
- 上半年生物药大增45% 关键财务指标好转营收账款持续下降
- 环球即时:elasticsearch怎么安装插件?elasticsearch拼音分词插件安装教程
- 资讯推荐:周杰伦演武神的一部电影叫什么名字?讲述了什么剧情?
- 从虚拟化安全到容器安全:Docker容器的安全机制与解决方案
- 快报:陋室铭作者是谁?陋室铭作者资料介绍?
- 天天精选!mysql设计总结 基于mysql的bbs设计总结
- 含有狗的谚语有哪些?含有狗的谚语汇总?
- 骆驼精神是什么样的精神?骆驼精神介绍?
- 全球热门:12306抢票网站靠谱吗?火车票候补购票概率有多大?
- 天天新动态:什么贷款能贷10年以上(有什么贷款能贷五年)
- 全球今头条!携程:年后跨境航班“量升价跌”,海外酒店错峰均价降一成
- 每日关注!艾莉森洛曼为什么不火?瑶瑶来为您解答
- 环球动态:货拉拉推出同城门到门跑腿服务 预计4月正式开放服务和骑手接单
- 上海浦东香楠路城市经典会所二次拍卖流拍 当前价1.08亿元
- 每日短讯:香港“高才通计划”接获7417宗申请 其中5799宗获批
- 焦点观察:c盘临时文件可以清理吗?c盘临时文件可以删除
- 【全球新要闻】卫生整顿工作总结(通用31篇)
- 豫能控股:公司指定的信息披露媒体有《证券时报》《上海证券报》和巨潮资讯网,相关费用以合同签订为准
- 多普达830怎么样?多普达830手机报价及性能配置介绍
- visit怎么读的?will和visit读音相同吗?
- 全球滚动:《从结婚开始恋爱》什么时候播出?从结婚开始恋爱演员表
- 当前简讯:福州高新投资1.09亿元摘闽侯一宗宅地 将建设拆迁安置房项目
- 快看点丨华为y320怎么样?华为y320报价及简评分享
- 今日热闻!西安空调移机哪家好?西安空调移机厂家技术信得过
- 焦点精选!win10怎么彻底清除win32trojan病毒?win32 trojan病毒清除教程
- 全球看点:尼康镜头标识的含义是什么?详情介绍
- 江河集团:公司在海外的业务主要集中在东南亚地区,暂无在中东地区开展业务的计划
- 全球最资讯丨春秋航空启动大规模线下招聘
- 热点在线丨【linux系统命令大全】免费使用和自由传播的Unix系统
- matlab软件实验原理 matlab中的图像增强与复原实验
- 社保基数忘记申报,基数自动上调了怎么回事(公积金基数上调了社保基数没调)
- 环球今日报丨皇家加勒比:2022年Q4营收26亿美元,净亏损5亿美元
- 世界观焦点:java代码实现二分法查找 二分法的实现
- 世界关注:北京社保外埠农村劳动力(社保为外埠农村劳动力是什么意思)
- 【环球新要闻】Waze将很快获得Android Auto最酷的新功能之一
- 最新消息:狄拉克:量子场论的研究方法
- 环球速读:10套极好用的PS绘画笔刷工具 简直就是神器
- 环球关注:越秀地产以25.99亿竞得石景山苹果园地块 配建1.5万平方米现房
- 世界短讯!京山轻机:如公司与其他公司发生达到信息披露标准的重大合作项目,公司将按规定及时履行信息披露义务
- 快讯:拉萨城建投资30亿元私募债项目状态更新为“已反馈”
- 全球快资讯:丹化科技:公司目前没有这方面的计划
- 全球热讯:房企融资分化:有国企两月授信超千亿,出险企业盼借新还旧应对偿债高峰
- 华联控股:华联南山A区更新项目有关申请报批工作在推进中
- 当前关注:深圳安托山新业花园动工 将提供226套保障性住房
- 环球热点评!*ST日海:上述资产转让的会计影响会体现在2022年年度报告中
- 信息:抖音在杭州成立无限能量房产经纪公司 注册资本150万
- 当前视讯!支付宝免费保单啥意思(支付宝免费领保单可以领吗)
- 徽商银行怎么交个人社保(我的社保是在安徽合肥徽商银行交的,怎样转到天津社保交费)
- 【全球报资讯】“19泰达01”回售数量234.49万手 回售金额23.45亿元
- 环球快资讯:新华制药:公司是全球主要解热镇痛等类药物供应商,与众多制剂生产企业均有业务往来
- 最新资讯:住建部等:启动公共领域车辆全面电动化先行区试点
- 美的置业10.2亿元公司债将于2月13日提前摘牌 利率4.4%
- 商汤-W跌超4% 此前遭软银集团减持近3亿股
- 世界聚焦:江西:落实16条金融措施 有效防范化解优质头部房企风险
- 当前头条:养乌龟的缸图片大全_养乌龟的缸
- 全球今头条!声迅股份:公司高度关注ChatGPT相关的行业化应用,也在探索ChatGPT与公司业务的结合点
- 动态:全城高考的观后感
- 精彩看点:海得控制:公司在系统解决方案业务中会涉及百度相关技术与产品的应用
- 咨询公司报告:中国旅游业复苏路径评估
- 超过退休年龄可以补交养老金吗(超过退休年龄可以补交养老金吗?)
- 【全球播资讯】降低存量房贷利率,可行吗?
- 世界最资讯丨金科地产:累计完成 285.77 亿元有息负债的展期工作
- 广东发改委:推动国家出台金融支持横琴粤澳深度合作区建设政策
- 最资讯丨首进北京!中建东孚14.26亿元竞得北京朝阳区小红门地块
- 环球快报:广东省发改委:力争横琴粤澳深度合作区年内“封关运作”
- 【全球独家】实益达:公司暂无chatgpt相关技术。关于公司具体业务内容详见公司披露的定期报告
- 【BT金融分析师】丰田重心偏向混动车型,分析师称其没全部押注电动汽车
- 前沿热点:华夏银行信用卡账单日和还款日(华夏银行信用卡账单日和还款日)
- 【世界播资讯】万达商管成功发行3亿美元债,消息称有望二季度重返港股
- 环球观天下!越秀以25.99亿元+1.5万平现房销售面积竞得北京石景山1宗地块
- 环球快资讯:奥普光电:公司主营业务为光电测控仪器设备、光学材料和光栅编码器等产品的研发、生产和销售
- 中泰证券:强预期与弱现实的博弈 关注低PB房企及央企地产附属物业公司
- 【全球速看料】富力地产欠税金额超千万
- 当前快讯:江阴银行:财务总监亲属因误操作导致买卖公司股票构成短线交易
- 深南电路:公司在保障正常生产经营和项目建设资金需要的同时,持续加强资金的统筹管理,实现资金的高效利用
- 银河证券:房地产基本面仍在筑底 集中供地规则优化
- 环球微头条丨生源地助学贷款可以异地办理吗(生源地助学贷款可以异地办理吗)
- 爆冷!亚冠冠军3-2淘汰南美冠军进世俱杯决赛 或与皇马争冠
- 天天头条:英大人寿内勤怎么样(英大人寿内勤好不好干)
- 如何训练抗干扰能力?训练抗干扰能力的方法步骤?
- 每日快播:狼和小羊的作者是谁?狼和小羊是出自哪里?
- 天天时讯:《横琴粤澳深度合作区发展促进条例》公布 自3月1日起施行
- 【东海期货2月8日产业链日报】能化篇:中国需求信心增强,油价大幅上涨
- 天天热头条丨润华生活服务全球发售的稳定价格期于2月8日结束
- 头条焦点:hm是什么牌子的衣服?HM是什么的简称?
- 环球滚动:国信期货早评:原油高涨,国际油脂震荡走高,原糖走升
- 每日热讯!羟脯氨酸怎么测定?羟脯氨酸的测定方法?
- 快播:中信建投期货2月8日早间交易策略
- 华光环能:预计占推广项目收入的比例不到5%,相关涉及信息属于商业性保密信息,不便于披露
- 带一毛字的成语有多少?带一毛字的成语汇总?
- 【独家焦点】什么叫甲基化?甲基化是指什么?
- 世界看热讯:传无锡首房首贷利率将降至3.8%!
- 头条:富贵竹怎么养殖?富贵竹的养殖方法是什么?
- 血红蛋白正常值是多少_血红
- 当前速讯:xwd四轮驱动是什么?xwd四轮驱动配置怎么样?
- 天天亮点!中国新城镇领涨港股内房股 A股地产板块早盘走强
- 天天即时看!北京涨价业主越来越多
- 【世界速看料】春日宴主演都有谁?春日宴讲述了什么故事?
- 环球观点:中交地产:截止1月20日收盘的股东人数为68029
- 全球滚动:云南省的简称是什么?云南省的面积有多大?
- 焦点热议:【东海期货2月8日产业链日报】贵金属篇:鲍威尔发言偏鹰,金银震荡