## Figuring the intersection of a line

### Figuring the intersection of a line

Forgive my .NET references here, but I'm using .NET's "GDI+" in a project
and seeing the great help I've gotten on the Delphi boards (and the little
help
I find on the MS boards), I figured I'd pose my question here:

I'm using a .NET Graphics object (similar to a TCanvas) to draw some lines
on a UserControl and I want to figure out when a user clicks on the control,
if they've clicked on one of the painted lines. In the simplest of cases,
I'm
calling Graphics.DrawLine between two points (akin to LineTo()), so I guess
I need some sort of algorithm that can see if a point is an "intersection"
between two other points. Also, to make things more complex, I'm calling
Graphics.DrawCurve, so it's a "curve" that would probably be even
more complex to figure out if the user clicked on the line or not...

-BKN

### Figuring the intersection of a line

Hello Bryce,
I do not use .NET but there has to be something like paths and regions there
two, especially when using GDI+.
I have appended some Delphi-code that detects a line using regions. This
code is also applicable to
curves.
However when using Curves you will have to substract the inner part with
CombineRgn,
else your HitTest will also return true when inside the curve.

General:
=====
Everything drawn on a DC between BeginPath and EndPath
can be converted to a region with PathToRegion.
With the obtained region you can make a hit test using PtInRegion.
This way you know if a point belongs to a geometric object or not.

If you have several lines crossing you will also have to save somewhere
which one is at the highest position (= the last drawn).
So when a point is in RgnLine1 and in RgnLine2, you should activate Line2 as
it was drawn on top of Line1.

Also look in the Windows API for more details about Regions and Paths.

Hope this helps.
Regards Ma?l.

CODE
=====
unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;

type
TForm1 = class(TForm)
Label1: TLabel;
procedure FormCreate(Sender: TObject);
procedure FormDestroy(Sender: TObject);
procedure FormPaint(Sender: TObject);
procedure FormMouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
private
Rgn: HRGN;
public
{ Public-Deklarationen }
end;

var
Form1: TForm1;

implementation

{\$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
begin
BeginPath(Canvas.Handle);
Canvas.Pen.Width := 4;
Canvas.MoveTo(0, 0);
Canvas.LineTo(100, 100);
EndPath(Canvas.Handle);
// if you do not use WidenPath then the Region will
// not use Pen.Width and the resulting region will be to small
WidenPath(Canvas.Handle);
Rgn := PathToRegion(Canvas.Handle);
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
DeleteObject(Rgn);
end;

procedure TForm1.FormPaint(Sender: TObject);
begin
Canvas.Pen.Width := 4;
Canvas.MoveTo(0, 0);
Canvas.LineTo(100, 100);
end;

procedure TForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
const
BoolStr: array[Boolean] of string = ('False', 'True');
begin
Label1.Caption := BoolStr[PtInRegion(Rgn, X, Y)];
end;

end.

### Figuring the intersection of a line

http://www.simdesign.nl/tips/tip001.html

Kind regards, Nils

Quote:> Forgive my .NET references here, but I'm using .NET's "GDI+" in a project
> and seeing the great help I've gotten on the Delphi boards (and the little
> help
> I find on the MS boards), I figured I'd pose my question here:

> I'm using a .NET Graphics object (similar to a TCanvas) to draw some lines
> on a UserControl and I want to figure out when a user clicks on the
control,
> if they've clicked on one of the painted lines. In the simplest of cases,
> I'm
> calling Graphics.DrawLine between two points (akin to LineTo()), so I
guess
> I need some sort of algorithm that can see if a point is an "intersection"
> between two other points. Also, to make things more complex, I'm calling
> Graphics.DrawCurve, so it's a "curve" that would probably be even
> more complex to figure out if the user clicked on the line or not...

> -BKN

Greetings

Working in 2-D, I have a line segment PQ, given by the end point
co-ordinates (Px,Py) and (Qx,Qy), and a bounding box B aligned to the x-y
axes, given by the maximum and minimum co-ordinates (Bx0,Bx1,By0,By1).  The
predicate is "PQ intersects B", i.e some point is common to both PQ and B
(including the border of B).  What is the most efficient way to calculate
the predicate?

I already have the coefficients of the equation of the infinite line through
P and Q in normalised general form, and a formula to calculate the
projection of (x,y) onto this line.  I believe that PQ intersects B iff any
corner of B projected onto PQ lies within the segment PQ and within B.  Is
this optimal?

I further evaluate "(x,y) lies within B" as

(x-Bx0)*(x-Bx1) <= 0 && (y-By0)*(y-B1) <= 0

and "(x,y) lies between P and Q (where (x,y) known to be on the line through
P and Q)"
by a similar formula (since P and Q define the bounding box for line segment
PQ).  Is this optimal?

For the predicate "line segment P1Q1 intersects line segment P2Q2", let
d(P,L) be the perpendicular distance of point P from line L.  I evaluate the
predicate as

d(P1,P2Q2)*d(Q1,P2Q2) <= 0 && d(P2,P1Q1)*d(Q2,P1Q1) <= 0

i.e. endpoints of each line segment are on the opposite sides of the other
line segment.  The special case is d(P1,P2Q2) == d(Q1,P2Q2) == 0, when all I
have proved is that the segments are collinear, and I have to check whether
any endpoint lies within the other segment.  Is this optimal?  It avoids the
problem of special casing small as well as zero determinants.  I get the
point of intersection by interpolating between the endpoints in the ratio of
the d values.

Is there a recommended text for this kind of nuts-and-bolts stuff?

Thanks for your input

Jeff