Solved

# Distance between a point and an object

Posted on 2004-09-09
812 Views
Say I have a group of line segments represented by a set of points
What would be the best way of calculating the closest distance between them?
Its used for selecting different objects.

Similarly how would you check if a point lines within an area?
0
Question by:spiffles
• 2
• 2
• 2
• +2

LVL 45

Expert Comment

ID: 12024238
Hi spiffles,

Are you looking for smallest distance between any two lines in the set of line segments or closest neighbour for all line segments.

Checking a point lying within an area is realtively simple ... What does the area look like? If it is rectangularor square, then checking

max_x >= point_x >= min_x AND max_y >= point_y >= min_y

will be sufficient ... You can ofcourse extrapolate it to as many dimensions as you like ...

Otherwise, above can server as a preliminary check and you can draw a ray from the given point to an edge or point on the perimeter of the area ... If the ray intersects the perimeter twice, then point is external else the point is internal

cheers
sunnycoder
0

Author Comment

ID: 12040519
Line Feature = Group of points which result in a non enclosed feature
I have a array of these line features and I'm trying to calculate the distance
between a position that a user left clicks and all other line features.

Its used for selecting a specific line feature.
Any ideas?
0

LVL 45

Accepted Solution

sunnycoder earned 55 total points
ID: 12041307
>Line Feature = Group of points which result in a non enclosed feature
From the question "Similarly how would you check if a point lines within an area?" If there no closed area, how do you define an area?

>I have a array of these line features and I'm trying to calculate the distance
>between a position that a user left clicks and all other line features.
Ok, so you are looking to find distance between one fixed point and all other lines you have. Right?
check these links ... they have figures that can explain it better

http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html
http://astronomy.swin.edu.au/~pbourke/geometry/pointline/
0

LVL 3

Expert Comment

ID: 12067141
you could employ some sort of binary shadder tree (left/right side distinctinon - like bsp ) to speed up the lookup (test distance on a subgrup - traceing a tree might be cheaper thean evaluating the whole ... especialy for large, and balanced trees !)

take a look at any gamedev (like gamedev.net) portal to get familiar with this (bsp) idea ...

and if there are only few ( let say hundred of lines to test) dont care but it... it might not be worth coding btree for that purpse....

0

LVL 3

Expert Comment

ID: 12067223
oh.. nad bout the area... if the area is defineid as a room (area must be closed... it's not area when it's not closed)where walls are vectors ( they have an "extra" direction) you can draw it as a set of vectors that point each others ends ( like a chain of vectors) ...now depending on the directon they tend to point ( clockwise/counterclockwise) if your evaluated point is on the right(clockwise)/left(counterclockwise) side of them all it's inside the area described by them ....

i might be bubbling a bit.... dont worry it's all a part of geral bsp usage idea, so any bsp howto covers basics of this problem as well :)
0

LVL 3

Expert Comment

ID: 12082076
if your lines  are already objects than you could give them a region around these lines
(maybe about 3 pixels in each direction).
and with the PtInRegion api function you can easy check if your mouseclick was in the lineregion and select it
0

LVL 9

Expert Comment

ID: 12129572
very well known analogy to this problem is for points instead of for lineFeatures. the solution is to divide the universe (= your drawing area) into polygonal regions and associate each region with unique lineFeature
the criteria is that any point lying in a particular region would be closer to the associated lineFeature than any other lineFeature.
and when the user clicks, check if the click was within that region. if yes then select that particular line
0

LVL 9

Expert Comment

ID: 12129598
just thought of a better idea. use gandalf's method to create lineregions. but these regions will overlap around points of intersection. if click is within a intersection region then you need additional checks to see which lineFeature is closer. then use the above method to divide the the region around intersection into polygons and ...
0

LVL 3

Expert Comment

ID: 12140352
this is a delphi implementation
it creates lineobjects with regions that you can drag around after
dropping on a paintbox. you should be able to identify the windows api
calls that have been used  (i.e.:   if PtInRegion(AryLineObj[i].hRegion, X, Y) then...)
to check on which object has been clicked.

unit Unit1;

interface

uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, ExtCtrls, Buttons, Math;

type

TLineObj = Record
ObjType: Integer;
BeginPt, EndPt: TPoint;
aColor, hRegion: Cardinal;
PenWidth: Byte;
end;

TOffSetRec = Record
RefX, RefY, BeginX, BeginY, EndX, EndY: Integer;
end;

