Solved

Distance between a point and an object

Posted on 2004-09-09
9
812 Views
Last Modified: 2013-12-26
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
Comment
Question by:spiffles
  • 2
  • 2
  • 2
  • +2
9 Comments
 
LVL 45

Expert Comment

by:sunnycoder
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

by:spiffles
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

by:
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

by:str_ek
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
Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

 
LVL 3

Expert Comment

by:str_ek
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

by:gandalf_the_white
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

by:jhshukla
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

by:jhshukla
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

by:gandalf_the_white
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;
    RadioGroup1: TRadioGroup;
    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;
  Rad1, Cos1, Sin1, Angle1: Extended;
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);
  Rad1 := DegToRad(Angle1+90);
  SinCos(Rad1, Sin1, Cos1);
  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));
  Rad1 := DegToRad(Angle1-90);
  SinCos(Rad1, Sin1, Cos1);
  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}
        if RadioGroup1.ItemIndex > -1 then
           PenWidth := RadioGroup1.ItemIndex + 1
        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

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

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.

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

24 Experts available now in Live!

Get 1:1 Help Now