Algorithm help
by Joel Douthit · in Technical Issues · 03/22/2001 (5:07 pm) · 6 replies
This is kind of heavy, especially with my description of the problem :). Looking for maybe a link to a page describing similar problems or this problem, or a name of an algorithm to look up, or just any help at all.
What I know:
I have a segment(a path), described by an ordered list of 2d shape points. Index zero is one (lets call it the left) end, and index N is the right end. Adjacent points in the list form straight lines. I do not know if 3 adjacent points can be colinear.
What I want:
I also have another point in the same space(may or may not be on the segment). I want to map that point to the segment, and find the index of the shape point to the left of the that mapped point.
Here's another description, in more mathmatical terms for those of you who lean that way.
Given a list of points 0...N, and Point P. Find Point J(can be 0...(N-1)) such that Points J and J+1 form a line that has the smallest perpendicular distance from Point P.
I think I said that correctly. Not up on all my geometry terms anymore.
The problem is that a segment can be several thousand shape points, and I have 2 points to map to the segment, so simply walking down the segment testing each time is not really acceptable. It doesn't have to be a real-time solution, but something that'll finish during lunch would be nice:).
This is for my paid job, so don't spend too much time trying to figure out the algorithm, as I'm doing the same thing on the clock. I'm just looking for more information about this problem, in case anyone here has dealt with it before.
Joel.
What I know:
I have a segment(a path), described by an ordered list of 2d shape points. Index zero is one (lets call it the left) end, and index N is the right end. Adjacent points in the list form straight lines. I do not know if 3 adjacent points can be colinear.
What I want:
I also have another point in the same space(may or may not be on the segment). I want to map that point to the segment, and find the index of the shape point to the left of the that mapped point.
Here's another description, in more mathmatical terms for those of you who lean that way.
Given a list of points 0...N, and Point P. Find Point J(can be 0...(N-1)) such that Points J and J+1 form a line that has the smallest perpendicular distance from Point P.
I think I said that correctly. Not up on all my geometry terms anymore.
The problem is that a segment can be several thousand shape points, and I have 2 points to map to the segment, so simply walking down the segment testing each time is not really acceptable. It doesn't have to be a real-time solution, but something that'll finish during lunch would be nice:).
This is for my paid job, so don't spend too much time trying to figure out the algorithm, as I'm doing the same thing on the clock. I'm just looking for more information about this problem, in case anyone here has dealt with it before.
Joel.
About the author
#2
Data-Parallel Spatial Join Algorithms,Efficient Processing Of Spatial Queries In Line Segment Databases, Spatial Data Structures, and Speeding Up Construction of Quadtrees for Spatial Indexing
I haven't looked them over in any detail as yet (that's for tomorrow), so YMMV.
This is my first post to this forum, so I hope this post isn't mangled too badly.
Hope this helps.
03/22/2001 (9:11 pm)
I needed to find out this same algorithm at my paid job today, oddly enough. From my research on and off the Internet, it looks like the data structure you need is the PMR Quadtree. Several spatial indexing algorithms exist for this structure and I found a few papers relating to the implementation of the structure itself or the algorithms to perform spatial queries such as finding the nearest line to a point. The promising papers I found that are available online are atData-Parallel Spatial Join Algorithms,Efficient Processing Of Spatial Queries In Line Segment Databases, Spatial Data Structures, and Speeding Up Construction of Quadtrees for Spatial Indexing
I haven't looked them over in any detail as yet (that's for tomorrow), so YMMV.
This is my first post to this forum, so I hope this post isn't mangled too badly.
Hope this helps.
#3
I hadn't run across that database before, that's a big help.
Joel.
03/23/2001 (10:23 am)
Ah thanks, Brian and Brian. You're right, while it will work just to walk through, I absolutely hate ugly solutions. Since I have no experience in graphics coding, and it sounded like a graphics style of problem to me, I figured I'd ask to see if anyone knew the answer off the top of their head.I hadn't run across that database before, that's a big help.
Joel.
#5
03/23/2001 (6:21 pm)
FYI, oct-trees, quadtrees, BSPs, etc. are all really special-case instances of kd-trees.
#6
Joel.
03/23/2001 (11:08 pm)
Ack...yeah, I knew that. There goes me being an idiot again. I do that occasionally, every few minutes or so :).Joel.
Torque 3D Owner Brian Smith
You could also divide your points into groups spacially, a la quadtrees. This would probably help in rejecting quite a few path points. If this is in the context of an engine with visibility code, just do some integration with that.