usaco計算幾何

1、usaco 計算幾何usaco計算幾何2010-05-10 09：09Computational Geometry Prerequisites Graph TheoryShortest PathTools This module discusses several algorithms that calculate various geometric properties,mostly based on only two operations described below：cross product and arctangent.Cross Product The cross product

2、 of uand vis written as ux v.Computationally,the cross product of two three-dimensional vectors uand vis the vector determinant of the following matrix(where i,j,and kare unit vectors in the x,y,and zdirections respectively)：|i jk|ux uy uz|vx vy vz|That equation works out to：(uyvz-vyuz)i+(uzvx-uxvz)

3、j+(uxvy-uyvx)k This definition can be used for vectors in two dimensions by using three-dimensional vectors with az component of 0.The resulting vector will only have az value.The cross product has three properties：The cross product of two vectors is perpendicular to both vectors.The length of the c

4、ross product is equal to the product of：the length of u,the length of v,andthe sine of the angle between the vectors.Of the two different directions that are perpendicular to both uand v,the direction the cross product points depends on whether uisto the rightof vorto the left.Dot product The dot pr

5、oduct of two vectors uand vis ascalar written as uv.Computationally,it is defined in three dimensions as：uxvx+u yvy+uzv zThe dot product is actually equal to the product of：the length of uthe length of vthe cosine of the angle between uand v.Presuming uand vare non-zero,if the dot product if negativ

6、e,u and vmake an angle greater than 90 degrees.If it is zero,then uand vare perpendicular.If ucdot vis positive,then the two vectors form an acute angle.Arctangent The arctangentfunction calculates the(an)angle whose tangent is its argument and generally returns areal number between-pi/2 and pi/2.An

7、 additional function in C,atan2,takes two arguments：a DELTA yvalue and aDELTA xvalue(in that order！).It determines the angle between the given vector and the positive xaxis and returns avalue between-pi and pi.This has the advantage of removing concerns about dividing by zero or writing code to repa

8、ir angles in order to handle the negative xcases.The atan2 function is almost always easier to use than the simpler atan function that takes only one argument.Particular Debugging Problems The main problem with geometric problems is that they spawn alot of special cases.Be on the lookout for these s

9、pecial cases and make sure your program works for all of them.Floating point calculations also create anew set of problems.Floating point calculations are rarely precise,as the computer only maintains so many bits(digits)of accuracy：be aware of this.In particular,when checking if two values are equa

10、l,check to see if they are within some small tolerance of each other not precisely equal.Geometric Algorithms Here are some of snippets that can help you solve geometry problems.Area of Triangle To cal culate the area of atriangle with vertices(a,b,c),pick avertex(say a)and create avector to the oth

