# Circle Line Intersect Plugin

Hi people,

i´m trying to implement this code in a dynamic plugin, but i don´t know really how it works…
http://www.openprocessing.org/visuals/?visualID=8009

If anybody has a moment to check it would be great, this is my first attempt to make a plugin.

Here there is a realted thread.
https://discourse.vvvv.org/t/7075

ari.

CircleLineIntersect.rar (9.5 kB)

Hi,
i think i´ve got it, but it returns 2 solutions even if one of the points is into the circle.

Any idea?

ari

Circle Line Intersect_2 (43.5 kB)

It seems that all the people is on Hollydays ?¿

Haven’t looked at your code, but i guess it creates the formula of the line based on the 2 points you pass to the algorithm.

And of course this line (almost) always has 2 intersections with the circle.

I guess if you only want the intersection that lies between these 2 points, take the solution(x,y) where solution(x) is between P1(x) and P2(x) and solution(y) is between P1(y) and P2(y).

Hi ft, thanks a lot for your response.
this is the code, i´ve just implemented the processing one.

Any help would be great.

Ari.

``````- region usings
using System;
using System.ComponentModel.Composition;

using VVVV.PluginInterfaces.V1;
using VVVV.PluginInterfaces.V2;
using VVVV.Utils.VColor;
using VVVV.Utils.VMath;

using VVVV.Core.Logging;
- endregion usings

