doublelinePointDist(int[] A,int[] B,int[] C, boolean isSegment){doubledist = cross(A,B,C) / distance(A,B); //<-can be computed just before returnif(isSegment){intdot1 = dot(A,B,C);if(dot1 > 0)returndistance(B,C);intdot2 = dot(B,A,C);if(dot2 > 0)returndistance(A,C); }returnabs(dist); }

It's easy to see that "dist" might not need to be computed if "isSegment" is true and C point is not projected inside AB(another intepretation of dot1 > 0 || dot2 > 0), so

Optimization 1:

doublelinePointDist(int[] A,int[] B,int[] C, boolean isSegment){if(isSegment){intdot1 = dot(A,B,C);if(dot1 > 0)returndistance(B,C);intdot2 = dot(B,A,C);if(dot2 > 0)returndistance(A,C); }doubledist = cross(A,B,C) / distance(A,B); //<-here is betterreturnabs(dist); }

Another optimization, if you somehow skipped the previous observation (:P ) is to realise due to the properties of the dot product being a projection of 2d to 1d space on the vector that the segment AB is on, that if dot1 < - distance(A,B), the projection is outside the AB segment on its line.

Optimization 2

doublelinePointDist(int[] A,int[] B,int[] C, boolean isSegment){doubledistAB = distance(A,B); //new variable, save this might need it laterdoubledist = cross(A,B,C) / distAB;if(isSegment){intdot1 = dot(A,B,C);if(dot1 > 0)returndistance(B,C);elseif(dot1 < -distAB )returndistance(A,C); }returnabs(dist); }

Of course, optimization 2 makes sense only if you skipped optimization 1, as sqrt() function used in distance() is more expensive than the additional dotProduct call that you save.]]>

Does anyone know a better introduction to geometry topics for those 10+ years out of school never touching anything besides +-/* since school?]]>

Both answers are correct. The reason vector arithmetic is usually preferred in computer science is because of internals of trigonometry function (sin, cos, tan, etc.) implementations. First, these functions are slow. Then, using them to calculate things like line-point distance leads to less precise results. This is very important when it comes to determining things like "less than 0 degrees", "greater than 90 degrees" and so on. Especially when we deal with integer-valued coordinates.

Last but not least is that when using vector arithmetic, the corner case amount is usually reduced compared to trigonometry formulas.

To sum it up, when you have relatively high amount of time for calculations, and the coordinates are floating-point values, and allowed error tolerance is big enough (like 10E-5), you are free to use trigonometry. In other cases, do think twice before you do so. For example, I personally try to use vector arithmetic in Marathon Match contests whenever possible.]]>

The tutorial says...

"First, check to see if the nearest point on the line AB is beyond B (as in the example above) by taking AB Ã¢ÂÂ BC. If this value is greater than 0, it means that the angle between AB and BC is between -90 and 90, exclusive, and therefore the nearest point on the segment AB will be B"

But how come it isn't...

"If this value is greater than 0, it means that the angle between AB and BC is between -90 and 90, exclusive, and

So what I'm thinking is, if the angle between AB and BC, theta, is between 0 and 90, then cos(theta) is positive, then the nearest point to C should lie within the segment AB. In this case, we can drop a perpendicular from C to AB and calculate its length with dot_product(AC, AB) / abs(AB). Otherwise, if theta is greater than 90 degrees (but less than 270) then cos(theta) is negative and so C lies beyond line segment AB, therefore, the closest point must be one of the endpoints A or B and the distance we're looking for the length of line segment AC or BC.

I'm unfamiliar with vector arithmetic but I know high school trigonometry. Does anyone know what the right answer here is :c?]]>