hi,

Apologies for the crude diagram; I'm trying to find the point where two lines intersect. I know how to solve this in general, given the line geometry (eg 2 points on either line), but I'd like to avoid having to convert the problem to Cartesian coordinates and back.

Currently I'm working with halfspaces described as: normal direction (in radians) and offset (distance from the origin to a point on the line, moving along the normal).

ie I'd like a function where I plug in the delta angle between normals (will never be >180deg, theta in the diagram) and the two offsets (r1 and r2 in the diagram) and get the intersection point.

Ideally this shouldn't use any transcendental functions, however I suspect a single cos() or sin() is going to be needed.

I don't need the results as cartesian coordinates, for example it might be more natural to express the intersection point as a direction to move along the tangent of the first plane (ie as theta increases from 0 to 180deg, the solution distance would increase from 0 to infinity; when theta is 90deg, the solution would be r2).

I'd like to find a solution which uses this data directly rather than converting the lines to some other form to solve the problem. If needed, I could use unit normal direction instead of angle, so that the halfspaces are described in the more natural “ABC" format.

Please let me know if I'm confused about something, or if this doesn't make sense. I don't want to work directly with vectors since I have convex shapes described as a sorted-by-angle ordered list of [angle,offset] halfspaces.

raigan said:
Ideally this shouldn't use any transcendental functions, however I suspect a single cos() or sin() is going to be needed.

If you really wanted to avoid trig, you would use complex numbers to represent angles. Which is pretty much the same as a 2d vector, and also has the same operations like dot products to calculate intersections conventionally.

raigan said:
I don't need the results as cartesian coordinates, for example it might be more natural to express the intersection point as a direction to move along the tangent of the first plane (ie as theta increases from 0 to 180deg, the solution distance would increase from 0 to infinity; when theta is 90deg, the solution would be r2).

Which would be precisely using the trig functions you don't want (and could avoid) to use:

raigan said:
I don't want to work directly with vectors since I have convex shapes described as a sorted-by-angle ordered list of [angle,offset] halfspaces.

I see, but while it feels elegant to represent convex shapes only using a half space definition, there always comes the point where you have to find their intersections. And you can't avoid the gritty details once you actually work with them.

I've watched several great videos about how you can represent rotations via complex number multiplication, but honestly I still wouldn't know how to go about implementing it. :/

So far I've avoided needing explicit geometry because I've been using k-dops essentially (ie all shapes use the same set of global axes, so support points/vertices are never needed).

I guess what I'm working on is very similar to path rendering: https://developer.nvidia.com/nv-path-rendering

(gha..

This forum gets worse every day, twice it's eaten half of my post!

Anyway, please let me know if you have any recommendations for how to represent the path geometry.

My current approach is basically a mesh represented as a doubly-connected edge list, more or less. Each vertex is a list of wedges; each wedge is the solid angle between adjacent linesegs connected to the vertex. The wedge's local geometry can be described as a set of halfspaces, either their union (concave corner) or intersection (convex corner). This makes it easy to insert bevel planes at joints between two linesegs, for example. But, the wedges (ie the linesegs radiating outward from a given vertex) need to be kept sorted in order, via atan2(), which frankly makes me feel miserable. So I thought, while we're in angle-land, maybe we could just solve all the problems more easily in that space. I guess not!

I'm going to try just explicitly doing the intersections, I only have a few thousand nodes to process and computers are really fast these days. But please let me know if you have any tips or suggestions for a better strategy! :D

raigan said:
I've watched several great videos about how you can represent rotations via complex number multiplication, but honestly I still wouldn't know how to go about implementing it. :/

I use std::complex. Implementing yourself wouldn't be difficult or much work either. I still don't really understand the mathematical background regarding its relation to the paradox sqrt(-1).
While terms like ‘complex plane’ sound quite involved, i really understand it as a 2D vector implementation. Multiplication is is the same math as a 2x2 matrix multiply, where we only need two numbers in case of representing rotations and uniform scale.
It also has convenient trig functions to convert to / from angles, to multiply angles, magnitude, dot product. Just the terminology is a bit fancy, e.g. to get the difference in angle from two complex numbers, you use the division operator iirc. But easy and convenient to use once getting used to that.

It might give you a speedup from using less trig, but it's twice the data than an angle, so it surely depends.

raigan said:
So far I've avoided needing explicit geometry because I've been using k-dops essentially (ie all shapes use the same set of global axes, so support points/vertices are never needed).

Sounds interesting. I think of MC Escher ornaments. Something like that?

raigan said:
But please let me know if you have any tips or suggestions for a better strategy! :D

Maybe some math experts here have ideas.
But likely it depends on context. I just assume you need intersections to generate a final outcome which you can render? You might want to post an image to give people a better idea of what's the goal.

>>Sounds interesting. I think of MC Escher ornaments. Something like that?

It's more like, every shape is the union of N slabs (slab = parallel pair of halfspaces with opposite normals). So for example AABBs are represented as 2 slabs (one along x, one along y); add two diagonal slabs, and now everything is octagons (but, you can also represent right triangles and other shapes as “octagons” with some degenerate 0-sized edges). The math for separating axis tests is incredibly simple, but I guess you're right, ultimately there always needs to be explicit geometry for something or other, alas.

I don't have any screenshots, currently it's a bunch of debug circles that aren't very comprehendable!

About the intersection point of two planes described as an offset+direction from a common point, I could swear that in the past I've calculated it something like this:

point p, offsets ra,rb, unit normals na,nb

intersection point = p + (ra*na + rb*nb)/dot(ra*na,rb*nb)*dot(ra*na,rb*nb)

(note: I don't think this actually works, it's just the form of the formula that I remember: mainly, you don't need to re-normalize the averaged normal, instead you can scale by the inverse of the squared length. Sadly I can't find that code anymore..)

raigan said:
Sadly I can't find that code anymore.

My favourite resource to look up intersection tests (and other stuff): https://github.com/davideberly/GeometricTools/tree/master/GTE/Mathematics​

Intersection files start with ‘Intr’.

(If you can still read this, clicking ‘Link’ button then pasting link there instead directly into the post seems to work to prevent forum bugs ;D )

What is the angle between the lines?

@JoeJ: thanks! IntrLine2Line2.h is just what I need (also thanks for the tip about pasting links)

@Acosix: the angle between the lines is theta, a given (ie known value).