namespace VVVV.Nodes
{
#region PluginInfo
[PluginInfo(Name = "CircleLineIntersect",
Category = "Value",
Help = "Basic template with one value in/out",
Tags = "")]
#endregion PluginInfo
public class ValueCircleLineIntersectNode : IPluginEvaluate
{
#region fields & pins
[Input("CircleCenter")](Input("CircleCenter"))

[Input("Line1")](Input("Line1"))

[Input("Line2")](Input("Line2"))

[Output("Intersection 1 ")](Output("Intersection 1 "))

[Output("Intersection 2 ")](Output("Intersection 2 "))

[Output("Number of Solutions")](Output("Number of Solutions"))

[Import()](Import())
ILogger FLogger;
#endregion fields & pins

//called when data for any output pin is requested
{

for (int i = 0; i < SpreadMax; i++)
{
Vector2D s1;
Vector2D s2;

FSolutionCount[i](i) = CircleLineIntersection(center[i](i), cr[i](i), L1[i](i), L2[i](i) , out s1, out s2);
FIntersection1[i](i) = s1;
FIntersection2[i](i) = s2;
}

//FLogger.Log(LogType.Debug, "Logging to Renderer (TTY)");
}
private int CircleLineIntersection (Vector2D center, double cr, Vector2D L1 , Vector2D L2,  out Vector2D p1, out Vector2D p2)
{
p1 = new Vector2D();
p2 = new Vector2D();

double dx = L2.x - L1.x;
double dy = L2.y - L1.y;
double a = dx * dx + dy * dy;
double b = 2 * (dx * (L1.x - center.x) + dy * (L1.y - center.y));
double c = L1.x * L1.x + L1.y * L1.y + center.x * center.x + center.y * center.y - 2 * (center.x * L1.x + center.y * L1.y)-(cr * cr);
double bb4ac = b * b - 4 * a * c;

double mu1 = (-b + Math.Sqrt(bb4ac)) / (2*a);
double mu2 = (-b - Math.Sqrt(bb4ac)) / (2*a);

double i1x = L1.x + mu1*(dx);
double i1y = L1.y + mu1*(dy);

double i2x = L1.x + mu2*(dx);
double i2y = L1.y + mu2*(dy);

double dist1 = Math.Sqrt[L1.x-center.x)*(L1.x-center.x)+(L1.y-center.y)*(L1.y-center.y](https://vvvv.org/documentation/L1.x-center.x)*(L1.x-center.x)+(L1.y-center.y)*(L1.y-center.y);
double dist2 = Math.Sqrt[L2.x-center.x)*(L2.x-center.x)+(L2.y-center.y)*(L2.y-center.y](https://vvvv.org/documentation/L2.x-center.x)*(L2.x-center.x)+(L2.y-center.y)*(L2.y-center.y);
double dist3 = Math.Sqrt[L2.x-L1.x)*(L2.x-L1.x)+(L2.y-L1.y)*(L2.y-L1.y](https://vvvv.org/documentation/L2.x-L1.x)*(L2.x-L1.x)+(L2.y-L1.y)*(L2.y-L1.y);
double dist4 = Math.Sqrt[p1.x-i1x)*(p1.x-i1x)+(p1.y-i1y)*(p1.y-i1y](https://vvvv.org/documentation/p1.x-i1x)*(p1.x-i1x)+(p1.y-i1y)*(p1.y-i1y);
double dist5 = Math.Sqrt[p1.x-i2x)*(p1.x-i2x)+(p1.y-i2y)*(p1.y-i2y](https://vvvv.org/documentation/p1.x-i2x)*(p1.x-i2x)+(p1.y-i2y)*(p1.y-i2y);

if (bb4ac < 0) {  // Not intersecting
return 0;
}
if (bb4ac > 0) {  //2 solutions

p1.x = i1x;
p1.y = i1y;
p2.x = i2x;
p2.y = i2y;
return 2;
}
if (bb4ac == 0) {  //1 solution tangent

p1.x = i1x;
p1.y = i1y;
return 1;
}
// Figure out which point is closer to the circle
if (dist1 < dist2 ) {  //&& cr >= dist2

p1.x = L2.x;
p1.y = L2.y;
return 1;

} if (dist1>dist2 ) {

p1.x = L1.x;
p1.y = L1.y;
return 1;
}
if (dist4 < dist3 || dist5 < dist3) { //2 solutions

p1.x = i1x;
p1.y = i1y;
p2.x = i2x;
p2.y = i2y;

return 2;
} else {
return 0;

}
}
}
}``````

Hi people,

i´ve made some changes and it works more or less, but when the points are outside the circle, the plugin shows 2 values instead of 0.

if anyone has time to look at it, it would be great.

Thanks,

Ari.

``````- region usings
using System;
using System.ComponentModel.Composition;

using VVVV.PluginInterfaces.V1;
using VVVV.PluginInterfaces.V2;
using VVVV.Utils.VColor;
using VVVV.Utils.VMath;

using VVVV.Core.Logging;
- endregion usings

namespace VVVV.Nodes
{
#region PluginInfo
[PluginInfo(Name = "CircleLineIntersect",
Category = "Value",
Help = "Basic template with one value in/out",
Tags = "")]
#endregion PluginInfo
public class ValueCircleLineIntersectNode : IPluginEvaluate
{
#region fields & pins
[Input("CircleCenter")](Input("CircleCenter"))

[Input("Line1")](Input("Line1"))

[Input("Line2")](Input("Line2"))

[Output("Intersection 1 ")](Output("Intersection 1 "))

[Output("Intersection 2 ")](Output("Intersection 2 "))

[Output("Number of Solutions")](Output("Number of Solutions"))

[Import()](Import())
ILogger FLogger;
#endregion fields & pins

//called when data for any output pin is requested
{

for (int i = 0; i < SpreadMax; i++)
{
Vector2D s1;
Vector2D s2;

FSolutionCount[i](i) = CircleLineIntersection(center[i](i), cr[i](i), L1[i](i), L2[i](i) , out s1, out s2);
FIntersection1[i](i) = s1;
FIntersection2[i](i) = s2;
}

}
private int CircleLineIntersection (Vector2D center, double cr, Vector2D L1 , Vector2D L2,  out Vector2D p1, out Vector2D p2)
{
p1 = new Vector2D();
p2 = new Vector2D();

double dx = L2.x - L1.x;
double dy = L2.y - L1.y;
double a = dx * dx + dy * dy;
double b = 2 * (dx * (L1.x - center.x) + dy * (L1.y - center.y));
double c = L1.x * L1.x + L1.y * L1.y + center.x * center.x + center.y * center.y - 2 * (center.x * L1.x + center.y * L1.y)-(cr * cr);
double bb4ac = b * b - 4 * a * c;

double mu1 = (-b + Math.Sqrt(bb4ac)) / (2*a);
double mu2 = (-b - Math.Sqrt(bb4ac)) / (2*a);

double i1x = L1.x + mu1*(dx);
double i1y = L1.y + mu1*(dy);

double i2x = L1.x + mu2*(dx);
double i2y = L1.y + mu2*(dy);

double dist1 = Math.Sqrt[L1.x-center.x)*(L1.x-center.x)+(L1.y-center.y)*(L1.y-center.y](https://vvvv.org/documentation/L1.x-center.x)*(L1.x-center.x)+(L1.y-center.y)*(L1.y-center.y);
double dist2 = Math.Sqrt[L2.x-center.x)*(L2.x-center.x)+(L2.y-center.y)*(L2.y-center.y](https://vvvv.org/documentation/L2.x-center.x)*(L2.x-center.x)+(L2.y-center.y)*(L2.y-center.y);

if  (bb4ac < 0)    // Not intersecting  (bb4ac < 0)
{
return 0;
}

if  (bb4ac==0 )  //1 solution tangent  (bb4ac == 0)
{
p1.x = i1x;
p1.y = i1y;
return 1;
}

if  ( (dist1>=cr & dist2>=cr ))    //2 solutions  (dist1>=cr & dist2>=cr)
{
p1.x = i1x;
p1.y = i1y;
p2.x = i2x;
p2.y = i2y;
return 2;
}
//else {return 0;}

if  ( (dist1>=cr & dist2<=cr))    //1 solution
{
p1.x = i2x;
p1.y = i2y;
return 1;
}
if  ( (dist1<=cr & dist2>=cr))    //1 solution
{
p1.x = i1x;
p1.y = i1y;
return 1;
}

{
return 0;
}
}
}}``````

Finally i found the solution for the 5 cases, in a “finite line - circle intersection”.

Thanks ft for the hint.

Ari.

Finite Line - Circle intersection (11.1 kB)

Is there any way to do this spreadable???

… no text …

Hi Ari,

Its been a while since you posed the question but I recently started looking for the answer too. Andy McW and I went over the plugin to try and figure out a spreadable method and we got a very workable if not perfect solution.

The patch explains why but it ain’t bad.

Here’s the code if you wanna peak:

``````#region usings
using System;
using System.ComponentModel.Composition;

using VVVV.PluginInterfaces.V1;
using VVVV.PluginInterfaces.V2;
using VVVV.Utils.VColor;
using VVVV.Utils.VMath;

using VVVV.Core.Logging;
- endregion usings

namespace VVVV.Nodes
{
#region PluginInfo
[PluginInfo(Name = "IntersectCircles", Category = "2d", Help = "Basic template with one value in/out", Tags = "")](PluginInfo(Name = "IntersectCircles", Category = "2d", Help = "Basic template with one value in/out", Tags = ""))
#endregion PluginInfo
public class C2dIntersectCirclesNode : IPluginEvaluate
{
#region fields & pins
[Input("Centers")](Input("Centers"))

[Output("Intersections")](Output("Intersections"))

[Output("Number of Solutions")](Output("Number of Solutions"))

[Import()](Import())
ILogger FLogger;
#endregion fields & pins

//called when data for any output pin is requested
{

for(int i = 0; i < FIntersections.SliceCount; i++)
{
FIntersections.RemoveAt(i);
}

for (int i = 0; i < SpreadMax; i++)
{
for (int j = i + 1; j < SpreadMax; j++)
{
Vector2D s1;
Vector2D s2;

}
}
}

private int CircleIntersection (Vector2D c1, double c1r, Vector2D c2, double c2r, out Vector2D p1, out Vector2D p2)
{
p1 = new Vector2D();
p2 = new Vector2D();

//Calculate distance between centres of circle
double d = !(c1 - c2);
double m = c1r + c2r;
double n = c1r - c2r;

if (n < 0)
n = n * -1;

//No solns
if ( d > m )
return 0;

//Circle are contained within each other
if ( d < n )
return 0;

//Circles are the same
if ( d == 0 && c1r == c2r )
return 0;

//Solve for a
double a = ( c1r * c1r - c2r * c2r + d * d ) / (2 * d);

//Solve for h
double h = Math.Sqrt( c1r * c1r - a * a );

//Calculate point p, where the line through the circle intersection points crosses the line between the circle centers.
Vector2D p;

p.x = c1.x + ( a / d ) * ( c2.x -c1.x );
p.y = c1.y + ( a / d ) * ( c2.y -c1.y );

//1 soln , circles are touching
if ( d == c1r + c2r )
{
p1 = p;
return 1;
}

//2solns
p1.x = p.x + ( h / d ) * ( c2.y - c1.y );
p1.y = p.y - ( h / d ) * ( c2.x - c1.x );

p2.x = p.x - ( h / d ) * ( c2.y - c1.y );
p2.y = p.y + ( h / d ) * ( c2.x - c1.x );

return 2;
}

}
}
``````

Circle Interesector Demo (25.5 kB)

i´ll try to use the same method to Circle-Line and Line-Line intersections.
could i share it as a contribution?

2d-circle-line-intersections

Thanks a lot.

Ari.

Be our guest!

The idea came from Elias’s ConnectAll))](https://vvvv.org/contribution/connectall">ConnectAll))) dynamic plug-in he did for his tutorial. In it he showed how multiple vectors can be made to analyse each other (the “for j = i+1” bit).

Most of the credit goes to Andy McWilliams and your good self, though, co-opted the ideas into a something usable and lovely.

Looking forward to the lines version!

Hayd

you should replace these lines

``````for(int i = 0; i < FIntersections.SliceCount; i++)
{
FIntersections.RemoveAt(i);
}
``````

with this

``````FIntersections.Clear();
``````

it’s easier to read and has a better run time, as removing them one by one will trigger a shift of all remaining slices each time you remove one slice.

Danke Elias.

Hi Elias,

.Clear method wasn’t recognised.

‘VVVV.PluginInterfaces.V2.ISpread<VVVV.Utils.VMath.Vector2D>’ does not contain a definition for ‘Clear’ and no extension method ‘Clear’ accepting a first argument of type ‘VVVV.PluginInterfaces.V2.ISpread<VVVV.Utils.VMath.Vector2D>’ could be found (are you missing a using directive or an assembly reference?)

whaaat? :p
ok, then replace it with a

``FIntersections.SliceCount = 0;``

Hey guys,
i´m trying to make the multiple finite lines version,
but i don´t know how to feed the plugin with a spread of points instead of 4 points with individual inputs.

Any tip?

thanks.

``````- region usings
using System;
using System.ComponentModel.Composition;

using VVVV.PluginInterfaces.V1;
using VVVV.PluginInterfaces.V2;
using VVVV.Utils.VColor;
using VVVV.Utils.VMath;

using VVVV.Core.Logging;
- endregion usings

namespace VVVV.Nodes
{
#region PluginInfo
[PluginInfo(Name = "MultipleLinesIntersect", Category = "Value", Help = "2 lines intersect", Tags = "")](PluginInfo(Name = "MultipleLinesIntersect", Category = "Value", Help = "2 lines intersect", Tags = ""))
//Source:
//http://paulbourke.net/geometry/lineline2d/
//Credits:
//Lasal 2011

#endregion PluginInfo
public class Value2LinesIntersectNode : IPluginEvaluate
{
#region fields & pins

// Could it be possible to use a spread of points?

[Input("P1")](Input("P1"))

[Input("P2")](Input("P2"))

[Input("P3")](Input("P3"))

[Input("P4")](Input("P4"))

[Output("Intersection")](Output("Intersection"))

[Output("Number of Solutions")](Output("Number of Solutions"))

[Import()](Import())
ILogger FLogger;
#endregion fields & pins

//called when data for any output pin is requested
{

for(int i = 0; i < FIntersection.SliceCount; i++)
{
FIntersection.RemoveAt(i);
}

for (int i = 0; i < SpreadMax; i++)
{
for (int j = i + 1; j < SpreadMax; j++)
{
Vector2D s1;
Vector2D s2;

//How to use 10 variables? P1[j](j), P2[j](j), P3[j](j), P4[j](j)

FSolutionCount[i](i) = LinesIntersection( P1[i](i), P2[i](i), P3[i](i), P4[i](i), out s1, out s2);

}

}

}
private int LinesIntersection ( Vector2D P1 , Vector2D P2, Vector2D P3 , Vector2D P4, out Vector2D so1, out Vector2D so2)
{
so1 = new Vector2D();
so2 = new Vector2D();

// Denominator for ua and ub are the same, so store this calculation
double d =
(P4.y - P3.y) * (P2.x - P1.x)
-
(P4.x - P3.x) * (P2.y - P1.y);

//n_a and n_b are calculated as seperate values for readability
double n_a =
(P4.x - P3.x) * (P1.y - P3.y)
-
(P4.y - P3.y) * (P1.x - P3.x);

double n_b =
(P2.x - P1.x) * (P1.y - P2.y)
-
(P2.y - P1.y) * (P1.x - P2.x);

// Calculate the intermediate fractional point that the lines potentially intersect.
double ua = n_a / d;
double ub = n_b / d;

double   SX = P1.x + (ua * (P2.x - P1.x));
double   SY = P1.y + (ua * (P2.y - P1.y));

if (d == 0)   // Parallel lines.
{
return 0;
}

if (SX < P1.x & SX < P2.x |
SY < P1.y & SY < P2.y |
SX > P1.x & SX > P2.x |
SY > P1.y & SY > P2.y )
// No finite lines intersecting, delete this for infinite lines Intersection.
{
return 0;
}

// than 0 the lines would need to be longer to intersect.
if (ua >= 0d && ua <= 1d && ub >= 0d && ub <= 1d)
{
so1.x = SX;
so1.y = SY;
return 1;
}

{
return 0;
}
}
}}``````

I think Input 1 could be “line start(vector2D)” and Input 2 “line end(vector2D).”

Then you can compare the spread of lines

``````j = i + 1;
line1[i](i); line2[j](j);
``````

(Pardon my lack of correct formatting, and the fact I may be wrong)

Hayd

PS thanks Elias

Bam:

``````- region usings
using System;
using System.ComponentModel.Composition;

using VVVV.PluginInterfaces.V1;
using VVVV.PluginInterfaces.V2;
using VVVV.Utils.VColor;
using VVVV.Utils.VMath;

using VVVV.Core.Logging;
- endregion usings

namespace VVVV.Nodes
{
#region PluginInfo
[PluginInfo(Name = "MultipleLinesIntersect", Category = "Value", Help = "2 lines intersect", Tags = "")](PluginInfo(Name = "MultipleLinesIntersect", Category = "Value", Help = "2 lines intersect", Tags = ""))
//Source:
//http://paulbourke.net/geometry/lineline2d/
//Credits:
//Lasal 2011

#endregion PluginInfo
public class Value2LinesIntersectNode : IPluginEvaluate
{
#region fields & pins

// Could it be possible to use a spread of points?

[Input("Line Start")](Input("Line Start"))

[Input("Line End")](Input("Line End"))

[Output("Intersection")](Output("Intersection"))

[Output("Number of Solutions")](Output("Number of Solutions"))

[Import()](Import())
ILogger FLogger;
#endregion fields & pins

//called when data for any output pin is requested
{

for(int i = 0; i < FIntersection.SliceCount; i++)
{
FIntersection.SliceCount = 0;
}

for (int i = 0; i < SpreadMax; i++)
{
for (int j = i + 1; j < SpreadMax; j++)
{
Vector2D s1;
Vector2D s2;

//How to use 10 variables? P1[j](j), P2[j](j), P3[j](j), P4[j](j)

FSolutionCount[i](i) = LinesIntersection( P1[i](i), P2[i](i), P1[j](j), P2[j](j), out s1, out s2);

}

}

}
private int LinesIntersection ( Vector2D P1 , Vector2D P2, Vector2D P3 , Vector2D P4, out Vector2D so1, out Vector2D so2)
{
so1 = new Vector2D();
so2 = new Vector2D();

// Denominator for ua and ub are the same, so store this calculation
double d =
(P4.y - P3.y) * (P2.x - P1.x)
-
(P4.x - P3.x) * (P2.y - P1.y);

//n_a and n_b are calculated as seperate values for readability
double n_a =
(P4.x - P3.x) * (P1.y - P3.y)
-
(P4.y - P3.y) * (P1.x - P3.x);

double n_b =
(P2.x - P1.x) * (P1.y - P2.y)
-
(P2.y - P1.y) * (P1.x - P2.x);

// Calculate the intermediate fractional point that the lines potentially intersect.
double ua = n_a / d;
double ub = n_b / d;

double   SX = P1.x + (ua * (P2.x - P1.x));
double   SY = P1.y + (ua * (P2.y - P1.y));

if (d == 0)   // Parallel lines.
{
return 0;
}

if (SX < P1.x & SX < P2.x |
SY < P1.y & SY < P2.y |
SX > P1.x & SX > P2.x |
SY > P1.y & SY > P2.y )
// No finite lines intersecting, delete this for infinite lines Intersection.
{
return 0;
}

// than 0 the lines would need to be longer to intersect.
if (ua >= 0d && ua <= 1d && ub >= 0d && ub <= 1d)
{
so1.x = SX;
so1.y = SY;
return 1;
}

{
return 0;
}
}
}}``````

Gets a little upset if I try to setup a line one axis going along a zero co-ordinates, but seems okay otherwise. Any ideas how to avoid that?

Hayd

Line Intersection Demo with Plugin (23.7 kB)