11、er two vertices(let u=b-a,and v=c-a).The area of the triangle(a,b,c)is one half the length of cross product ux v.An alternative method to find the area of triangle is to use Heros formula.If the lengths of the sides of atriangle are a,b,and c,let s=(a+b+c)/2.The area of the triangle is then sqrt(s*(

12、s-a)*(s-b)*(s-c).Are Two Line Segments Parallel?To check if two line segments are parallel,create vectors along each line segment and check to see if their cross product is(almost)zero.Area of polygon The area of apolygon with vertices(x 1,y 1),.,(x n,y n)is equal to the determinant：1|x1 x2.xn|-|2|y

13、1 y2.yn|where the determinate is defined to be similar to the 2by 2determinant：x1 y2+x2y3+.+xn y1-y1 x2-y2x3-.-yn x1 Distance from apoint to aline The distance from apoint Pto aline AB is given by the magnitude of the cross product.In particular,d(P,AB)=|(P-A)x(B-A)|/|B-A|.To determine the distance

14、from apoint Pto the plane defined by A,B,and C,let n=(B-A)x(C-A).The distance is then give by the following equation：d(P,ABC)=(P-A)n/|n|.Points on aline Apoint is on aline if the distance from the point to the line is 0.Points on the same side of line This notion only makes sense for two dimensions.

15、To check if points Cand Dare on the same side of line AB,calculate the zcomponent of(B-A)x(C-A)and(B-A)x(D-A).If the zcomponents have the same sign(i.e.,their product is positive),then Cand Dare on the same side of the line AB.Point on line segment To calculate if apoint Cis on the line segment AB,c

16、heck if Cis on the line AB.If it is,then check if the length of AB is equal to the sum of the lengths of AC and CB.Point in triangle To check if apoint Ais in atriangle,find another point Bwhich is within the triangle(the average of the three vertices works well).Then,check if the point Ais on the s

17、ame side of the three lines defined by the edges of the triangle as B.Point in convex polygon The same trick works for aconvex polygon：Four(or more)points are coplanar To determine if acollection of points is coplanar,select three points,A,B,and C.Now,if,for any other point D,(B-A)x(C-A)(D-A)=0,then

18、 the collection of points resides in some plane.Two lines intersect Two lines intersect if and only if they are not parallel in two dimensions.In three dimensions,two lines AB and CD intersect if they are not parallel and A,B,C,and Dare coplanar.Two line segments intersect In two dimensions,two line

19、 segments AB and CD intersect if and only if Aand Bare on opposite sides of the line CD and Cand Dare on opposite sides of line AB.Note that both of the checks are necessary,as for the last case one of the checks returns true,while the other testifies to the fact that AB and CD do not intersect.In t

20、hree dimensions,solve following system of equations,where iand jare the unknowns：Ax+(Bx-Ax)i=Cx+(Dx-Cx)j Ay+(By-Ay)i=Cy+(Dy-Cy)j Az+(Bz-Az)i=Cz+(Dz-Cz)j If this system has asolution(i,j),where 0=i=1 and 0=j=1,then the line segments intersect at：(Ax+(Bx-Ax)i,Ay+(By-Ay)i,Az+(Bz-Az)i.Point of Intersect

21、ion of Two Lines For the lines AB and CD in two dimensions,the most straight-forward way to calculate the intersection of them is to solve the system of two equations and two unknowns：Ax+(Bx-Ax)i=Cx+(Dx-Cx)j Ay+(By-Ay)i=Cy+(Dy-Cy)jThe point of intersection is：(Ax+(Bx-Ax)i,Ay+(By-Ay)i)In three dimens

22、ions,solve the same system of equations as was used to check line intersection,and the point of intersection is：(Ax+(Bx-Ax)i,Ay+(By-Ay)i,Az+(Bz-Az)i)Checking convexity of 2-dimensional polygon To check the convexity of a2-dimensional polygon,walk the polygon in clock-wise order.For each triplet of c

23、onsecutive points(A,B,C),calculate the cross product(B-A)x(C-A).If the zcomponent of each of these vectors is positive,the polygon is convex.Point in non-convex polygon To calculate if apoint is within anonconvex polygon,make aray from that point in arandom direction and count the number of times it

24、 intersects the polygon.If the ray intersects the polygon at avertex or along an edge,pick anew direction.Otherwise,the point is within the polygon if and only if th eray intersects the polygon an odd number of times.This method also extends to three dimensions(and higher),but the restriction on int

25、ersection is that it only intersects at faces and not at either avertex or an edge.Geometry Methodologies Geometric problems introduce several different tricks that can be used to either reduce the run-time or approximate the solution.Monte Carlo The first geometric trick is based on randomness.Inst

26、ead of calculating the probability that something occurs,simulate arandom event and calculate the fraction of times it occurs.If enough events are simulated,the difference between these two values becomes very small.This can be helpful to determine something like the area of afigure.Instead of calcu

27、lating the area directly,determine abounding box,and throwdartsat the box,and estimate what the probability of hitting the figure is.If this is calculated accurately enough,this can give agood estimate of the actual area.The problem with this method is to get agood relative error(error divided by th

28、e actual value)requires alarge number of successful events.If the probability of the event occurring is very small,the method does not yield good results.Partitioning Partitioning is amethod to improve the speed of ageometric algorithm.This entails dividing the plane up into sections(usually by agri

29、d but sometimes into radial sections or some other method),and bucketing the objects into appropriate section(s).When looking for objects within some figure,only those sections which have anon-zero intersection with that figure need to be examined,thereby greatly reducing the cost of the algorithm.T

30、his is helpful to determine the set of objects within some distance of agiven point(the figure is acircle)or to check for intersections(the figure is aline).Graph Problems Sometimes what may look like ageometric problem is really agraph problem.Just because the input is points in the plane does not

31、mean its ageometric algorithm.Example Problems Poi nt Moving Given aset of line segments in the plane,and two points Aand B,is it possible to move from Ato Bwithout crossing any of the segments?The line segments partition the plane into regions.Determine these regions,and see if Aand Breside in the

32、same region.Bicycle Routing Given acollection of non-intersecting buildings along with start and end locations,find the shortest path from Ato Bthat doesnt go through any buildings.Analysis：This is really agraph problem.The nodes are the start and end locations,along with the vertices of the buildin

33、gs.There are edges between any two nodes such that the line segment between them does not intersect any buildings,with weight equal to the length of the length of the line segments.Once that graph has been calculated,the problem is shortest path.Maximizing Line Intersections Given acollection of seg

34、ments in the plane,find the greatest number of segments which can by intersected by drawing asingle line.Analysis：With alittle bit of thought,it is clear that the line segment must pass through two of the vertices of the collection of line segments.Thus,try all pairs of vertices,and cal culate the c

35、rossing for each.Combining this with partitioning gives an algorithm that runs fairly quickly.Polygon Classification Given acollection of segments defining apolygon,determine if it is simple(no two non-consecutive line segments intersect)and convex.計算機應用中的解析幾何譯by zhougu學習該內(nèi)容的基礎*圖論問題*最短路徑問題工具這個模塊論述了一

36、些具有幾何特性的多方面做計劃的算法，而這些算法大多都建立在以下的兩個概念的基礎上：向量乘積和反正切。向量的乘積：向量u和v的乘積被記做u xv。而對于計算機程序來說，兩個三維空間內(nèi)的向量u和的積是決定于下面的這個矩陣。(i，j，k是單位向量，而x，y，z分別是它們的方向)|i jk|ux uy uz|vx vy vz|可以通過這個方程計算出：(uyvz-vyu z)i+(uzvx-u xvz)j+(uxvy-uvx)k這個方法完全可以被用在二維的空間內(nèi)，那時我們認為z=0，自然結(jié)果向量中的z也為0。向量的乘法有三個性質(zhì)：*兩個向量的積在空間范圍內(nèi)同時垂直于這兩個向量。*向量u和v的積的長度等于

37、向量u的長度、向量v的長度和兩向量夾角的正弦值的乘積。*在兩個可能出現(xiàn)的方向中，向量u和向量v的積的方向取決于u和v的位置關系。向量的數(shù)量積：向量u和向量v的數(shù)量積記做u?v，用與剛才類似的方程表示為：u xvx+u yvy+u zvz而事實上我們可以用標量u的長度、v標量的長度和兩向量夾角的余弦值的乘積來表示向量u和向量v的數(shù)量積。如果向量u和向量v的夾角大于90度，而u和v都是非0的，那么它們的數(shù)量積是負數(shù)。如果它們的數(shù)量積等于0，那么它們是互相垂直的。如果u?v的結(jié)果是正數(shù)，那么它們夾的是一個銳角。反正切：反正切作為函數(shù)通?？梢酝ㄟ^正切值計算出一個處在-Pi/2到Pi/2之間的角的度數(shù)。

38、C語言中額外的atan2函數(shù)帶有兩個引數(shù)：DELTA y的值和DELTA x的值。它會測定所給向量與x軸的夾角并返回一個處在-Pi/2到Pi/2之間的角度。它的好處就在于消去了涉及到0做被除數(shù)和為處理多種角度情況時所寫的代碼。大多時候，函數(shù)atan2要比只帶有一個引數(shù)的函數(shù)atan簡單。特殊的調(diào)試問題：解決幾何問題時最主要是問題是它們往往有很多特殊情況，所以要確認你的程序可以應付所有的特殊情況。浮點數(shù)據(jù)的計算總會產(chǎn)生一系列的問題。浮點數(shù)據(jù)的計算很少是100%精確的，因為電腦本身也只能維持一定位數(shù)的準確度。尤其是判斷兩個值是否相等時，電腦只是看它們的差是否在一個很小的容差值的范圍內(nèi)。幾何算法：以

39、下是幾個可以幫助我們解決幾何問題的資料。三角形區(qū)域：計算一個頂點為(a,b,c)的三角形所在的區(qū)域，要先選擇一個頂點(比如頂點a)，并創(chuàng)建兩個與另外三角形的三邊有如下關系的向量：使向量u=b-a，向量v=c-a。三角形a、b、c的區(qū)域就是向量u和向量v的乘積的1.5倍。還有一個求三角形區(qū)域可以選擇的方法是用hero定理。如果三角形三邊的長度分別為a、b、c，設s=(a+b+c)/2，這個三角形的區(qū)域就等于：sqrt(s*(s-a)*(s-b)*(s-c)兩條線段是否平行：檢驗兩條線段是否平行，可以沿著兩條線段的方向創(chuàng)建兩個向量，然后看它們的乘積是否為0。多邊形區(qū)域：一個頂點為(x 1,y 1)

40、,.,(x n,y n)的多邊形的區(qū)域等于下面這個行列式。1|x1 x2.xn|-|2|y1 y2.yn|這個行列陣的算法類似于2 X2的行列陣：x1 y2+x2y3+.+xn y1-y1 x2-y2x3-.-yn x1。點到直線的距離：值得注意的是點P到直線AB的距離往往是由向量乘積量得出的：d(P,AB)=|(P-A)x(B-A)|/|B-A|。要決定點P到A、B、C三點所在的平面的距離，需先設n=(B-A)x(C-A)，然后用這個公式來計算：d(P,ABC)=(P-A)?n/|n|。在直線上的點：在直線上的點到直線的距離為0。在直線同側(cè)的點：這個想法只對二維的空間有意義。要檢驗點C和點D

41、是否在直線AB同側(cè)，只需計算(B-A)x(C-A)和(B-A)x(D-A)的值。如果它們同號，C和D就在直線AB的同側(cè)。三角形內(nèi)的點：檢驗點A是否在三角形內(nèi)部，我們可以先在三角形內(nèi)部找一個點B(三個頂點的平均值即可)。然后檢驗A相對三邊是否都在B的同側(cè)。凸多邊形內(nèi)的點：這和三角形是同樣的做法。多個(四個以上)點共面：要判斷一系列點是否共面，我們可以先選擇三個點A、B、C，它們必然是共面的，在任意挑選一點D，如果(B-A)x(C-A)?(D-A)=0，則這個點與點A、B、C在一個平面內(nèi)。兩線段相交：在二維空間內(nèi)，兩條線段AB和CD相交，如果A、B分別在線段CD的兩側(cè)而且C、D分別在線段AB的兩側(cè)。把這兩個核對全記錄下來往往是不必要的，如果其中一個的核對證明AB和CD是不相交的就返回false并結(jié)束核對。在三維空間內(nèi)，利用以下的等式(i,j不是已知的)：Ax+(Bx-Ax)i=Cx+(Dx-Cx)j Ay+(By-Ay)i=Cy+(Dy-Cy)j Az+(Bz-Az)i=Cz+(Dz-Cz)j如果已知了(i,j)，且i、j在0和1之間，那么兩線段相交于(Ax+(Bx-Ax)i,Ay+(By-Ay)i,Az+(Bz-Az)i。兩條直線交點：要計算二維空間內(nèi)的兩直線AB、CD的交點，最容易