Point/Line selection

General Discussions
#1

Hi,

I wasnt sure where to post this topic as its not a questions about game development but Im thinking the same logic could be applied.

I have a CAD program and I need a system where I can select lines/points individually by clicking on them. I developed a system for points where it would iterate through every point and calculate the distance between the point and the mouse cursor, it would then pick the closest point (as long as it wasn’t more then a maximum distance away) as the selected point. this system does seem to work but doesnt seem very efficient especially when you could be talking about thousands of points in a model.

For lines I have no idea how to work that out. One thing to remember is that I dont want the user to have to click on the exact coordinate of the point because this may be difficult and prove frustrating for the user.

Does anyone have an idea of an efficient system that could be applied to this problem? Im sure this must be a fundimental problem in many games.

Thanks,

Ken

#2 
	public static double getPointLineDistance(V2 p, V2 a, V2 b) {
		Line2D.Double l = new Line2D.Double(a.x, a.y, b.x, b.y);
		return l.ptLineDist(p.x, p.y);
	}

hint: re-use the line…

#3

Thanks for the reply.

Yes I guess I could do a similar method to what I did with points using that method. The only thing to bare in mind is that Im not using Line2D and Point2D for the actual point and line elements (apart from the fine graphical rendering) so I would have to implement that method myself. But luckily because Java is open source I can trawl through the source code and do something similar to what they have done.

Now can anyone think of a better method then iterating through every line/point and checking the distances.

Regards,

Ken

#4

In that snippet the V2 is my own class for holding x,y values, just replace it with your class. The Line2D is used only locally, it has the functionality you need (point-line distance).

For acceleration (not looping through all points) you need another data structure, google for QuadTrees for example.

#5

Yes but is that efficient?
Im always paranoid about creating a new object just to use one of its methods.

Ah I thought that might be the case but I dont know much about data structures, thanks for the advice Ill look into your suggested one and see what I can find out.

Thanks,

Ken

#6

hehe, thats the reason I wrote you should re-use the line.

	private static Line2D.Double l=new Line2D.Double();
	public static double getPointLineDistance(V2 p, V2 a, V2 b) {
		l.setLine(a.x, a.y, b.x, b.y);
		return l.ptLineDist(p.x, p.y);
	}

that code is ok if your program is not multithreaded.

#7

Ah thanks sorry yes I could use it for other calculations too.

If multiple threads have access to it then I would have to sync the method to fix it right?

#8

I would make a class {private Line2D l;public double getDist(…)} (without the static), and instanciate that PER thread, thats much faster.

#9

Makes alot of sense.

I was looking at quadTree in wikipedia and Im starting to get the idea but Im unsure how it would actually be implemented for my situation. So I would create a new collection similar to a hashmap but with a key of x AND y and then each value would be a point?

How is QuadTree used to actually order the elements? I presume it would be a sorted collection of some sort…

EDIT: I found this crazy thing which looks really useful:
http://donar.umiacs.umd.edu/quadtree/points/oldversion/index.html

And It looks like an amazing method its just I dont understand what its doing and why lol

#10

Regarding the point<->line distance issue.

You should be using Line2D.ptLineDistSq(double x1, double y1, double x2, double y2, double px, double py).

It doesn’t require temporary object creation and more importantly avoids the square root, which for your purposes is completely unnecessary.

#11

learning every single day :slight_smile: (yesterday it was the joy of using enums)

#12

haha I know how to use enums at least lol

Yes I did notice that when looking at the source code, I never even thought about it like that, whats the point in calculating the distance when I could settle for the smallest square. Knowing about those static methods will come in handy big style!

Are there any experts on data structures because I feel like Im going into a new field I have no idea about (yet).