computational geometry - efficient algorithm to find nearest point in a graph that does not have a known equation -

-

i'm asking questions out of curiostity, since quick , dirty implementation seems enough. i'm curious better implementation be.

i have graph of real world data. there no duplicate x values , x value increments @ consistant rate across graph, y data based off of real world output. want find nearest point on graph arbitrary given point p programmatically. i'm trying find efficient (ie fast) algorithm doing this. don't need the exact closest point, can settle point 'nearly' closest point.

the obvious lazy solution increment through every single point in graph, calculate distance, , find minimum of distance. theoretically slow large graphs; slow want.

since need approximate closest point imagine ideal fastest equation involve generating best fit line , using line calculate point should in real time; sounds potential mathematical headache i'm not take on.

my solution hack works because assume point p isn't arbitrary, namely assume p close graph line , when happens can cross out distant x values consideration. calculating how close point on line shares x coordinate p , use distance between point , p calculate largest/smallest x value possible closer points.

i can't feel there should faster algorithm solution (which useful because assume 99% of time point p point close line already). tried googling better algorithms found many algorithms didn't quite fit hard find looking amongst clutter of inappropriate algorithms. so, here have suggested algorithm more efficient? keep in mind don't need full algorithm since have works needs, i'm curious proper solution have been.

if can use data structure, common data structures spacial searching (including nearest neighbour) are...

  • quad-tree (and octree etc).
  • kd-tree
  • bsp tree (only practical static set of points).
  • r-tree

the r-tree comes in number of variants. it's closely related b+ tree, (depending on variant) different orderings on items (points) in leaf nodes.

the hilbert r tree uses strict ordering of points based on hilbert curve. hilbert curve (or rather generalization of it) @ ordering multi-dimensional data nearby points in space nearby in linear ordering.

in principle, hilbert ordering applied sorting simple array of points. natural clustering in mean search need search few fairly-short spans in array - complication being need work out spans are.

i used have link paper on doing hilbert curve ordering calculations, i've lost it. ordering based on gray codes simpler, not quite efficient @ clustering. in fact, there's deep connection between gray codes , hilbert curves - paper i've lost uses gray code related functions quite bit.

edit - found link - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.7490


Comments

Post a Comment

Popular posts from this blog

c# - How to set Z index when using WPF DrawingContext? -

-
how set z-index drawing object when using drawingcontext.drawxxx() methods? the object drawn last have higher z index. can't change index of drawn objects. way draw in order. if using wpf (as placed tag), can use, example, canvas control. create shapes need like polyline obj = new polyline(); //... // ... set properties of obj and add them canvas uielementcollection: yourcanvasname.children.add(obj); //or yourcanvasname.children.insert(i, obj); first items of collection have higher z index. advantages in way: no need redraw on window changes, can anytime move objects , change order.
Read more

razor - Is this a bug in WebMatrix PageData? -

-
i think may have found bug in webmatrix's pagedata, not sure. concerns how pass data partial page calling page. in webmatrix documentation (tutorials, e.g. " 3 - creating consistent look ", , example code), pagedata recommended mechanism pass data between pages (e.g. content page layout page, or partial page). however have found not work other way, pass data partial page calling page. modifying or adding entries in pagedata in partial page, not seem calling page. cutting right down simplest possible example, in test page may have this: @{ pagedata["test"] = "initial entry"; } <p>before calling partial page, test value @pagedata["test"]</p> @renderpage("_testpartial.cshtml") <p>after returning calling page, test value @pagedata["test"]</p> and in _testpartial.cshtml page might have this: @{ pagedata["test"] = "modified entry"; } <p>in partial page...
Read more

visual c++ - Using relative values in array sorting ( asm ) -

-
i need sort through array , sort each individual row in array in ascending order. doesn't seem going (surprise!) keep getting hit 2 errors: a2101: cannot add 2 relocatable labels , a2026: constant expected here's sort, makes sense me, think i'm still trying implement high-lvl language techniqes assembly. there way around not being able use relative values? (the array 7 rows 9 columns, btw). mov cx, 7; cx = number of rows outer: ; outer loop walk through rows push cx mov cx, 9 mov row, cx ;rows middle: ; middle-loop walk through columns push cx sub cx, 1 ;cx = cx-1 mov column, cx ;columns inner: ;inner loop - compare , exchange column values cmp marray[row*9 + column], marray[row*9 + column+1] xchg marray[row*9 + column+1], marray[row*9 + column] ; compare , exchange values marray table inc column loop inner pop cx loop mid...
Read more