|
What if you iterate over every line segment, and determine argmin(d(ThePoint,line-seg)), the polygon containing the line-seg is closest to the point.
Would that be too slow? The formula for d(point, line-segment) is not pretty and there might be ton of line segments (right? about how many segments do you expect?)modified on Friday, February 19, 2010 1:00 PM
|
|
|
|
|
Actually I came across the formula for figuring the point on a line that is closest to a given point.
It's not too bad, but I don't yet have a sense of how fast it would be with the average layout containing 50+ polygons, and each polygon containing at least 4 and likely many more line segments.
|
|
|
|
|
50 times 4 doesn't sound to bad yet, but "many more" is really a lot... Could it be worth a try? It does seem "cleaner" to me than expanding a circle until it hits something
|
|
|
|
|
I think you're right. I would like to try it, especially since the math would be simpler than the other solution.
|
|
|
|
|
The problem with circle approach is that you need to calculate the radius to every point to determine if it is within the circle, determining the radius of the next circle and iterating through it again.
This is worse than determining the distance to each point once and taking the one with the smallest radial distance.
If you need to do this in real time, you want to take an approach where you break the world up into 2 kinds of polygons, 'rooms', which are obvious, or 'not rooms', where the border between 'not room' polygons is the line equidistant between 2 rooms.
This way, every polygon is a room, or the area closest to a particular room.
If you know what polygon you are in, you either know the room you are in, or the room you are closest to.
You use the same code to determine which polygon you are in, either way.
The only special code is breaking up the world ahead of time.
RichardOpacity, the new Transparency.
|
|
|
|
|
Richard,
This is a lot like the Star mapping question from several years back. Sort the polygons by lowest Y value and lowest X value for a point in the polygon, but save the entries 4 times, once for each vertex. Divide the building into a 10x10 grid and determine which square contains the point. Then scan the list of polygons for one that has the XY point in the same square or in one of the adjacent squares. There may be several. Determine the perpendicular distance from the point to either line connecting with the closest point ot the distance to the point. Chose the polygon with the shortest distance. Remember, do not take the square root of the sum of the squares for comparisons, but just compare the sum of the squares.
Dave.
|
|
|
|
|
Richard,
I hate to double post, but there is a simplification. Sort the points for each polygon manually for lowest Y and lowest X, draw a line between lowest x lowest X and highest y highest Y, then draw a line between the other two points. Calculate the intersection of the lines to form the center point. Put the polygon points and center point into an array as a structure and repeat for all polygons. Sort on the center point Y and X values. Now just look for the closest center to the point. You do not need to divide the building into squares, just look for the closest center to the point. If the list is short enough, don't sort, just scan for the smallest distance between the center and the point (smallest sum of squares).
Dave.
|
|
|
|
|
Using this[^](PDF warning! googledocs version here[^]) paper as reference, I have so far (after a couple of days of being annoyed and rewriting the code from scratch every few hours) only been able to get half of it right.
The problem is mainly that this article is written in weird mathematical language with single-letter names all over the place, with the upper case S being an other variable than the lower case s. Add to that all the "obvious" steps for which the implementation is left as an exercise for the reader. The code in the appendix isn't any better, and may even be worse because it uses variables named n02 etc.
I've searched for implementations, but the best I found was a highly obfuscated Java implementation which passed values to methods by putting them in fields of the class rather than as arguments.
Could anyone please explain step 3 of this algorithm? (or more than that, I don't mind, but step 3 is the only part I don't understand)
|
|
|
|
|
Hi Harold,
I'm not familiar with the matter, however I glanced through the PDF; looks like a decent but though article indeed. The source code at the end doesn't seem that awful; why not just feed it to the C# compiler and fix the remarks it will throw at you?
 Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that. All Toronto weekends should be extremely wet until we get it automated in regular forums, not just QA.
|
|
|
|
|
That's possible, but I really prefer understanding it first - and also, all that pointer magic doesn't make me too happy (it can't easily be removed, either, because it's used to change the start of an array several times)
|
|
|
|
|
harold aptroot wrote: I really prefer understanding it first
for a big article and a small snippet I'm often willing to reverse the order, so run it first, observe and understand it later.
harold aptroot wrote: pointer magic ... can't easily be removed
I noticed that; however, adding start parameters solves that, like so:
public bool sleq(int[] s1, int[] s2, int start1, int start2) {
for(int i=0; ; i++) {
if (s1[start1+i]<s2[start2+i]) return true;
if (s1[start1+i]>s2[start2+i]) return false;
}
}
 Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that. All Toronto weekends should be extremely wet until we get it automated in regular forums, not just QA.
|
|
|
|
|
Ok well it can be removed of course, it just takes.. effort.
Are you sure you couldn't just explain step 3 quickly?
Otherwise I guess I'll work on converting that code..
|
|
|
|
|
harold aptroot wrote: Are you sure you couldn't just explain step 3 quickly?
No, not really. I am sure I could convert the code faster than you could make me understand it though.  Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that. All Toronto weekends should be extremely wet until we get it automated in regular forums, not just QA.
|
|
|
|
|
Fair enough, I'll convert it.
|
|
|
|
|
In the mean time, I have a TryAll.cs that compiles (and looks like it will generate a lot of output). I could mail it to you.
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that. All Toronto weekends should be extremely wet until we get it automated in regular forums, not just QA.
|
|
|
|
|
Yes please, my email is just my name @gmail.com (without underscores)
|
|
|
|
|
mail sent
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that. All Toronto weekends should be extremely wet until we get it automated in regular forums, not just QA.
|
|
|
|
|
changing the first line to
#define WITH_DEBUG_OUTPUT1 // WITH_xxx or WITHOUT_xxx
seems to generate decent results, assuming the command line holds two numbers, such as 3 5
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that. All Toronto weekends should be extremely wet until we get it automated in regular forums, not just QA.
|
|
|
|
|
Hi,
in a directed graph with positive edge weighs, how can I computed all pathes from A to B with length less than a certain bound?
I could use a k-shortest path algorithm, but I don't know k in advance..
I want something like
while (l < bound) {
path p = graph.GiveMeNextPathInAscendingOrder(A,B);
l = p.length;
do something with p..
}
Best regards
-->Andreas
|
|
|
|
|
Easy; just do a depth-first search, backing up when you hit a dead end or exceed the bound.
|
|
|
|
|
I have a huge database (3 million records) that I need to de-duplicate by street address every month. With non-conforming addresses like (123 S. Ventnor Blvd, 123 South Ventnor Boulevard NW, etc.), de-duping is a pain. I'd like to find an algorithm with whatever lookup tables are necessary to convert all of the addresses to USPS format like you find in CASS certified addresses, so they can be compared. Anybody ever done that and have some clues?
|
|
|
|
|
hi,
I am to develop a 2d self assembler as my college project... I searched a lot and found some many papers on this subject. But all of them are full of theory and none of them said anything about the implementation part...
Could someone help me with these or atleast direct me to some specific place where I can more info on 2d self assemblers.
Thank you
|
|
|
|
|
Sai Yasodharan wrote: I am to develop a 2d self assembler as my college project
You do understand that this means YOU are expected to do the work?
MVP 2010 - are they mad?
|
|
|
|
|
Are you kidding? It means he has to find a way to get it done. For sure self does not refer to him?
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that. [The QA section does it automatically now, I hope we soon get it on regular forums as well]
|
|
|
|
|
I know I must do the work... I m just here to get some help or guide from the experts, who already played with 2D SELF ASSEMBLERS, if any. Also help in the sense not the program, just some info on how to start and which way to proceed
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
