Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit9a40b9f

Browse files
f-frhsjkalias
andauthored
Circle2D intersection with Line(Segment)2D (#237)
* Feat: Line2D.DistanceTo(point)* feat: Circle2D.IntersectWith(Line2D)* doc: fix xml comment* refactor: extract the private method findParameterTs(Line2D)Aleady existing test cases must be changed because of the implementation of FindRoots.Polynomial(coeffs), that is, the order of the solutions.* feat: Circle2D.IntersectWith(LineSegment2D)* doc: fix the variable-name list in comment* fix: a typo* change: use the fact that dot-product of the unit vector is always 1.0* Revert "Feat: Line2D.DistanceTo(point)"This reverts commit0a2521d.* remove: src/Spatial/Extensions/DoubleExtensions.cs* doc: revise xml comments* fix a typo* test: fix testcases to test number of intersections* fix: IntersectionWith() to return a single point when a line tangent to the circle* test: Add tests for intersection of Circle and LineSegment2Dfor the case where LineSegment contains some of obtained intersections.* test: add TODO comment* refactor: rename line to segment* fix: type declaration (from 1d to 1.0)* test: fix testcases to use expected points* test: fix testcases to use expected points* test: add testcases where the line is parallel to the Y-axis* test: add testcases parallel to Y-axis and general cases* test: add testcases for Intersection of Circle2D with LIneSegment2D- parallel to X-axis- parallel to Y-axis- general cases (eg. x-y+c=0)test: rename method's name* test: replace +01 to +1* Minor changes in test---------Co-authored-by: jkaliak <john@kaliakatsos.net>
1 parent8cae855 commit9a40b9f

File tree

3 files changed

+189
-1
lines changed

3 files changed

+189
-1
lines changed

‎src/Spatial.Tests/Euclidean/Circle2DTests.cs‎

Lines changed: 122 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
1-
usingSystem;
1+
usingSystem;
2+
usingSystem.Linq;
23
usingMathNet.Spatial.Euclidean;
34
usingNUnit.Framework;
45

@@ -58,5 +59,125 @@ public void CircleFromThreePointsArgumentException()
5859

5960
Assert.Throws<ArgumentException>(()=>{Circle2D.FromPoints(p1,p2,p3);});
6061
}
62+
63+
//parallel to the X-axis
64+
[TestCase("0,0",1,"-10,-10","+10,-10",null)]
65+
[TestCase("0,0",1,"-10,-1","+10,-1","0,-1")]
66+
[TestCase("0,0",1,"-10,0","+10,0","+1,0;-1,0")]
67+
[TestCase("0,0",1,"-10,+1","+10,+1","0,+1")]
68+
[TestCase("0,0",1,"-10,+10","+10,+10",null)]
69+
//parallel to the Y-axis
70+
[TestCase("0,0",1,"-10,-10","-10,+10",null)]
71+
[TestCase("0,0",1,"-1,-10","-1,+10","-1,0")]
72+
[TestCase("0,0",1,"0,-10","0,+10","0,+1;0,-1")]
73+
[TestCase("0,0",1,"+1,-10","+1,+10","+1,0")]
74+
[TestCase("0,0",1,"+10,-10","+10,+10",null)]
75+
//general cases
76+
[TestCase("0,0",1,"-10,+10","+10,+10",null)]
77+
[TestCase("0,0",1,"-1.414213562373095,0","0,+1.414213562373095","-0.707,0.707")]
78+
[TestCase("0,0",1,"-10,-10","+10,+10","+0.707,+0.707;-0.707,-0.707")]
79+
[TestCase("0,0",1,"0,-1.41421356","+1.41421356,0","+0.707,-0.707")]
80+
[TestCase("0,0",1,"0,-10","+10,0",null)]
81+
publicvoidCircleIntersectWithLine2D(stringsc,doubleradius,stringsps,stringspe,stringintersections)
82+
{
83+
varcircle=newCircle2D(Point2D.Parse(sc),radius);
84+
varline=newLine2D(Point2D.Parse(sps),Point2D.Parse(spe));
85+
86+
varactual=circle.IntersectWith(line);
87+
88+
varexpected=parseToPointsArray(intersections);
89+
for(inti=0;i<Math.Min(actual.Length,expected.Length);i++)
90+
{
91+
vara=actual[i];
92+
vare=expected[i];
93+
AssertGeometry.AreEqual(a,e,1e-3);//needs to fix for the default tolerance
94+
}
95+
}
96+
//parallel to X-axis
97+
////segment contains the all intersections(same to the cases of circle and line)
98+
[TestCase("0,0",1,"-10,+10","+10,+10",null)]
99+
[TestCase("0,0",1,"-10,+1","+10,+1","0,+1")]
100+
[TestCase("0,0",1,"-10,0","+10,0","+1,0;-1,0")]
101+
[TestCase("0,0",1,"-10,-1","+10,-1","0,-1")]
102+
[TestCase("0,0",1,"-10,-10","+10,-10",null)]
103+
////segments cross the circle's contour just 1 time
104+
[TestCase("0,0",1,"+0,+10","+10,+10",null)]
105+
[TestCase("0,0",1,"+0,+1","+10,+1","0,1")]
106+
[TestCase("0,0",1,"+0,+0","+10,+0","1,0")]
107+
[TestCase("0,0",1,"+0,-1","+10,-1","0,-1")]
108+
[TestCase("0,0",1,"+0,-10","+10,-10",null)]
109+
////segment contains no intersections(px of the startingPoint is too big to intersect with the circle)
110+
[TestCase("0,0",1,"+10,+10","+100,+10",null)]
111+
[TestCase("0,0",1,"+10,+1","+100,+1",null)]
112+
[TestCase("0,0",1,"+10,+0","+100,0",null)]
113+
[TestCase("0,0",1,"+10,-1","+100,-1",null)]
114+
[TestCase("0,0",1,"+10,-10","+100,-10",null)]
115+
//parallel to Y-axis
116+
////segment contains the all intersections(same to the cases of circle and line)
117+
[TestCase("0,0",1,"-10,-10","-10,+10",null)]
118+
[TestCase("0,0",1,"-1,-10","-1,+10","-1,0")]
119+
[TestCase("0,0",1,"+0,-10","+0,+10","0,+1;0,-1")]
120+
[TestCase("0,0",1,"+1,-10","+1,+10","+1,0")]
121+
[TestCase("0,0",1,"+10,-10","+10,+10",null)]
122+
////segments cross the circle's contour just 1 time
123+
[TestCase("0,0",1,"+10,0","+10,+10",null)]
124+
[TestCase("0,0",1,"+1,0","+1,+10","+1,0")]
125+
[TestCase("0,0",1,"+0,0","+0,+10","0,+1")]
126+
[TestCase("0,0",1,"-1,0","-1,+10","-1,0")]
127+
[TestCase("0,0",1,"-10,0","-10,+10",null)]
128+
////segment contains no intersections(py of the startingPoint is too big to intersect with the circle)
129+
[TestCase("0,0",1,"+10,+10","+10,+100",null)]
130+
[TestCase("0,0",1,"+1,+10","+1,+100",null)]
131+
[TestCase("0,0",1,"+0,+10","+0,+100",null)]
132+
[TestCase("0,0",1,"-1,+10","-1,+100",null)]
133+
[TestCase("0,0",1,"-10,+10","-10,+100",null)]
134+
//general cases
135+
////segment contains the all intersections(same to the cases of circle and line)
136+
[TestCase("0,0",1,"-10,+10","+10,+10",null)]
137+
[TestCase("0,0",1,"-1.414213562373095,0","0,+1.414213562373095","-0.707,0.707")]
138+
[TestCase("0,0",1,"-10,-10","+10,+10","+0.707,+0.707;-0.707,-0.707")]
139+
[TestCase("0,0",1,"0,-1.41421356","+1.41421356,0","+0.707,-0.707")]
140+
[TestCase("0,0",1,"0,-10","+10,0",null)]
141+
////segments cross the circle's contour just 1 time
142+
[TestCase("0,0",1,"+10,0","+10,+10",null)]
143+
[TestCase("0,0",1,"+1,0","+1,+10","+1,0")]
144+
[TestCase("0,0",1,"+0,0","+0,+10","0,+1")]
145+
[TestCase("0,0",1,"-1,0","-1,+10","-1,0")]
146+
[TestCase("0,0",1,"-10,0","-10,+10",null)]
147+
////segment contains no intersections(py of the startingPoint is too big to intersect with the circle)
148+
[TestCase("0,0",1,"+10,+10","+10,+100",null)]
149+
[TestCase("0,0",1,"+1,+10","+1,+100",null)]
150+
[TestCase("0,0",1,"+0,+10","+0,+100",null)]
151+
[TestCase("0,0",1,"-1,+10","-1,+100",null)]
152+
[TestCase("0,0",1,"-10,+10","-10,+100",null)]
153+
publicvoidCircleIntersectWithLineSegment2D(stringsCenter,doubleradius,stringsStart,stringsEnd,stringintersections)
154+
{
155+
varcircle=newCircle2D(Point2D.Parse(sCenter),radius);
156+
varsegment=newLineSegment2D(Point2D.Parse(sStart),Point2D.Parse(sEnd));
157+
158+
varactual=circle.IntersectWith(segment);
159+
160+
varexpected=parseToPointsArray(intersections);
161+
for(inti=0;i<Math.Min(actual.Length,expected.Length);i++)
162+
{
163+
vara=actual[i];
164+
vare=expected[i];
165+
AssertGeometry.AreEqual(a,e,1e-3);//FIXME!
166+
}
167+
}
168+
169+
privatePoint2D[]parseToPointsArray(stringinput)
170+
{
171+
if(input==null)
172+
{
173+
returnnewPoint2D[]{};
174+
}
175+
176+
varresult=input.Split(';')
177+
.Select(s=>Point2D.Parse(s))
178+
.ToArray();
179+
180+
returnresult;
181+
}
61182
}
62183
}

