Figuring the intersection of a line

Figuring the intersection of a line

Post by Bryce K. Nielse » Sat, 28 Jun 2003 14:29:52



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

Post by Ma?l H?r » Sat, 28 Jun 2003 23:15:25


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

Post by newsgroups.borland.co » Mon, 30 Jun 2003 00:32:43


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

 
 
 

1. Intersection of line segment with bounding box or other line segment

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

2. File format needed!

3. sweep line algorithm for line intersection

4. 3D modelers for UNIX

5. How to: (3d) line with line intersection?

6. Have any of you done embroidery?

7. Intersection of Point-line and line....

8. Taron - MSI - copyright?

9. Need line/line intersection algorithm

10. Human Animation Demo on - line - - Ally McBeal : Stick Figure Animation - - ( Java )

11. HELP:Algorithm for intersection of line and volume

12. Intersection of line and volume

13. intersection of a line with an arbitrary surface