Drag and Drop glued to polygon sides
March 29, 2012 10:34 AM Subscribe
Looking for tips on implementing drag and drop that snaps to the nearest point on a polygon.
I've written an application that places markers (the markers are circles where the center point of each is on a polygon side) along the outer sides of any polygon according to a specific formula. The formula is exact enough that the majority of markers is placed correctly, but I'll need the ability to drag and drop markers to make fine-tuned adjustments in some cases. The markers are already draggable, but they're free-form draggable, meaning that I have to be very careful and exact about where I drag them, if I want a dragged marker to be aligned exactly like the automatically-placed markers.
Requirements:
1. A marker that has been dragged should, when it's dropped, be affixed to a polygon side - specifically, to the point on the side that is closest to the mouse position when dropping.
2. It would be nice, but not necessary to have the markers affixed to a side of the polygon while they're being dragged. I'm afraid this may introduce too much complication and slow things down, though.
3. It must be possible to drag a marker from its starting side to all other sides.
4. The algorithm must be efficient - I don't want to add so much computation that dragging is no longer fluid. This application is used primarily on Android tablets, so performance is more of a factor than for a PC-based application.
5. It would be nice to have a 'snap' capability that moves the marker in increments of X pixels along the walls, but this is something I could add later.
I've thought a good deal about this. I've considered using vector math to measure the distance of the mouse to each side of the polygon while dragging, and choosing the side with the shortest distance / the point on that side. I'm worried that this much computation will slow the app down for complex polygons.
I've also considered setting a center point on the polygon, drawing a ray from that point to the mouse location and using the intersection of that ray with a polygon side to determine the marker's location while dragging.
With the snap idea in mind, I've thought about generating a list of points on all sides that could be snapped to, and choosing the one that's closest to the mouse position.
Hoping someone's worked with something similar and might have some helpful tips.
I've written an application that places markers (the markers are circles where the center point of each is on a polygon side) along the outer sides of any polygon according to a specific formula. The formula is exact enough that the majority of markers is placed correctly, but I'll need the ability to drag and drop markers to make fine-tuned adjustments in some cases. The markers are already draggable, but they're free-form draggable, meaning that I have to be very careful and exact about where I drag them, if I want a dragged marker to be aligned exactly like the automatically-placed markers.
Requirements:
1. A marker that has been dragged should, when it's dropped, be affixed to a polygon side - specifically, to the point on the side that is closest to the mouse position when dropping.
2. It would be nice, but not necessary to have the markers affixed to a side of the polygon while they're being dragged. I'm afraid this may introduce too much complication and slow things down, though.
3. It must be possible to drag a marker from its starting side to all other sides.
4. The algorithm must be efficient - I don't want to add so much computation that dragging is no longer fluid. This application is used primarily on Android tablets, so performance is more of a factor than for a PC-based application.
5. It would be nice to have a 'snap' capability that moves the marker in increments of X pixels along the walls, but this is something I could add later.
I've thought a good deal about this. I've considered using vector math to measure the distance of the mouse to each side of the polygon while dragging, and choosing the side with the shortest distance / the point on that side. I'm worried that this much computation will slow the app down for complex polygons.
I've also considered setting a center point on the polygon, drawing a ray from that point to the mouse location and using the intersection of that ray with a polygon side to determine the marker's location while dragging.
With the snap idea in mind, I've thought about generating a list of points on all sides that could be snapped to, and choosing the one that's closest to the mouse position.
Hoping someone's worked with something similar and might have some helpful tips.
I don't know what programming language you're using (java I guess?) but if you're stuck I could probably code up a simple demo for you in something.
posted by RustyBrooks at 11:07 AM on March 29, 2012
posted by RustyBrooks at 11:07 AM on March 29, 2012
Try the accurate method first (finding the closest point on the closest edge). Then make the obvious optimizations -- e.g. ignore edges that can't possibly be close enough. I bet this will be fast enough; it's really not that much math. No reason to reach for approximations until you've found that the accurate way is too slow in your particular situation.
posted by xil at 11:12 AM on March 29, 2012 [1 favorite]
posted by xil at 11:12 AM on March 29, 2012 [1 favorite]
I just wrote something very similar yesterday, but I'm on my phone at the moment, so I can't type out the equations. It's actually fairly simple.
I'll write it out when I get home in a few hours.
posted by WasabiFlux at 11:24 AM on March 29, 2012
I'll write it out when I get home in a few hours.
posted by WasabiFlux at 11:24 AM on March 29, 2012
Response by poster: These polygons can be convex or concave (or a mix of the two).
At the moment, I'm working on a solution that only calculates the point when I drop the marker. The first iteration will find the closest point on each side of the polygon to the provided point, and will return the one with the shortest distance to the provided point.
Javascript is the language, and I've written a small geometry library that has a number of line, point and polygon utilities.
posted by syzygy at 11:41 AM on March 29, 2012
At the moment, I'm working on a solution that only calculates the point when I drop the marker. The first iteration will find the closest point on each side of the polygon to the provided point, and will return the one with the shortest distance to the provided point.
Javascript is the language, and I've written a small geometry library that has a number of line, point and polygon utilities.
posted by syzygy at 11:41 AM on March 29, 2012
OK I put something together, it works with any kind of polygon. I wrote it in tcl but hopefully you can figure out the basic algorithm? If you have tcl/tk installed you can run with like
wish ./test.tcl
on your machine. Move the mouse in the window and a purple dot will show the closest snapped point.
Granted I am running this on a regular PC but it's in the 300 microsecond range for me.
posted by RustyBrooks at 12:01 PM on March 29, 2012
wish ./test.tcl
on your machine. Move the mouse in the window and a purple dot will show the closest snapped point.
Granted I am running this on a regular PC but it's in the 300 microsecond range for me.
posted by RustyBrooks at 12:01 PM on March 29, 2012
I even just tried it with a polygon that crosses itself and it still works fine, btw.
posted by RustyBrooks at 12:22 PM on March 29, 2012
posted by RustyBrooks at 12:22 PM on March 29, 2012
It's been some time since I used it (and the documentation always seems to be going backwards for me), but could you use jQuery's Droppable as the basis and then just tweak the tolerances and drop target logic? Just thinking that might be easier than maintaining an entire geometry library.
posted by yerfatma at 1:16 PM on March 29, 2012
posted by yerfatma at 1:16 PM on March 29, 2012
Response by poster: RustyBrooks: Thanks for the explanation and code sample. Your explanation caused me to take a look at my geometry library. I realized that I have a Line.perpendicular() method and a Line.segmentContains() method that, together, get me most of the way to finding the shortest distance between a given point and line segment. The rest was just looping through the lines that make up the polygon sides.
underscore.js ftw here - pseudocode:
var snapToCoords = _.chain(polygon.sides)
.map(function(side){//return [intersection coords, shortest distance from point to side]})
.sortBy(function(side){//return distance})
.first()
.value()[1];
Because I'm doing this with an SVG drawing embedded in HTML, and I already have to perform some calculations while dragging (matrix transform, etc.), I decided to just do the snapTo on mouseUp for the time-being. This means the marker is freeform draggable, but snaps to the closest point on the polygon when the user mouses up.
yerfatma: I am using jQuery, and I have looked at Draggable and Droppable, but I don't think they work out-of-the-box with embedded SVG. Besides, writing and maintaining a geometry library has actually been pretty fun :-)
posted by syzygy at 1:23 AM on April 4, 2012
underscore.js ftw here - pseudocode:
var snapToCoords = _.chain(polygon.sides)
.map(function(side){//return [intersection coords, shortest distance from point to side]})
.sortBy(function(side){//return distance})
.first()
.value()[1];
Because I'm doing this with an SVG drawing embedded in HTML, and I already have to perform some calculations while dragging (matrix transform, etc.), I decided to just do the snapTo on mouseUp for the time-being. This means the marker is freeform draggable, but snaps to the closest point on the polygon when the user mouses up.
yerfatma: I am using jQuery, and I have looked at Draggable and Droppable, but I don't think they work out-of-the-box with embedded SVG. Besides, writing and maintaining a geometry library has actually been pretty fun :-)
posted by syzygy at 1:23 AM on April 4, 2012
Response by poster: RustyBrooks: For clarification, my line.perpendicular() method does the right triangle part of things in your explanation. line.segmentContains tells me whether the point where the intersection of the perpendicular line and the polygon side is on the line segment that defines the polygon side. If it is, that's my closest point to that side. If it's not, one of the endpoints of the segment will be the closest point to that side.
Also, the last line in the pseudocode example should be:
.value()[0] //returns the coordinates of the closest point on the side
This is wrong:
.value()[1] //returns the distance from the given point to the intersection of the perpendicular line with the polygon side line
posted by syzygy at 1:32 AM on April 4, 2012
Also, the last line in the pseudocode example should be:
.value()[0] //returns the coordinates of the closest point on the side
This is wrong:
.value()[1] //returns the distance from the given point to the intersection of the perpendicular line with the polygon side line
posted by syzygy at 1:32 AM on April 4, 2012
Glad it worked out for you. I had a pretty good time throwing that together, for what it's worth.
posted by RustyBrooks at 6:13 PM on April 8, 2012
posted by RustyBrooks at 6:13 PM on April 8, 2012
This thread is closed to new comments.
Once you know the closest line segment, you easily find the closest point on that line. Imagine a triangle formed by the vertices of that line and your mouse cursor. Call the mouse cursor M and the point you're looking for P. (M-P) will be a vector that is a right angle to your line segment. This is going to be hard for me to describe with out a picture...
Pick one vertex of your poly segment, call that angle A. The distance from that vertex to your mouse, let's call M. Since we have a right triangle now, the length along the segment from your chosen vertex (let's say L) is defined by cos(A) = L/M. We're looking for L, so L = cos(A)*M. And there's you're closest point.
posted by RustyBrooks at 11:07 AM on March 29, 2012