Обсуждение: Distance from point to box

Поиск
Список
Период
Сортировка

Distance from point to box

От
Alexander Korotkov
Дата:
Hackers,

while reading code written by my GSoC student for knn-spgist I faced many questions about calculation distance from point to box.

1) dist_pb calls close_pb which calls on_pb, dist_ps_internal, close_ps and so on. So, it's very complex way to calculate very simple value. I see this way has some mathematical beauty, but is it acceptable in practice?

2) computeDistance in knn-gist uses it's own quite simplified implementation of this calculation. But why has it own implementation instead on simplifying dist_pb?

3) computeDistance implementation looks still very complex for me. Right way (simple and fast) to calculate point to box distance seems for me to be so:

double dx = 0.0, dy = 0.0;

if (point->x < box->low.x)
    dx = box->low.x - point->x;
if (point->x > box->high.x)
    dx = point->x - box->high.x;
if (point->y < box->low.y)
    dy = box->low.y - point->y;
if (point->y > box->high.y)
    dy = point->y - box->high.y;
return HYPOT(dx, dy);

I feel myself quite tangled.
Could anybody clarify it for me? Did I miss something? Thanks.

------
With best regards,
Alexander Korotkov. 

Re: Distance from point to box

От
Fabien COELHO
Дата:
> double dx = 0.0, dy = 0.0;
>
> if (point->x < box->low.x)
>    dx = box->low.x - point->x;
> if (point->x > box->high.x)
>    dx = point->x - box->high.x;
> if (point->y < box->low.y)
>    dy = box->low.y - point->y;
> if (point->y > box->high.y)
>    dy = point->y - box->high.y;
> return HYPOT(dx, dy);
>
> I feel myself quite tangled.
> Could anybody clarify it for me? Did I miss something? Thanks.

ISTM that you miss the projection on the segment if dx=0 or dy=0.

-- 
Fabien.

Re: Distance from point to box

От
Alexander Korotkov
Дата:
On Wed, Jul 30, 2014 at 4:06 PM, Fabien COELHO <coelho@cri.ensmp.fr> wrote:

double dx = 0.0, dy = 0.0;

if (point->x < box->low.x)
   dx = box->low.x - point->x;
if (point->x > box->high.x)
   dx = point->x - box->high.x;
if (point->y < box->low.y)
   dy = box->low.y - point->y;
if (point->y > box->high.y)
   dy = point->y - box->high.y;
return HYPOT(dx, dy);

I feel myself quite tangled.
Could anybody clarify it for me? Did I miss something? Thanks.

ISTM that you miss the projection on the segment if dx=0 or dy=0.

I don't need to find projection itself, I need only distance. When dx = 0 then nearest point is on horizontal line of box, so distance to it is dy. Same when dy = 0. When both of them are 0 then point is in the box.

------
With best regards,
Alexander Korotkov.  

Re: Distance from point to box

От
Fabien COELHO
Дата:
>> ISTM that you miss the projection on the segment if dx=0 or dy=0.
>
> I don't need to find projection itself, I need only distance. When dx = 0
> then nearest point is on horizontal line of box, so distance to it is dy.
> Same when dy = 0. When both of them are 0 then point is in the box.

Indeed. I thought that the box sides where not parallel to the axis, but 
they are. So I do not see why it should be more complex. Maybe they is a 
general algorithm which works for polygons, and they use it for boxes?

-- 
Fabien.

Re: Distance from point to box

От
Alexander Korotkov
Дата:
On Wed, Jul 30, 2014 at 7:26 PM, Fabien COELHO <coelho@cri.ensmp.fr> wrote:

ISTM that you miss the projection on the segment if dx=0 or dy=0.

I don't need to find projection itself, I need only distance. When dx = 0
then nearest point is on horizontal line of box, so distance to it is dy.
Same when dy = 0. When both of them are 0 then point is in the box.

Indeed. I thought that the box sides where not parallel to the axis, but they are. So I do not see why it should be more complex. Maybe they is a general algorithm which works for polygons, and they use it for boxes?

Yeah, this answers question #1, but not #2 and #3 :)

------
With best regards,
Alexander Korotkov.