TForm1 = class(TForm)
PaintBox1: TPaintBox;
sbut_DrawLine: TSpeedButton;
sbut_SelectLine: TSpeedButton;
ColorEdit: TEdit;
procedure FormCreate(Sender: TObject);
procedure FormDestroy(Sender: TObject);
procedure PaintBox1Paint(Sender: TObject);
procedure sbut_DrawLineClick(Sender: TObject);
procedure sbut_SelectLineClick(Sender: TObject);
procedure PaintBox1MouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
procedure PaintBox1MouseUp(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
procedure PaintBox1MouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
private
PB_Bmp: TBitmap;
LineDraw: Boolean;
ReLine: Byte;
DrawStart, DrawPnt: TPoint;
AryLineObj: Array of TLineObj;
OffSetRec1: TOffSetRec;
ObjType, SelNum: Integer;
procedure SetLineRgn(Index: Cardinal);
procedure SetNotPen;

{ Private-Deklarationen }
public
{ Public-Deklarationen }
end;

var
Form1: TForm1;

implementation

{\$R *.DFM}

{ TForm1 }

procedure TForm1.SetLineRgn(Index: Cardinal);
var aRgn, bRgn, cRgn: Cardinal;
rWid: Integer;
aryPnt: Array[0..4] of TPoint;
begin
{this procedure sets the region for to Hit Test for each Line
I will not explain the Trigonomety used here}
rWid := AryLineObj[Index].PenWidth+3;
{rWid is set to 3 More than the line width, , the 3 is the amount of Pixels on
each side of the line added to the Hit test area}
if DrawStart.y-DrawPnt.y = 0 then
DrawPnt.y := DrawPnt.y +1;
Angle1 := 180 * (1 + ArcTan2(DrawStart.y-DrawPnt.y, DrawStart.x-DrawPnt.x) / Pi);
aryPnt[0].x := Round(DrawPnt.x-(Cos1*rWid));
aryPnt[0].y := Round(DrawPnt.y-(Sin1*rWid));
aryPnt[3].x := Round(DrawStart.x-(Cos1*rWid));
aryPnt[3].y := Round(DrawStart.y-(Sin1*rWid));
aryPnt[1].x := Round(DrawPnt.x-(Cos1*rWid));
aryPnt[1].y := Round(DrawPnt.y-(Sin1*rWid));
aryPnt[2].x := Round(DrawStart.x-(Cos1*rWid));
aryPnt[2].y := Round(DrawStart.y-(Sin1*rWid));
aryPnt[4] := aryPnt[0];
aRgn := CreatePolygonRgn(aryPnt, 5, WINDING);
bRgn := CreateEllipticRgn(DrawStart.x-rWid+1, DrawStart.y-rWid,
DrawStart.x+rWid+1, DrawStart.y+rWid);
cRgn := CreateEllipticRgn(DrawPnt.x-rWid, DrawPnt.y-rWid,
DrawPnt.x+rWid, DrawPnt.y+rWid);
CombineRgn(bRgn, bRgn, cRgn, RGN_OR);
CombineRgn(aRgn, aRgn, bRgn, RGN_OR);
AryLineObj[Index].hRegion := aRgn;
DeleteObject(bRgn);
DeleteObject(cRgn);
end;

procedure TForm1.SetNotPen;
begin
PaintBox1.Canvas.Pen.Color := clBlack;
PaintBox1.Canvas.Pen.Style := psSolid;
PaintBox1.Canvas.Pen.Width := 1;
PaintBox1.Canvas.Pen.Mode := pmNot;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
SelNum := -1;
ObjType := -1;
ReLine := 0;
LineDraw := False;
{the PB_Bmp is the background for the Paint Box
but you can just FillRect if you want to just erase the background
of the PaintBox}
PB_Bmp := TBitmap.Create;
PB_Bmp.Canvas.Brush.Color := \$CC3333;
PB_Bmp.Canvas.Brush.Style := bsDiagCross;
PB_Bmp.Width := PaintBox1.Width;
PB_Bmp.Height := PaintBox1.Height;
PB_Bmp.Canvas.Font.Name := 'Arial';
PB_Bmp.Canvas.Font.Size := 36;
PB_Bmp.Canvas.TextOut(40,100, 'Paint Box');
end;

procedure TForm1.FormDestroy(Sender: TObject);
var i: Integer;
begin
for i := 0 to High(AryLineObj) do
DeleteObject(AryLineObj[i].hRegion);
{Always Free the System Regions}
FreeAndNil(PB_Bmp);
end;

procedure TForm1.PaintBox1Paint(Sender: TObject);
var i: Integer;
begin
{this will paint the PaintBox, the Backgroung is bitmap PB_Bmp}
PaintBox1.Canvas.Draw(0,0,PB_Bmp);

{if SelNum is zero or above, then a Line is selected, and there will
be a Border drawn around it to show that it is selected}
if SelNum > -1 then
with PaintBox1.Canvas, AryLineObj[SelNum] do
begin
Pen.Color := clBlack;
Pen.Mode := pmNot;
Pen.Width := PenWidth+5;
MoveTo(BeginPt.x, BeginPt.y);
LineTo(EndPt.x, EndPt.y);
Ellipse(BeginPt.x-5, BeginPt.y-5, BeginPt.x+5, BeginPt.y+5);
Ellipse(EndPt.x-5, EndPt.y-5, EndPt.x+5, EndPt.y+5);
end;
PaintBox1.Canvas.Pen.Mode := pmCopy;

{you will need to cycle through ALL of the AryLineObj array
to draw all of the Lines, in there position with their color and width}
for i := 0 to High(AryLineObj) do
with PaintBox1.Canvas, AryLineObj[i] do
begin
Pen.Color := aColor;
Pen.Width := PenWidth;
MoveTo(BeginPt.x, BeginPt.y);
LineTo(EndPt.x, EndPt.y);
end;

PaintBox1.Canvas.Pen.Color := clBlack;
PaintBox1.Canvas.Pen.Width := 1;
PaintBox1.Canvas.Pen.Style := psSolid;
{if ReLine is more than zero then the line is being recreated
(sized, moved, angled)}
if ReLine > 0 then
PaintBox1.Canvas.Pen.Mode := pmNot;
end;

procedure TForm1.sbut_DrawLineClick(Sender: TObject);
begin
{you click this sbut_DrawLine button to set the PaintBox to Create
a NEW Line Object, it will remain in this Creation
State, untill you click the sbut_Select button}
PaintBox1.Cursor := crDrag;
ObjType := 2;
{ObjType 2 is what I use for drawing lines}
SelNum := -1;
{if SelNum is -1 then there is NO selected line}
PaintBox1Paint(PaintBox1);
end;

procedure TForm1.sbut_SelectLineClick(Sender: TObject);
begin
{click this button to turn OFF the New Line Creation,
it sets the "Mode" of the paintBox to Select, which means
that you can click on an individual Line (within 3 pixels
of the line) and it will become Selected, and Have a Selected
"Border" added to the line, you can ten drag and drop that
selected line on it's center area and "Move" the line to another
place on the paintbox, OR you can drag and Drop one of it's Ends
to Redraw the line to a new length or angle}
PaintBox1.Cursor := crArrow;
ObjType := -1;
SelNum := -1;
ReLine := 0;
PaintBox1Paint(PaintBox1);
end;

procedure TForm1.PaintBox1MouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
var i: Integer;
inPnt: TPoint;
inRect: TRect;
begin
{this mouse down is where you detect where to start drag and drop operations}
if Button = mbLeft then
begin
if ObjType = 2 then
begin
{ObjType = 2 means that a new Line is being created}
DrawStart.x := X;
DrawStart.y:= Y;
DrawPnt.x := X;
DrawPnt.y := Y;
LineDraw := True;
{set LineDraw to True so MouseMove will draw a line}
SetNotPen;
Exit;
end;

{next I test to see if the Cursor is in the Region of a Line by
for looping through ALL of the AryLineObj array and testing for
PtInRegion, and setting the OffSetRec1 with the Cursor OffSets
for the Line}
for i := High(AryLineObj) downTo 0 do
begin
if PtInRegion(AryLineObj[i].hRegion, X, Y) then
begin
ReLine := 1;
inPnt.x := X;
inPnt.y := Y;
with OffSetRec1, AryLineObj[i] do
begin
RefX := X;
RefY := Y;
BeginX := BeginPt.x - X;
BeginY := BeginPt.y - Y;
EndX := EndPt.x - X;
EndY := EndPt.y - Y;
end;

with AryLineObj[i] do
begin
DrawStart := BeginPt;
DrawPnt := EndPt;
inRect := Rect(BeginPt.x-6, BeginPt.y-6, BeginPt.x+6, BeginPt.y+6);
end;
{I need to test and see if the cursor is over an End Point of the line
the inRect is a Rectangle around an End Point, and test with PtInRect}
if PtInRect(inRect, inPnt) then
ReLine := 2 else
begin
with AryLineObj[i] do
inRect := Rect(EndPt.x-6, EndPt.y-6, EndPt.x+6, EndPt.y+6);
if PtInRect(inRect, inPnt) then
ReLine := 3;
end;

if i <> SelNum then
begin
{I set the SelNum to i to hold the Selected Line Index in the AryLineObj}
SelNum := i;
PaintBox1Paint(PaintBox1);
end else
SetNotPen;
Break;
end;
end;
end;
end;

procedure TForm1.PaintBox1MouseUp(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
begin
{this Mouse Up means that the drag and drop operation is finished}

{if ReLine is above 0 then the line is being ReDrawn, Changed}
with OffSetRec1 do
if ReLine > 0 then
if (RefX > X +4) or (RefX < X -4) or
(RefY > Y +4) or (RefY < Y -4) then
begin
AryLineObj[SelNum].BeginPt := DrawStart;
AryLineObj[SelNum].EndPt := DrawPnt;
{reset the Lines BeginPt, EndPt and region}
SetLineRgn(SelNum);
PaintBox1Paint(PaintBox1);
end;

{if DrawLine is True, then a NEW Line object is Being created}
if LineDraw and ((DrawStart.x > X +4) or (DrawStart.x < X -4) or
(DrawStart.y > Y +4) or (DrawStart.y < Y -4)) then
begin
SetLength(AryLineObj, Length(AryLineObj)+1);
{increase your Dynamic array with SetLength}
with PaintBox1.Canvas, AryLineObj[High(AryLineObj)] do
begin
Pen.Mode := pmCopy;
BeginPt := DrawStart;
EndPt := DrawPnt;
aColor := StrToIntDef('\$'+ColorEdit.Text, 0);
{AryLineObj aColor is taken from Hex Numbers in a TEdit ColorEdit}
else
PenWidth := 1;
{RadioGroup1 has 6 Radio Buttons in it, , ,  One, Two, Three, Four
Five, Six}
SetLineRgn(High(AryLineObj));
{now draw the New Line on the PaintBox}
Pen.Color := aColor;
Pen.Width := PenWidth;
MoveTo(BeginPt.x, BeginPt.y);
LineTo(EndPt.x, EndPt.y);
end
end;
LineDraw := False;
ReLine := 0;
end;

procedure TForm1.PaintBox1MouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
var inPnt: TPoint;
inRect: TRect;
begin
{you will need to do the repetative "NOT" Line drawing in the PaintBox MouseMove}

{if ReLine is above zero then an Existing line is being ReDrawn}
with OffSetRec1 do
if (ReLine > 0) and ((RefX > X +4) or (RefX < X -4) or
(RefY > Y +4) or (RefY < Y -4)) then
begin
PaintBox1.Canvas.MoveTo(DrawStart.x, DrawStart.y);
{draw the NOT Line to Erase the previous Not Line draw}
PaintBox1.Canvas.LineTo(DrawPnt.x, DrawPnt.y);
case Reline of
2: begin
{Reline = 2 means that the line's Begin Point is being moved
you must add the OffSetRec1 BeginX}
DrawStart.x := X + BeginX;
DrawStart.y := Y + BeginY;
end;
3: begin
{Reline = 3 means that the line's End Point is being moved}
DrawPnt.x := X + EndX;
DrawPnt.y := Y + EndY;
end;
else begin
{Reline = 1 means that the whole Line is being moved
you must add the OffSetRec1 BeginX, EndX}
DrawStart.x := X + BeginX;
DrawStart.y := Y + BeginY;
DrawPnt.x := X + EndX;
DrawPnt.y := Y + EndY;
end;
end;
PaintBox1.Canvas.MoveTo(DrawStart.x, DrawStart.y);
PaintBox1.Canvas.LineTo(DrawPnt.x, DrawPnt.y);
Exit;
end;

if LineDraw and ((DrawStart.x > X +4) or (DrawStart.x < X -4) or
(DrawStart.y > Y +4) or (DrawStart.y < Y -4)) then
with PaintBox1.Canvas do
begin
MoveTo(DrawStart.x, DrawStart.y);
{draw the NOT Line to Erase the previous Not Line draw}
LineTo(DrawPnt.x, DrawPnt.y);
DrawPnt.x := X;
DrawPnt.y := Y;
MoveTo(DrawStart.x, DrawStart.y);
{draw New NOT Line}
LineTo(DrawPnt.x, DrawPnt.y);
Exit;
end;

if SelNum < 0 then Exit;
inPnt.x := X;
inPnt.y := Y;
with AryLineObj[selNum] do
inRect := Rect(BeginPt.x-5, BeginPt.y-5, BeginPt.x+5, BeginPt.y+5);
{test to see if the Cursor is over the Select Line's End Point
and if it is change the Cursor to give the user an indication}
if PtInRect(inRect, inPnt) then
PaintBox1.Cursor := crSizeAll
else
begin
with AryLineObj[selNum] do
inRect := Rect(EndPt.x-5, EndPt.y-5, EndPt.x+5, EndPt.y+5);
if PtInRect(inRect, inPnt) then
PaintBox1.Cursor := crSizeAll else
PaintBox1.Cursor := crDefault;
end;
end;

end.
0

## Featured Post

### Suggested Solutions

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I was…
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…
This demo shows you how to set up the containerized NetScaler CPX with NetScaler Management and Analytics System in a non-routable Mesos/Marathon environment for use with Micro-Services applications.