Code:
/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / wpf / src / Core / CSharp / MS / Internal / Ink / StrokeNodeOperations2.cs / 1 / StrokeNodeOperations2.cs
//------------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//-----------------------------------------------------------------------
using System;
using System.Collections.Generic;
using System.Windows;
using System.Windows.Media;
using System.Windows.Input;
namespace MS.Internal.Ink
{
///
/// Static methods implementing generic hit-testing operations
///
internal partial class StrokeNodeOperations
{
#region enum HitResult
/// A set of possible results frequently used in StrokeNodeOperations and derived classes
internal enum HitResult
{
Hit,
Left,
Right,
InFront,
Behind
}
#endregion
#region HitTestXxxYyy
///
/// Hit-tests a linear segment against a convex polygon.
///
/// Vertices of the polygon (in clockwise order)
/// an end point of the hitting segment
/// an end point of the hitting segment
/// true if hit; false otherwise
internal static bool HitTestPolygonSegment(Vector[] vertices, Vector hitBegin, Vector hitEnd)
{
System.Diagnostics.Debug.Assert((null != vertices) && (2 < vertices.Length));
HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
int count = vertices.Length;
Vector vertex = vertices[count - 1];
for (int i = 0; i < count; i++)
{
Vector nextVertex = vertices[i];
hitResult = WhereIsSegmentAboutSegment(hitBegin, hitEnd, vertex, nextVertex);
if (HitResult.Hit == hitResult)
{
return true;
}
if (IsOutside(hitResult, prevResult))
{
return false;
}
if (i == 0)
{
firstResult = hitResult;
}
prevResult = hitResult;
vertex = nextVertex;
}
return (false == IsOutside(firstResult, hitResult));
}
///
/// This is a specialized version of HitTestPolygonSegment that takes
/// a Quad for a polygon. This method is called very intensively by
/// hit-testing API and we don't want to create Vector[] for every quad it hit-tests.
///
/// the connecting quad to test against
/// begin point of the hitting segment
/// end point of the hitting segment
/// true if hit, false otherwise
internal static bool HitTestQuadSegment(Quad quad, Point hitBegin, Point hitEnd)
{
System.Diagnostics.Debug.Assert(quad.IsEmpty == false);
HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
int count = 4;
Vector zeroVector = new Vector(0, 0);
Vector hitVector = hitEnd - hitBegin;
Vector vertex = quad[count - 1] - hitBegin;
for (int i = 0; i < count; i++)
{
Vector nextVertex = quad[i] - hitBegin;
hitResult = WhereIsSegmentAboutSegment(zeroVector, hitVector, vertex, nextVertex);
if (HitResult.Hit == hitResult)
{
return true;
}
if (true == IsOutside(hitResult, prevResult))
{
return false;
}
if (i == 0)
{
firstResult = hitResult;
}
prevResult = hitResult;
vertex = nextVertex;
}
return (false == IsOutside(firstResult, hitResult));
}
///
/// Hit-test a polygin against a circle
///
/// Vectors representing the vertices of the polygon, ordered in clockwise order
/// Vector representing the center of the circle
/// Vector representing the radius of the circle
/// true if hit, false otherwise
internal static bool HitTestPolygonCircle(Vector[] vertices, Vector center, Vector radius)
{
// NTRAID#WINDOWS-1448096-2006/1/9-SAMGEO, this code is not called, but will be in VNext
throw new NotImplementedException();
/*
System.Diagnostics.Debug.Assert((null != vertices) && (2 < vertices.Length));
HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
int count = vertices.Length;
Vector vertex = vertices[count - 1];
for (int i = 0; i < count; i++)
{
Vector nextVertex = vertices[i];
hitResult = WhereIsCircleAboutSegment(center, radius, vertex, nextVertex);
if (HitResult.Hit == hitResult)
{
return true;
}
if (true == IsOutside(hitResult, prevResult))
{
return false;
}
if (i == 0)
{
firstResult = hitResult;
}
prevResult = hitResult;
vertex = nextVertex;
}
return (false == IsOutside(firstResult, hitResult));
*/
}
///
/// This is a specialized version of HitTestPolygonCircle that takes
/// a Quad for a polygon. This method is called very intensively by
/// hit-testing API and we don't want to create Vector[] for every quad it hit-tests.
///
/// the connecting quad
/// center of the circle
/// radius of the circle
/// true if hit; false otherwise
internal static bool HitTestQuadCircle(Quad quad, Point center, Vector radius)
{
// NTRAID#WINDOWS-1448096-2006/1/9-SAMGEO, this code is not called, but will be in VNext
throw new NotImplementedException();
/*
System.Diagnostics.Debug.Assert(quad.IsEmpty == false);
Vector centerVector = (Vector)center;
HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
int count = 4;
Vector vertex = (Vector)quad[count - 1];
for (int i = 0; i < count; i++)
{
Vector nextVertex = (Vector)quad[i];
hitResult = WhereIsCircleAboutSegment(centerVector, radius, vertex, nextVertex);
if (HitResult.Hit == hitResult)
{
return true;
}
if (true == IsOutside(hitResult, prevResult))
{
return false;
}
if (i == 0)
{
firstResult = hitResult;
}
prevResult = hitResult;
vertex = nextVertex;
}
return (false == IsOutside(firstResult, hitResult));
*/
}
#endregion
#region Whereabouts
///
/// Finds out where the segment [hitBegin, hitEnd]
/// is about the segment [orgBegin, orgEnd].
///
internal static HitResult WhereIsSegmentAboutSegment(
Vector hitBegin, Vector hitEnd, Vector orgBegin, Vector orgEnd)
{
if (hitEnd == hitBegin)
{
return WhereIsCircleAboutSegment(hitBegin, new Vector(0, 0), orgBegin, orgEnd);
}
//---------------------------------------------------------------------
// Source: http://isc.faqs.org/faqs/graphics/algorithms-faq/
// Subject 1.03: How do I find intersections of 2 2D line segments?
//
// Let A,B,C,D be 2-space position vectors. Then the directed line
// segments AB & CD are given by:
//
// AB=A+r(B-A), r in [0,1]
// CD=C+s(D-C), s in [0,1]
//
// If AB & CD intersect, then
//
// A+r(B-A)=C+s(D-C), or Ax+r(Bx-Ax)=Cx+s(Dx-Cx)
// Ay+r(By-Ay)=Cy+s(Dy-Cy) for some r,s in [0,1]
//
// Solving the above for r and s yields
//
// (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
// r = ----------------------------- (eqn 1)
// (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
//
// (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
// s = ----------------------------- (eqn 2)
// (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
//
// Let P be the position vector of the intersection point, then
//
// P=A+r(B-A) or Px=Ax+r(Bx-Ax) and Py=Ay+r(By-Ay)
//
// By examining the values of r & s, you can also determine some
// other limiting conditions:
// If 0 <= r <= 1 && 0 <= s <= 1, intersection exists
// r < 0 or r > 1 or s < 0 or s > 1 line segments do not intersect
// If the denominator in eqn 1 is zero, AB & CD are parallel
// If the numerator in eqn 1 is also zero, AB & CD are collinear.
// If they are collinear, then the segments may be projected to the x-
// or y-axis, and overlap of the projected intervals checked.
//
// If the intersection point of the 2 lines are needed (lines in this
// context mean infinite lines) regardless whether the two line
// segments intersect, then
// If r > 1, P is located on extension of AB
// If r < 0, P is located on extension of BA
// If s > 1, P is located on extension of CD
// If s < 0, P is located on extension of DC
// Also note that the denominators of eqn 1 & 2 are identical.
//
// References:
// [O'Rourke (C)] pp. 249-51
// [Gems III] pp. 199-202 "Faster Line Segment Intersection,"
//---------------------------------------------------------------------
// The result tells where the segment CD is about the vector AB.
// Return "Right" if either C or D is not on the left from AB.
HitResult result = HitResult.Right;
// Calculate the vectors.
Vector AB = orgEnd - orgBegin; // B - A
Vector CA = orgBegin - hitBegin; // A - C
Vector CD = hitEnd - hitBegin; // D - C
double det = Vector.Determinant(AB, CD);
if (DoubleUtil.IsZero(det))
{
// The segments are parallel.
/*if (DoubleUtil.IsZero(Vector.Determinant(CD, CA)))
{
// The segments are collinear.
// Check if their X and Y projections overlap.
if ((Math.Max(orgBegin.X, orgEnd.X) >= Math.Min(hitBegin.X, hitEnd.X)) &&
(Math.Min(orgBegin.X, orgEnd.X) <= Math.Max(hitBegin.X, hitEnd.X)) &&
(Math.Max(orgBegin.Y, orgEnd.Y) >= Math.Min(hitBegin.Y, hitEnd.Y)) &&
(Math.Min(orgBegin.Y, orgEnd.Y) <= Math.Max(hitBegin.Y, hitEnd.Y)))
{
// The segments overlap.
result = HitResult.Hit;
}
else if (false == DoubleUtil.IsZero(AB.X))
{
result = ((AB.X * CA.X) > 0) ? HitResult.Behind : HitResult.InFront;
}
else
{
result = ((AB.Y * CA.Y) > 0) ? HitResult.Behind : HitResult.InFront;
}
}
else */
if (DoubleUtil.IsZero(Vector.Determinant(CD, CA)) || DoubleUtil.GreaterThan(Vector.Determinant(AB, CA), 0))
{
// C is on the left from AB, and, since the segments are parallel, D is also on the left.
result = HitResult.Left;
}
}
else
{
double r = AdjustFIndex(Vector.Determinant(AB, CA) / det);
if (r > 0 && r < 1)
{
// The line defined AB does cross the segment CD.
double s = AdjustFIndex(Vector.Determinant(CD, CA) / det);
if (s > 0 && s < 1)
{
// The crossing point is on the segment AB as well.
result = HitResult.Hit;
}
else
{
result = (0 < s) ? HitResult.InFront : HitResult.Behind;
}
}
else if ((WhereIsVectorAboutVector(hitBegin - orgBegin, AB) == HitResult.Left)
|| (WhereIsVectorAboutVector(hitEnd - orgBegin, AB) == HitResult.Left))
{
// The line defined AB doesn't cross the segment CD, and neither C nor D
// is on the right from AB
result = HitResult.Left;
}
}
return result;
}
///
/// Find out the relative location of a circle relative to a line segment
///
/// center of the circle
/// radius of the circle. center.radius is a point on the circle
/// begin point of the line segment
/// end point of the line segment
/// test result
internal static HitResult WhereIsCircleAboutSegment(
Vector center, Vector radius, Vector segBegin, Vector segEnd)
{
segBegin -= center;
segEnd -= center;
double radiusSquared = radius.LengthSquared;
// This will find out the nearest path from center to a point on the segment
double distanceSquared = GetNearest(segBegin, segEnd).LengthSquared;
// The segment must cross the circle, hit
if (radiusSquared > distanceSquared)
{
return HitResult.Hit;
}
Vector segVector = segEnd - segBegin;
HitResult result = HitResult.Right;
// NTRAID#Tablet PC bugs-26556-2004/10/19-xiaotu,resolved two issues with the original code:
// 1. The local varial "normal" is assigned a value but it is never used afterwards. \
// 2. the code indicates that that only case result is HitResult.InFront or HitResult.Behind is
// when WhereIsVectorAboutVector(-segBegin, segVector) == HitResult.Left.
HitResult vResult = WhereIsVectorAboutVector(-segBegin, segVector);
//either front or behind
if (vResult == HitResult.Hit)
{
result = DoubleUtil.LessThan(segBegin.LengthSquared, segEnd.LengthSquared) ? HitResult.InFront :
HitResult.Behind;
}
else
{
// Find the projection of center on the segment.
double findex = GetProjectionFIndex(segBegin, segEnd);
// Get the normal vector, pointing from center to the projection point
Vector normal = segBegin + (segVector * findex);
// recalculate distanceSquared using normal
distanceSquared = normal.LengthSquared;
// The extension of the segment won't hit the circle
if (radiusSquared <= distanceSquared)
{
// either left or right
result = vResult;
}
else
{
result = (findex > 0) ? HitResult.InFront : HitResult.Behind;
}
}
return result;
}
///
/// Finds out where the vector1 is about the vector2.
///
internal static HitResult WhereIsVectorAboutVector(Vector vector1, Vector vector2)
{
double determinant = Vector.Determinant(vector1, vector2);
if (DoubleUtil.IsZero(determinant))
{
return HitResult.Hit; // collinear
}
return (0 < determinant) ? HitResult.Left : HitResult.Right;
}
///
/// Tells whether the hitVector intersects the arc defined by two vectors.
///
internal static HitResult WhereIsVectorAboutArc(Vector hitVector, Vector arcBegin, Vector arcEnd)
{
//HitResult result = HitResult.Right;
if (arcBegin == arcEnd)
{
// full circle
return HitResult.Hit;
}
if (HitResult.Right == WhereIsVectorAboutVector(arcEnd, arcBegin))
{
// small arc
if ((HitResult.Left != WhereIsVectorAboutVector(hitVector, arcBegin)) &&
(HitResult.Right != WhereIsVectorAboutVector(hitVector, arcEnd)))
{
return HitResult.Hit;
}
}
else if ((HitResult.Left != WhereIsVectorAboutVector(hitVector, arcBegin)) ||
(HitResult.Right != WhereIsVectorAboutVector(hitVector, arcEnd)))
{
return HitResult.Hit;
}
if ((WhereIsVectorAboutVector(hitVector - arcBegin, TurnLeft(arcBegin)) != HitResult.Left) ||
(WhereIsVectorAboutVector(hitVector - arcEnd, TurnRight(arcEnd)) != HitResult.Right))
{
return HitResult.Left;
}
return HitResult.Right;
}
#endregion
#region Misc. helpers
///
///
///
///
///
///
///
///
///
///
///
///
///
///
/// Internal helper function to find out the ratio of the distance from hitpoint to lineVector
/// and the distance from lineVector to (lineVector+nextLine)
///
/// This is one edge of a polygonal node
/// The connection vector between the same edge on biginNode and ednNode
/// a point
/// the relative position of hitPoint
internal static double GetPositionBetweenLines(Vector linesVector, Vector nextLine, Vector hitPoint)
{
Vector nearestOnFirst = GetProjection(-hitPoint, linesVector - hitPoint);
hitPoint = nextLine - hitPoint;
Vector nearestOnSecond = GetProjection(hitPoint, hitPoint + linesVector);
Vector shortest = nearestOnFirst - nearestOnSecond;
System.Diagnostics.Debug.Assert((false == DoubleUtil.IsZero(shortest.X)) || (false == DoubleUtil.IsZero(shortest.Y)));
//return DoubleUtil.IsZero(shortest.X) ? (nearestOnFirst.Y / shortest.Y) : (nearestOnFirst.X / shortest.X);
return Math.Sqrt(nearestOnFirst.LengthSquared / shortest.LengthSquared);
}
///
/// On a line defined buy two points finds the findex of the point
/// nearest to the origin (0,0). Same as FindNearestOnLine just
/// different output.
///
/// A point on the line.
/// Another point on the line.
///
/// On a line defined buy two points finds the point nearest to the origin (0,0).
///
/// A point on the line.
/// Another point on the line.
///
/// On a given segment finds the point nearest to the origin (0,0).
///
/// The segment's begin point.
/// The segment's end point.
///
/// Clears double's computation fuzz around 0 and 1
///
internal static double AdjustFIndex(double findex)
{
return DoubleUtil.IsZero(findex) ? 0 : (DoubleUtil.IsOne(findex) ? 1 : findex);
}
#endregion
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//------------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//-----------------------------------------------------------------------
using System;
using System.Collections.Generic;
using System.Windows;
using System.Windows.Media;
using System.Windows.Input;
namespace MS.Internal.Ink
{
///
/// Static methods implementing generic hit-testing operations
///
internal partial class StrokeNodeOperations
{
#region enum HitResult
/// A set of possible results frequently used in StrokeNodeOperations and derived classes
internal enum HitResult
{
Hit,
Left,
Right,
InFront,
Behind
}
#endregion
#region HitTestXxxYyy
///
/// Hit-tests a linear segment against a convex polygon.
///
/// Vertices of the polygon (in clockwise order)
/// an end point of the hitting segment
/// an end point of the hitting segment
/// true if hit; false otherwise
internal static bool HitTestPolygonSegment(Vector[] vertices, Vector hitBegin, Vector hitEnd)
{
System.Diagnostics.Debug.Assert((null != vertices) && (2 < vertices.Length));
HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
int count = vertices.Length;
Vector vertex = vertices[count - 1];
for (int i = 0; i < count; i++)
{
Vector nextVertex = vertices[i];
hitResult = WhereIsSegmentAboutSegment(hitBegin, hitEnd, vertex, nextVertex);
if (HitResult.Hit == hitResult)
{
return true;
}
if (IsOutside(hitResult, prevResult))
{
return false;
}
if (i == 0)
{
firstResult = hitResult;
}
prevResult = hitResult;
vertex = nextVertex;
}
return (false == IsOutside(firstResult, hitResult));
}
///
/// This is a specialized version of HitTestPolygonSegment that takes
/// a Quad for a polygon. This method is called very intensively by
/// hit-testing API and we don't want to create Vector[] for every quad it hit-tests.
///
/// the connecting quad to test against
/// begin point of the hitting segment
/// end point of the hitting segment
/// true if hit, false otherwise
internal static bool HitTestQuadSegment(Quad quad, Point hitBegin, Point hitEnd)
{
System.Diagnostics.Debug.Assert(quad.IsEmpty == false);
HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
int count = 4;
Vector zeroVector = new Vector(0, 0);
Vector hitVector = hitEnd - hitBegin;
Vector vertex = quad[count - 1] - hitBegin;
for (int i = 0; i < count; i++)
{
Vector nextVertex = quad[i] - hitBegin;
hitResult = WhereIsSegmentAboutSegment(zeroVector, hitVector, vertex, nextVertex);
if (HitResult.Hit == hitResult)
{
return true;
}
if (true == IsOutside(hitResult, prevResult))
{
return false;
}
if (i == 0)
{
firstResult = hitResult;
}
prevResult = hitResult;
vertex = nextVertex;
}
return (false == IsOutside(firstResult, hitResult));
}
///
/// Hit-test a polygin against a circle
///
/// Vectors representing the vertices of the polygon, ordered in clockwise order
/// Vector representing the center of the circle
/// Vector representing the radius of the circle
/// true if hit, false otherwise
internal static bool HitTestPolygonCircle(Vector[] vertices, Vector center, Vector radius)
{
// NTRAID#WINDOWS-1448096-2006/1/9-SAMGEO, this code is not called, but will be in VNext
throw new NotImplementedException();
/*
System.Diagnostics.Debug.Assert((null != vertices) && (2 < vertices.Length));
HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
int count = vertices.Length;
Vector vertex = vertices[count - 1];
for (int i = 0; i < count; i++)
{
Vector nextVertex = vertices[i];
hitResult = WhereIsCircleAboutSegment(center, radius, vertex, nextVertex);
if (HitResult.Hit == hitResult)
{
return true;
}
if (true == IsOutside(hitResult, prevResult))
{
return false;
}
if (i == 0)
{
firstResult = hitResult;
}
prevResult = hitResult;
vertex = nextVertex;
}
return (false == IsOutside(firstResult, hitResult));
*/
}
///
/// This is a specialized version of HitTestPolygonCircle that takes
/// a Quad for a polygon. This method is called very intensively by
/// hit-testing API and we don't want to create Vector[] for every quad it hit-tests.
///
/// the connecting quad
/// center of the circle
/// radius of the circle
/// true if hit; false otherwise
internal static bool HitTestQuadCircle(Quad quad, Point center, Vector radius)
{
// NTRAID#WINDOWS-1448096-2006/1/9-SAMGEO, this code is not called, but will be in VNext
throw new NotImplementedException();
/*
System.Diagnostics.Debug.Assert(quad.IsEmpty == false);
Vector centerVector = (Vector)center;
HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
int count = 4;
Vector vertex = (Vector)quad[count - 1];
for (int i = 0; i < count; i++)
{
Vector nextVertex = (Vector)quad[i];
hitResult = WhereIsCircleAboutSegment(centerVector, radius, vertex, nextVertex);
if (HitResult.Hit == hitResult)
{
return true;
}
if (true == IsOutside(hitResult, prevResult))
{
return false;
}
if (i == 0)
{
firstResult = hitResult;
}
prevResult = hitResult;
vertex = nextVertex;
}
return (false == IsOutside(firstResult, hitResult));
*/
}
#endregion
#region Whereabouts
///
/// Finds out where the segment [hitBegin, hitEnd]
/// is about the segment [orgBegin, orgEnd].
///
internal static HitResult WhereIsSegmentAboutSegment(
Vector hitBegin, Vector hitEnd, Vector orgBegin, Vector orgEnd)
{
if (hitEnd == hitBegin)
{
return WhereIsCircleAboutSegment(hitBegin, new Vector(0, 0), orgBegin, orgEnd);
}
//---------------------------------------------------------------------
// Source: http://isc.faqs.org/faqs/graphics/algorithms-faq/
// Subject 1.03: How do I find intersections of 2 2D line segments?
//
// Let A,B,C,D be 2-space position vectors. Then the directed line
// segments AB & CD are given by:
//
// AB=A+r(B-A), r in [0,1]
// CD=C+s(D-C), s in [0,1]
//
// If AB & CD intersect, then
//
// A+r(B-A)=C+s(D-C), or Ax+r(Bx-Ax)=Cx+s(Dx-Cx)
// Ay+r(By-Ay)=Cy+s(Dy-Cy) for some r,s in [0,1]
//
// Solving the above for r and s yields
//
// (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
// r = ----------------------------- (eqn 1)
// (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
//
// (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
// s = ----------------------------- (eqn 2)
// (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
//
// Let P be the position vector of the intersection point, then
//
// P=A+r(B-A) or Px=Ax+r(Bx-Ax) and Py=Ay+r(By-Ay)
//
// By examining the values of r & s, you can also determine some
// other limiting conditions:
// If 0 <= r <= 1 && 0 <= s <= 1, intersection exists
// r < 0 or r > 1 or s < 0 or s > 1 line segments do not intersect
// If the denominator in eqn 1 is zero, AB & CD are parallel
// If the numerator in eqn 1 is also zero, AB & CD are collinear.
// If they are collinear, then the segments may be projected to the x-
// or y-axis, and overlap of the projected intervals checked.
//
// If the intersection point of the 2 lines are needed (lines in this
// context mean infinite lines) regardless whether the two line
// segments intersect, then
// If r > 1, P is located on extension of AB
// If r < 0, P is located on extension of BA
// If s > 1, P is located on extension of CD
// If s < 0, P is located on extension of DC
// Also note that the denominators of eqn 1 & 2 are identical.
//
// References:
// [O'Rourke (C)] pp. 249-51
// [Gems III] pp. 199-202 "Faster Line Segment Intersection,"
//---------------------------------------------------------------------
// The result tells where the segment CD is about the vector AB.
// Return "Right" if either C or D is not on the left from AB.
HitResult result = HitResult.Right;
// Calculate the vectors.
Vector AB = orgEnd - orgBegin; // B - A
Vector CA = orgBegin - hitBegin; // A - C
Vector CD = hitEnd - hitBegin; // D - C
double det = Vector.Determinant(AB, CD);
if (DoubleUtil.IsZero(det))
{
// The segments are parallel.
/*if (DoubleUtil.IsZero(Vector.Determinant(CD, CA)))
{
// The segments are collinear.
// Check if their X and Y projections overlap.
if ((Math.Max(orgBegin.X, orgEnd.X) >= Math.Min(hitBegin.X, hitEnd.X)) &&
(Math.Min(orgBegin.X, orgEnd.X) <= Math.Max(hitBegin.X, hitEnd.X)) &&
(Math.Max(orgBegin.Y, orgEnd.Y) >= Math.Min(hitBegin.Y, hitEnd.Y)) &&
(Math.Min(orgBegin.Y, orgEnd.Y) <= Math.Max(hitBegin.Y, hitEnd.Y)))
{
// The segments overlap.
result = HitResult.Hit;
}
else if (false == DoubleUtil.IsZero(AB.X))
{
result = ((AB.X * CA.X) > 0) ? HitResult.Behind : HitResult.InFront;
}
else
{
result = ((AB.Y * CA.Y) > 0) ? HitResult.Behind : HitResult.InFront;
}
}
else */
if (DoubleUtil.IsZero(Vector.Determinant(CD, CA)) || DoubleUtil.GreaterThan(Vector.Determinant(AB, CA), 0))
{
// C is on the left from AB, and, since the segments are parallel, D is also on the left.
result = HitResult.Left;
}
}
else
{
double r = AdjustFIndex(Vector.Determinant(AB, CA) / det);
if (r > 0 && r < 1)
{
// The line defined AB does cross the segment CD.
double s = AdjustFIndex(Vector.Determinant(CD, CA) / det);
if (s > 0 && s < 1)
{
// The crossing point is on the segment AB as well.
result = HitResult.Hit;
}
else
{
result = (0 < s) ? HitResult.InFront : HitResult.Behind;
}
}
else if ((WhereIsVectorAboutVector(hitBegin - orgBegin, AB) == HitResult.Left)
|| (WhereIsVectorAboutVector(hitEnd - orgBegin, AB) == HitResult.Left))
{
// The line defined AB doesn't cross the segment CD, and neither C nor D
// is on the right from AB
result = HitResult.Left;
}
}
return result;
}
///
/// Find out the relative location of a circle relative to a line segment
///
/// center of the circle
/// radius of the circle. center.radius is a point on the circle
/// begin point of the line segment
/// end point of the line segment
/// test result
internal static HitResult WhereIsCircleAboutSegment(
Vector center, Vector radius, Vector segBegin, Vector segEnd)
{
segBegin -= center;
segEnd -= center;
double radiusSquared = radius.LengthSquared;
// This will find out the nearest path from center to a point on the segment
double distanceSquared = GetNearest(segBegin, segEnd).LengthSquared;
// The segment must cross the circle, hit
if (radiusSquared > distanceSquared)
{
return HitResult.Hit;
}
Vector segVector = segEnd - segBegin;
HitResult result = HitResult.Right;
// NTRAID#Tablet PC bugs-26556-2004/10/19-xiaotu,resolved two issues with the original code:
// 1. The local varial "normal" is assigned a value but it is never used afterwards. \
// 2. the code indicates that that only case result is HitResult.InFront or HitResult.Behind is
// when WhereIsVectorAboutVector(-segBegin, segVector) == HitResult.Left.
HitResult vResult = WhereIsVectorAboutVector(-segBegin, segVector);
//either front or behind
if (vResult == HitResult.Hit)
{
result = DoubleUtil.LessThan(segBegin.LengthSquared, segEnd.LengthSquared) ? HitResult.InFront :
HitResult.Behind;
}
else
{
// Find the projection of center on the segment.
double findex = GetProjectionFIndex(segBegin, segEnd);
// Get the normal vector, pointing from center to the projection point
Vector normal = segBegin + (segVector * findex);
// recalculate distanceSquared using normal
distanceSquared = normal.LengthSquared;
// The extension of the segment won't hit the circle
if (radiusSquared <= distanceSquared)
{
// either left or right
result = vResult;
}
else
{
result = (findex > 0) ? HitResult.InFront : HitResult.Behind;
}
}
return result;
}
///
/// Finds out where the vector1 is about the vector2.
///
internal static HitResult WhereIsVectorAboutVector(Vector vector1, Vector vector2)
{
double determinant = Vector.Determinant(vector1, vector2);
if (DoubleUtil.IsZero(determinant))
{
return HitResult.Hit; // collinear
}
return (0 < determinant) ? HitResult.Left : HitResult.Right;
}
///
/// Tells whether the hitVector intersects the arc defined by two vectors.
///
internal static HitResult WhereIsVectorAboutArc(Vector hitVector, Vector arcBegin, Vector arcEnd)
{
//HitResult result = HitResult.Right;
if (arcBegin == arcEnd)
{
// full circle
return HitResult.Hit;
}
if (HitResult.Right == WhereIsVectorAboutVector(arcEnd, arcBegin))
{
// small arc
if ((HitResult.Left != WhereIsVectorAboutVector(hitVector, arcBegin)) &&
(HitResult.Right != WhereIsVectorAboutVector(hitVector, arcEnd)))
{
return HitResult.Hit;
}
}
else if ((HitResult.Left != WhereIsVectorAboutVector(hitVector, arcBegin)) ||
(HitResult.Right != WhereIsVectorAboutVector(hitVector, arcEnd)))
{
return HitResult.Hit;
}
if ((WhereIsVectorAboutVector(hitVector - arcBegin, TurnLeft(arcBegin)) != HitResult.Left) ||
(WhereIsVectorAboutVector(hitVector - arcEnd, TurnRight(arcEnd)) != HitResult.Right))
{
return HitResult.Left;
}
return HitResult.Right;
}
#endregion
#region Misc. helpers
///
///
///
///
///
///
///
///
///
///
///
///
///
///
/// Internal helper function to find out the ratio of the distance from hitpoint to lineVector
/// and the distance from lineVector to (lineVector+nextLine)
///
/// This is one edge of a polygonal node
/// The connection vector between the same edge on biginNode and ednNode
/// a point
/// the relative position of hitPoint
internal static double GetPositionBetweenLines(Vector linesVector, Vector nextLine, Vector hitPoint)
{
Vector nearestOnFirst = GetProjection(-hitPoint, linesVector - hitPoint);
hitPoint = nextLine - hitPoint;
Vector nearestOnSecond = GetProjection(hitPoint, hitPoint + linesVector);
Vector shortest = nearestOnFirst - nearestOnSecond;
System.Diagnostics.Debug.Assert((false == DoubleUtil.IsZero(shortest.X)) || (false == DoubleUtil.IsZero(shortest.Y)));
//return DoubleUtil.IsZero(shortest.X) ? (nearestOnFirst.Y / shortest.Y) : (nearestOnFirst.X / shortest.X);
return Math.Sqrt(nearestOnFirst.LengthSquared / shortest.LengthSquared);
}
///
/// On a line defined buy two points finds the findex of the point
/// nearest to the origin (0,0). Same as FindNearestOnLine just
/// different output.
///
/// A point on the line.
/// Another point on the line.
///
/// On a line defined buy two points finds the point nearest to the origin (0,0).
///
/// A point on the line.
/// Another point on the line.
///
/// On a given segment finds the point nearest to the origin (0,0).
///
/// The segment's begin point.
/// The segment's end point.
///
/// Clears double's computation fuzz around 0 and 1
///
internal static double AdjustFIndex(double findex)
{
return DoubleUtil.IsZero(findex) ? 0 : (DoubleUtil.IsOne(findex) ? 1 : findex);
}
#endregion
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- CustomAttribute.cs
- WebBaseEventKeyComparer.cs
- StrokeNodeData.cs
- SqlInternalConnection.cs
- DeobfuscatingStream.cs
- SelectionRange.cs
- IsolatedStorageException.cs
- ProfileGroupSettings.cs
- WebBaseEventKeyComparer.cs
- FreezableOperations.cs
- InfoCardX509Validator.cs
- DataGridColumn.cs
- ZeroOpNode.cs
- Operand.cs
- InfoCardArgumentException.cs
- PageHandlerFactory.cs
- ThumbButtonInfo.cs
- DataGridViewMethods.cs
- XmlResolver.cs
- InputProviderSite.cs
- MonthChangedEventArgs.cs
- PropertyMetadata.cs
- DbException.cs
- webproxy.cs
- SchemaNames.cs
- XmlValueConverter.cs
- Size3D.cs
- TaskHelper.cs
- HtmlImage.cs
- EncodingStreamWrapper.cs
- MSG.cs
- TimersDescriptionAttribute.cs
- UriTemplateClientFormatter.cs
- DataAdapter.cs
- FormViewDeleteEventArgs.cs
- StringAnimationUsingKeyFrames.cs
- DataGridViewTopLeftHeaderCell.cs
- TextSerializer.cs
- BitmapDownload.cs
- BamlLocalizerErrorNotifyEventArgs.cs
- CategoryNameCollection.cs
- BitmapEffectInput.cs
- InfoCardRSAOAEPKeyExchangeDeformatter.cs
- NativeMethods.cs
- SchemaEntity.cs
- Crypto.cs
- BulletChrome.cs
- StaticTextPointer.cs
- StructureChangedEventArgs.cs
- HierarchicalDataBoundControlAdapter.cs
- ThreadExceptionEvent.cs
- _AutoWebProxyScriptHelper.cs
- TextRangeProviderWrapper.cs
- ConfigurationException.cs
- SourceSwitch.cs
- RequestQueryParser.cs
- EmbossBitmapEffect.cs
- DaylightTime.cs
- _CacheStreams.cs
- PasswordTextNavigator.cs
- PropertyFilter.cs
- _RequestCacheProtocol.cs
- BasicDesignerLoader.cs
- Latin1Encoding.cs
- NativeMethods.cs
- SvcMapFileLoader.cs
- EntityTypeEmitter.cs
- TextRangeEditTables.cs
- CategoryNameCollection.cs
- DataGridSortCommandEventArgs.cs
- ServiceAuthorizationBehavior.cs
- EntityTypeBase.cs
- Stream.cs
- CmsUtils.cs
- OdbcDataAdapter.cs
- Char.cs
- FormsAuthenticationUser.cs
- StorageAssociationSetMapping.cs
- TextBox.cs
- ComponentDesigner.cs
- X509Extension.cs
- CrossSiteScriptingValidation.cs
- EventLog.cs
- SimpleWorkerRequest.cs
- AliasedExpr.cs
- XmlAtomicValue.cs
- NetStream.cs
- FieldAccessException.cs
- WindowsUserNameSecurityTokenAuthenticator.cs
- Compiler.cs
- ExpandSegment.cs
- XmlSignatureManifest.cs
- HierarchicalDataBoundControlAdapter.cs
- ProjectionCamera.cs
- DbDataRecord.cs
- GuidelineCollection.cs
- BamlLocalizableResource.cs
- UnsafeNativeMethodsTablet.cs
- TypeFieldSchema.cs
- AnnotationService.cs