‎src/Spatial/Euclidean/Circle2D.cs‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,11 @@
11
usingMathNet.Spatial.Internals;
22
usingSystem;
33
usingSystem.Diagnostics.Contracts;
4+
usingSystem.Linq;
45
usingSystem.Xml;
56
usingSystem.Xml.Schema;
67
usingSystem.Xml.Serialization;
8+
usingMathNet.Numerics;
79
usingHashCode=MathNet.Spatial.Internals.HashCode;
810

911
namespaceMathNet.Spatial.Euclidean
@@ -131,6 +133,67 @@ public static Circle2D FromPoints(Point2D pointA, Point2D pointB, Point2D pointC
131133
returnnewCircle2D(center,radius);
132134
}
133135

136+
/// <summary>
137+
/// Returns the intersections of this circle with the given line.
138+
/// </summary>
139+
/// <param name="line">the given line</param>
140+
/// <returns>intersections as a Point2D Array, depending on the count.</returns>
141+
publicPoint2D[]IntersectWith(Line2Dline)
142+
{
143+
varts=this.findParameterTs(line);
144+
varresult=ts
145+
.Select(t=>line.StartPoint+t*line.Direction)
146+
.ToArray();
147+
returnresult;
148+
}
149+
150+
privatedouble[]findParameterTs(Line2Dline)
151+
{
152+
// These 2 equations in vector form can be described
153+
// (p-cc)^2=r^2 (eq1)
154+
// p=s+t*d (eq2)
155+
// , where p is the point on the line and/or circle,
156+
// cc is the center of the circle,
157+
// r is the radius of the circle,
158+
// s is the starting point of the line,
159+
// t is the parameter and
160+
// d is the line direction.
161+
// Substituting (eq2) into (eq1) yields:
162+
// ((s+t*d)-cc)^2=r^2 (eq3)
163+
// (eq3) reduces to the following quadratic equation: a*t^2 + b*t + c==0
164+
165+
varcc=this.Center.ToVector2D();//center of circle
166+
vars=line.StartPoint.ToVector2D();
167+
vard=line.Direction;
168+
varr=this.Radius;
169+
170+
vara=1.0;
171+
varb=2*(s.DotProduct(d)-d.DotProduct(cc));
172+
varc=(s-cc).DotProduct(s-cc)-r*r;
173+
174+
varsolutions=FindRoots.Polynomial(new[]{c,b,a});
175+
varts=solutions
176+
.Where(z=>z.IsReal())
177+
.Select(z=>z.Real)
178+
.Distinct()
179+
.ToArray();
180+
returnts;
181+
}
182+
183+
/// <summary>
184+
/// Returns the intersections of this circle with the given line segment, which lie within the segment.
185+
/// </summary>
186+
/// <param name="segment">the given line-segment</param>
187+
/// <returns>intersections as a Point2D Array, depending on the count.</returns>
188+
publicPoint2D[]IntersectWith(LineSegment2Dsegment)
189+
{
190+
varts=findParameterTs(segment.ToLine2D())
191+
.Where(t=>0<=t&&t<=segment.Length);
192+
varresult=ts.Select(t=>segment.StartPoint+t*segment.Direction).ToArray();
193+
returnresult;
194+
}
195+
196+
134197
/// <summary>
135198
/// Returns a value to indicate if a pair of circles are equal
136199
/// </summary>

‎src/Spatial/Euclidean/LineSegment2D.cs‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -236,5 +236,9 @@ void IXmlSerializable.WriteXml(XmlWriter writer)
236236
writer.WriteElement("StartPoint",StartPoint);
237237
writer.WriteElement("EndPoint",EndPoint);
238238
}
239+
240+
/// <summary>convert this to Line2D </summary>
241+
/// <returns>converted Line2D object</returns>
242+
publicLine2DToLine2D()=>newLine2D(StartPoint,EndPoint);
239243
}
240244
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp