473,573 Members | 2,773 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

How to find duplicate 3d points?

I have a large data file of upto 1 million x,y,z coordinates of
points. I want to identify which points are within 0.01 mm from each
other. I can compare the distance from each point to every other
point , but this takes 1 million * 1 million operations, or forever!

Any quick way to do it, perhaps by inserting just the integer portion
of the coordinates into an array, and checking if the integer has
already been defined before inserting a new point?
Jun 27 '08 #1
2 2411
On Jun 11, 11:35*am, oprah.cho...@gm ail.com wrote:
I have a large data file of upto 1 million x,y,z coordinates of
points. I want to identify which points are within 0.01 mm from each
other. I can compare the distance from each point to every other
point , but this takes 1 million * 1 million operations, or forever!

Any quick way to do it, perhaps by inserting just the integer portion
of the coordinates into an array, and checking if the integer has
already been defined before inserting a new point?
what many people do when doing collision detection in 3d games in
instead of having one massive list of the vertices will break the
field into bounding boxes. in the 2d situation that would look like
this.

|----|----|----|----|
|. . | | .| |
|----|----|----|----|
|. |. | . |. |
|----|----|----|----|
| | . | . | |
|----|----|----|----|
| | | | . .|
|----|----|----|----|

That so instead of comparing all points against all other points
instead sort them into bounding cubes. that should make doing the
comparisons more reasonable. now the only sticky bit will be comparing
two vertices that are in two different boxes but so close to the edges
that they are under .01mm from each other. in this situation if a
point is less that .01mm from any edge of its bounding cube you must
compare it against the points in the adjacent cubes.

hope this helps a bit.

cheers
Tim Henderson
Jun 27 '08 #2
op**********@gm ail.com wrote:
I have a large data file of upto 1 million x,y,z coordinates of
points. I want to identify which points are within 0.01 mm from each
other. I can compare the distance from each point to every other
point , but this takes 1 million * 1 million operations, or forever!

Any quick way to do it, perhaps by inserting just the integer portion
of the coordinates into an array, and checking if the integer has
already been defined before inserting a new point?
--
http://mail.python.org/mailman/listinfo/python-list
There is a whole field of Math/CS research on problems like this called
Computational Geometry. It provides many algorithms for many geometric
problems, including things like this.

In particular, to categorize a list of points and find the
NearestNeighbor , I'd suggest a KD-tree. I believe this would turn your
problem from O(N^2) to O(N log n) or so.

Happy google-ing and good luck.

Gary Herron

Jun 27 '08 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
1495
by: F C | last post by:
I have http://localhost/myweb1 who redirect me to my pages. I would like to have http://localhost/myweb2 which I would like to use the same exact set of pages, except a different global.asa (application data will be different). If I duplicate pages, that is not a problem, but I would prefer not to duplicate them. How can I do this ?
2
1526
by: Richard | last post by:
Hi Everyone, I have a table in which their is record which is exactly same. I want to delete all the duplicate keeping ony 1 record in a table. Example Table A Empid currentmonth Previousmonth Supplimentarydays basic
6
6389
by: nick4soup | last post by:
I have read the CGI FAQ 'How can I avoid users hitting "submit" twice' (on http://www.htmlhelp.org/faq/cgifaq.3.html#19 ) which essentially says you have to detect it at the server, using a hidden form field. That's fair enough. My server is therefore processing a response on the first request, so what kind of HTML response should I...
3
4168
by: deko | last post by:
I'm using Access 2003 on WinXP-SP2. I open mydb.mdb from Windows Explorer, or from a shortcut that points to the mdb. The problem is every time I open mydb.mdb, a duplicate is created - mydb1.mdb. And if I try opening mydb1, then mydb11.mdb is created. Anyone have any idea why this is happening? How I can stop this? Thanks in advance.
1
2476
by: aknoch | last post by:
My basic situation is this - I ONLY want duplicates, so the opposite of DISTINCT: I have two tables. Ordinarily, Table1ColumnA corresponds in a one to one ratio with Table2ColumnB through a shared variable. So if I query TableB using the shared variable, there really should only be on record returned. In essence, if I run this and return...
5
3015
by: JD | last post by:
Hi, There are about 10+ 3-D points on the same line. I want to find the two end points from these points. The efficiency is not an issue because there are only 10 points or so. I just need a cleaner code to do it. Should I use an STL set to store the distances among them and then retrieve the max distance from the last element in the...
5
13861
by: Sheol | last post by:
Hello everyone! Can somebody please help me with this... I have a VB program that inputs Name and Address. I've made a database in MS Access using ADO Control: Table Name: Contacts Fields are: ID, CompanyName, CompanyAddress My only problem is that how can I find duplicate entries in the CompanyName field. I have an ADD command button when...
2
2570
by: raphael001 | last post by:
In my Visual Basic program I'm just trying to find duplicate values entered into an array from an inputbox, but i can't seem to get the coding right on the final part to check for duplicate values already entered. Any help would be greatly appreciated. This is what i have so far except the code to check for duplicate values: Dim intarray() As...
0
1977
by: =?Utf-8?B?UGF1bCBIYWdlcg==?= | last post by:
I've been trying to solve this issue for the better part of a month. My attempts to get an answer on the MSDN groups proved to no avail. Here is the situation/problem. I am migrating an old piece of software developed using VC++ 4.2, running on Windows NT 3.51 to VC++ 2005, running on Windows XP Pro SP2. I went through all of the...
0
7784
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
8033
Oralloy
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. ...
0
8206
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7796
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...
1
5601
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5294
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...
0
3734
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...
1
2224
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
0
1044
bsmnconsultancy
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...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.