OPENRNDR & Processing - Circle & line-segment intersection

Circle & line-segment intersection

This example is based on code found in Stack Overflow and it includes a function for finding intersection points between a line segment and a circle.

Processing / Java

Imports
import java.util.List;
PVector p0 = new PVector(100.0, 100.0);
PVector p1 = new PVector(400.0, 400.0);
float circleRadius = 90.0;

void settings() {
  size(640, 480);
}

void draw() {
  background(255);
  fill(#FFAA00, 100);
  stroke(0, 100);
  strokeWeight(2);
  
  PVector circleCenter = new PVector(mouseX, mouseY);
  line(p0.x, p0.y, p1.x, p1.y);
  circle(circleCenter.x, circleCenter.y, circleRadius * 2);

  List<PVector> intersections = intersections(p0, p1, circleCenter, circleRadius);
  for(PVector i : intersections) {
    circle(i.x, i.y, 10);
  }
}

List<PVector> intersections(PVector start, PVector end, PVector circleCenter, float radius) {
  PVector d = PVector.sub(end, start);
  PVector f = PVector.sub(start, circleCenter);
  
  List<PVector> result = new ArrayList<PVector>();

  float a = d.dot(d);
  float b = 2 * f.dot( d );
  float c = f.dot(f) - radius * radius;

  float discriminant = b * b - 4 * a * c;
  if ( discriminant < 0 ) {
    return result;
  } 

  discriminant = sqrt(discriminant);

  float t1 = (-b - discriminant) / (2 * a);
  float t2 = (-b + discriminant) / (2 * a);

  if (t1 >= 0 && t1 <= 1) {
    result.add(PVector.lerp(start, end, t1));
  }

  if (t2 >= 0 && t2 <= 1) {
    result.add(PVector.lerp(start, end, t2));
  }    

  return result;
}

OPENRNDR / Kotlin

Imports
import org.openrndr.application
import org.openrndr.color.ColorRGBa
import org.openrndr.math.Vector2
import org.openrndr.shape.Circle
import org.openrndr.shape.LineSegment
import kotlin.math.sqrt
fun main() = application {
    program {
        val line = LineSegment(100.0, 100.0, 400.0, 400.0)
        var cir = Circle(Vector2.ZERO, 90.0)

        extend {
            drawer.clear(ColorRGBa.WHITE)
            drawer.fill = ColorRGBa.fromHex("FFAA00").opacify(0.4)
            drawer.stroke = ColorRGBa.BLACK.opacify(0.4)
            drawer.strokeWeight = 2.0

            cir = cir.movedTo(mouse.position)
            drawer.lineSegment(line)
            drawer.circle(cir)
            drawer.circles(line.intersections(cir), 10.0)
        }
    }
}

private fun LineSegment.intersections(cir: Circle): List<Vector2> {
    val d = end - start
    val f = start - cir.center

    val result = mutableListOf<Vector2>()

    val a = d.dot(d)
    val b = 2 * f.dot(d)
    val c = f.dot(f) - cir.radius * cir.radius

    var discriminant = b * b - 4 * a * c
    if (discriminant < 0) {
        return result
    }

    discriminant = sqrt(discriminant)

    val t1 = (-b - discriminant) / (2 * a)
    val t2 = (-b + discriminant) / (2 * a)

    if (t1 in 0.0..1.0) {
        result.add(mix(start, end, t1))
    }

    if (t2 in 0.0..1.0) {
        result.add(mix(start, end, t2))
    }

    return result
}
Concept Processing OPENRNDR
geometry and shape classes PVector, PShape Vector2, Vector3, Vector4, Circle, Rectangle, and more, LineSegment, Shape, ShapeContour and more
add methods to existing classes possible using inheritance Kotlin lets you extend a class with new functionality without having to inherit from the class or use any design patterns. In this program we added the method .intersections() to LineSegment.
draw a line between two points line(p0.x, p0.y, p1.x, p1.y); drawer.lineSegment(line) //or
drawer.lineSegment(p0, p1)
mouse position vector new PVector(mouseX, mouseY); mouse.position
draw segment-circle intersections List<PVector> intersections = intersections(p0, p1, circleCenter, circleRadius); for(PVector i : intersections) { circle(i.x, i.y, 10); } drawer.circles( line.intersections(cir), 10.0)
subtract two vectors PVector d = PVector.sub(end, start); val d = end - start
check if variable in given range if (t1 >= 0 && t1 <= 1) if (t1 in 0.0..1.0)
linear interpolation between two vectors PVector.lerp(start, end, pos) mix(start, end, pos)

I like that in OPENRNDR vector data types (representing points in 2D, 3D or 4D) can be used to define shapes, draw them, set colors, call noise functions, etc. For example you can do line(p1, p2) instead of line(p1.x, p1.y, p2.x, p2.y). Those same vectors can easily be combined using +, -, *, / to write very readable expressions, for example line(p1+p2, p1-p2), where p1 and p2 are 2D points.

Note: if you are wondering where do start and end come from in the OPENRNDR example, note that the context of the .intersections() function is the LineSegment class, which luckily has properties called start and end.

Using IntelliJ Idea

In the past, if I needed a function, I would first write the function and only then use it. Now I do it the other way around: I first write the function call including the desired arguments. Idea will highlight it as an error and, by pressing Alt+Enter, it will suggest to create that function.

This not only works for a a typical function call like add(person1, person2) but also for generating operator overloading functions, like person1 + person2 or even person1.add(person2). In all these cases the IDE suggests adding something that will make the code compile.

That is how I generated the LineSegment.intersections() function: I typed line.intersections(cir) and Idea created the empty function which I then populated.

:point_down: Share your questions and comments below | :mag_right: Find other OPENRNDR & Processing posts

2 Likes

If you don’t like repeating the word drawer multiple times, you can do this:

OPENRNDR / Kotlin

extend {
    drawer.run {
        clear(ColorRGBa.WHITE)
        fill = ColorRGBa.fromHex("FFAA00").opacify(0.4)
        stroke = ColorRGBa.BLACK.opacify(0.4)
        strokeWeight = 2.0

        cir = cir.movedTo(mouse.position)
        lineSegment(line)
        circle(cir)
        circles(line.intersections(cir), 10.0)
    }
}

Ten months later I see that the program can be greatly simplified, in part thanks to the built-in intersection calculations. The whole program would look like this now:

imports
import org.openrndr.application
import org.openrndr.color.ColorRGBa
import org.openrndr.color.rgb
import org.openrndr.shape.Circle
import org.openrndr.shape.LineSegment
fun main() = application {
    program {
        val line = LineSegment(100.0, 100.0, 400.0, 400.0)

        extend {
            drawer.run {
                clear(ColorRGBa.WHITE)
                fill = rgb("FFAA00").opacify(0.4)
                stroke = ColorRGBa.BLACK.opacify(0.4)
                strokeWeight = 2.0

                val cir = Circle(mouse.position, 90.0)
                lineSegment(line)
                circle(cir)
                circles(line.contour.intersections(cir.contour).map {
                    it.position
                }, 10.0)
            }
        }
    }
}

Notice that we can query intersections between ShapeContour objects, therefore I convert both line and the cir to contours. That call returns a list of ContourIntersections containing additional information, but in this case we only care about the positions of the intersections, therefore the use of .map {}.

To get rid of a few extra characters I replaced ColorRGBa.fromHex() with rgb() :slight_smile: