Hello, I am currently writing an application that involves many (>
1000) points on a (x,y) plane. I am using a struct to contain the
position information, and I have the structs contained in a STL
vector. Given a target coordinate (x,y)_t, I would like to be able to
cycle through the vector of points in order to obtain the closest
point. What would be the most efficient way to implement this?
I have considered keeping the vector sorted by the coordinates, say,
by the x-coordinate and the y-coordinate and to "home-in" on the point
by two successive filters. However, my memory of the STL is not so
great and I would very much appreciate some pointers in implementing
this idea.
Furthermore, it seems like this approach may not always yield the
point that is closest to the point.
Thank you in advance
1  1558  ki**@mit.edu wrote:
Hello, I am currently writing an application that involves many (>
1000) points on a (x,y) plane. I am using a struct to contain the
position information, and I have the structs contained in a STL
vector. Given a target coordinate (x,y)_t, I would like to be able to
cycle through the vector of points in order to obtain the closest
point. What would be the most efficient way to implement this?
Partition your points. Partition searches are the fastest.
I have considered keeping the vector sorted by the coordinates, say,
by the x-coordinate and the y-coordinate and to "home-in" on the point
by two successive filters. However, my memory of the STL is not so
great and I would very much appreciate some pointers in implementing
this idea.
If that's what you want...
All you need is a way to compare two points to put them in order.
Write a function taking two points and returning a bool. It would
return 'true' if the first argument is "less" than the second one.
Whatever "less" means to you. Then pass this function as the third
argument of 'std::sort'. I am sure you could use some decent book
on standard library as well. Try "The C++ Standard Library" by
Josuttis.
Furthermore, it seems like this approach may not always yield the
point that is closest to the point.
I think you need a decent book on graphical algorithms. Finding the
nearest point from a collection of points can be better than N*N.
Read about Kd-trees.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: R U B'n |
last post by:
Hi everyone,
I have to make a (case-insensitive) search from a form with only one
search string,
e.g. "Doe Peters english California",
which will search in several fields of my table for each word.
My fields that are searchable by this query are:
nr smallint(5)
company varchar(100)
lastname(100)
|
by: Steve Chen |
last post by:
Wireless Search with Summarized Results/Web Pages, powered by Google!
We just released a wireless search service. The wireless search
service takes the results returned by Google and gives key points of
the resulting web sites. The short key points are suitable for viewing
on wireless devices.
Check it out at:
<a href=http://www.netosprey.com> wireless search </a>
|
by: Magix |
last post by:
hi,
let say I have this string
+CCED: "xxxxxxxxx", 333
What is the most efficient way to capture the string within the " " ? which
is xxxxxxxxx
xxxxxxxxx can be any string.
|
by: Tamir Khason |
last post by:
Let's say I have Point and I want to sort it circle way (e.g.
2;2.4;1,8;2,8,5;4;8,2;7,1;4
The algo for this is:
if ((p.X<p.X & p.Y<Avg(p).Y & p.Y<Avg(p).Y) |
(p.X>p.X & p.Y>Avg(p).Y & p.Y>Avg(p).Y) )
Swap(p,p);
where Avg(p).Y is the middle (average) of all Y values.
Other words:
First of all all point with Y above the Middle of Ys acsending and then
all point with Y under the Middle of Ys descending
|
by: David Pratt |
last post by:
Hi. I like working with lists of dictionaries since order is preserved
in a list when I want order and the dictionaries make it explicit what
I have got inside them. I find this combination very useful for storing
constants especially. Generally I find myself either needing to
retrieve the values of constants in an iterative way (as in my
contrived example below). Perhaps even more frequent is given one value
is to look up the matching...
| | |
by: JJ48 |
last post by:
Hi all,
I was hoping I could get some direction for you folks on how to tackle this problem.
Background:
A person applying for health coverage gets assigned certain number of points which range from 1 - around 200. Based on the points and their age group, we decide what level of coverage (5 levels) they get. Each level has a maximum point allowed. The number of points per plan and level is very random. The only sequence is that Level 1 is...
|
by: Rahul |
last post by:
Hi Everyone,
I have the following problem and i was wondering as to how to solve
the same with time complexity as the priority,
a is an array of integers having combination of 0 and 1 only.
function is given a pointer to a and the size of the array and the
function should return
|
by: Mahesh |
last post by:
Hi,
I am looking for efficient string cancatination c code. I did it using
ptr but my code i think is not efficient.
Please help.
Thanks a lot
|
by: Ken Fine |
last post by:
This is a question that someone familiar with ASP.NET and ADO.NET DataSets
and DataTables should be able to answer fairly easily. The basic question is
how I can efficiently match data from one dataset to data in a second
dataset, using a common key. I will first describe the problem in words and
then I will show my code, which has most of the solution done already.
I have built an ASP.NET that queries an Index Server and returns a...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
| | |
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| | |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |
