Aлгоритъм

Здравейте!

Нещо запекох доста яко на 1 алгоритъм, та се надявам някой да е попадал на нещо подобно от вас.

Значи имам колекция от отсечки в равнината.Съхраняват се в База(т.е пазя начална(x,y) и крайна(x,y) точка на всяка отсечка - не че има значение коя е начална) Всичко е в първи квадрант - положителни координати.

Искам да намеря най-близката отсечка до дадена точка(прозволно избрана) от тази равнина.

Същия проблем имам и с най-близка точка, но там съм скалъпил някакъв алгоритъм който действа отноително бързо.

Нали се досещате, че усера ще цъка върху графика, а аз трябва да се досетя къде точно е искал да цъкне

ако бързодействието е от значение (съмнявам се) то направи си квадратно дърво - делиш екрана, гледаш в секи квадрат колко отсечки има, ако са повече от 4 да речем, делиш пак, и така рекурсивно. най-тежкото тук е определяне дали отсечката и квадрата имат обща точка.
ако скороста не ти е от значение, какъв е проблема? отсечката е с краища а,б (2д вектори) точката е р. вземаш права, с направление (а.у-б.у,б.х-а.х) и минаваща през точка р, намираш пресечницата и с правата а-б, за предпочитане в параметричен вид. гледаш параметъра дали е между нула и 1, ако да, тогава пресечницата е най-близка, ако не, то един от двата краища е най-близък. и така за всички отсечки.

Ставаше въпрос за селектиране на отсечка от полигон. Не сме правили оптимизации за двоично делене на равнината, щото отсечките не бяха много.
Тук проблемите са два:

1. Намира ли се точката някъде по направлението перпендикулярно на отсечката, или е в страни.
2. Разстоянието от точката до правата на отсечката.

(2) е елементарно: заместваш точката в уравнението на отсечката и взимаш модул.
dx = x1-x0
dy = y1-y0
g: dy.x - dx.y + dx.y0 - dy.x0
демек матрицата:
| x-x0 y-y0 |
| dx dy |
За съжаление резултатът трябва да се нормализира за да не се получават различни числа при отсечки с различна дължина. Т.е. трябва накрая да разделиш на sqrt(dx^2+dy^2), или ако ако не ти пука точно колко е, а само сравняваш може и без корен да минеш.

За (1) ти трябват две прави, перпендикулярни на отсечката през крайните точки. Техните уравнения са почти като на първата, но с малко разместени вектори. Нещо от сорта:

g0:
| x-x0 y-y0 |
| -dy dx |

g1:
| x1-x y1-y |
| -dy dx |

Ще поекспериментираш и ще ги нацелиш. Всъщност нещата могат да се направят с точност до знак. Ако правилно си задал g0 и g1 трябва точка, която лежи на направлението да има различни знаци на ориентираното разстояние.

Демек във вид на код изглежда така:

if( g1(P)*g2(P) < 0 )
{
Смяташ g(P), нормализираш и сравняваш с досегашните резултати. Поддържаш рекорд.
}else{
На мен това не ми е трябвало, но ако ти трябва взимаш правата с по-малкото по модул нормализирано разстояние и смяташ разстоянието до нейната точка от отсечката ( както се разбрахме без корена ).
}


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Ами ако има една точка, която съвпада с началната точка на отсечката и друга, която съвпада с последната, коя от двете е по-близо?

Ми то човека го интересува Точката до коя отсечка се намира.
Все едно се опитваш да местиш отсечките с мишката.
И трябва да разбереш като цъкне някъде юзъра коя отсечка да прихванеш.

Bеer? Mоre?
Плацебото

Ми то колегата май го е написал горе, но не много ясно. Номера е да направиш от отсечката правоъгълник и от там нататаък вече е ясно.