PDA

View Full Version : Code Help Request



ronjon65
10-07-2015, 03:49 PM
This is pretty straightforward, but my skills have dwindled (use it or lose it). The goal is determine the 3 points numbers in red (create a rectangle) from a given point number. For help with this, I can donate $30 to the site. Does that seem reasonable?


14528

mikerickson
10-07-2015, 08:01 PM
You have a four column grid,
So a 2X2 rectangle (bottom left point K) would have top-left = K+4, bottom-right = K+1, top-right = K+5

If you change the coordinates so there are other than four points per row, you should be able to determine the number of points per row with the formula

=MATCH(0,B4:B200,0)+1 (if "x" is in B1 and 1 is in A3)

ronjon65
10-07-2015, 08:34 PM
Well, maybe I over simplified things with this example. The order of the points and their arrangement is random and the number of points is over 10,000. I had thought about using MATCH, but it seems like it would get messy for a general problem. I will think about it some more though.

My thought to do in VBA would be (for example to find the bottom right point):
- Loop to see which points have the same Y value
- Loop to see which point has the minimum (but positive) delta X value.
- For example, for given point number 6, the first loop would only consider points 5,6,7,8 and the second loop would down select to point 7.
- Similar process for the other points and the top right corner point could be determined based on the bottom right point or top left point (seems easier than basing it off the bottom left point).
- Essentially, it is just a matter of finding the adjacent point within the array.

The loops would go until there is a blank (where "Continued" currently is).

p45cal
10-08-2015, 02:38 AM
I was exploring this last night and I have a few ideas and got the correct results (with orthogonal grid) but the code is messy and not very robust, so:
1. Could you provide a link to a file in the cloud so that (a) we don't have to copy data from a picture, (b) guess wrongly other aspects of the sheet and (c) allow us to play with a realistic amount of data.
2. Is this (part of) some recognized mathematical problem/algorithm? If so, could you name it?

ronjon65
10-08-2015, 05:57 AM
Well, I don't really know of a god way to get the file on the cloud :/ But here is how it would break down, in further detail. Lets assume you want to to find the BOTTOM RIGHT point.

1. Get the y-position of point F6 from column C (requires looping through column C to find point)
2. From column D, store all points with same y-position as that of F6 (this can be done either internally to the code or temporarily off to the side of the sheet)
3. From the list found in (2), find the point with the point with the minimum delta x (provided it is a positive value).
4. Loop the code through column F.
5. This should generate the H column
6. Do this for the other corners (top right, top left, bot right). I can probably handle that part if the code for the bottom right exists.

14529

----

For reference, this is to determine what is called "connectivity" for finite element analysis. I can create the nodes rather easily, but the connectivity can be a hassle, especially when you have thousands of nodes that do not always have a nice and neat order. Attached is an example of a finite element:

14530

ronjon65
10-09-2015, 09:51 AM
I decided just to give it a go myself. Think I will be able to figure it out, even if it is a big kludgy. Thanks though.

mikerickson
10-09-2015, 10:32 AM
I've been working on a solution (probably more elaborate than what you want).
Its almost ready.

ronjon65
10-09-2015, 11:05 AM
Oh shoot, I thought you abandoned it! I just finished. Its not very elegant, but works. Used some Excel functions and 4 loops. I will still donate to the site anyway though.

Maybe we can exchange codes and though and you can see how ugly mine is and why its not a first resort, haha.

mikerickson
10-09-2015, 12:26 PM
I'm doing a more general approach (and got sidetracked with some drawing functions)


"Given a set of points. Given one of those points, find the smallest rectangle that encloses four of those points."

That part is done.
The part I'm working on is "find the other three corner points". This is easy if the grid is regular (i.e. if one can assume that there is a point at each corner).

ronjon65
10-09-2015, 02:52 PM
EDIT: Working on some optimizations/efficiency and it is running 5-10X faster now. So might be OK in the end.

OK, here is the example code. While it "works", it is dog slow (due to inefficient coding). When using 15,000 points, I estimate it will take a few weeks to run. So that won't cut the mustard. 14546

The slow part is where the following comment can be found
'Find potential matches

This portion of the code is slow because it is writing the values to cells. I tried to not update the screen, but that didn't help...surprisingly.

p45cal
10-09-2015, 04:54 PM
In the attached is a formula approach.
It assumes orthogonal.
Largish formulae in vicinity of H38:J40
Derivation of those formulae with helper cells can be seen in H32:N34 but these are no longer needed.
If you supply it with given points along right edge or top edge it will 'loop' to opposite edge of grid (oops).

mikerickson
10-13-2015, 08:24 PM
Given a set of points (name, x-coord, y-coord), these points have unique coordinates
Given a point (O, x0,y0)
Find the smallest rectangle with O as the bottom left corner, that encloses 4 or more points, return the 4 points closest to the corners of that rectangle.

1)Loop through all the points
Looking for the three points, closest to O, whose X-coord is greater than x0.
In the same loop, look for the three points closes to 0, where Y > y0
In that same loop, get the three closes points with both X>x0 and Y>y0

This gives us three sets (above, right, both above and right) each with three points. There may be duplicates across those sets, but not within the sets.

2) Loop through the 27 possible combinations of one point from each of the sets.
If there is a duplicate point, discard.
From the remaining combinations, find the one where MAX(aboveX,belowX,bothX)+MAX(aboveY,belowY,bothY) is minimal.

That is the dimensions of the smallest rectangle of all points that encloses 4 or more.

BUT, to find the points closest to the corners of that rectangle, we need to:
3a) know that the given point O is the bottom left corner of the rectangle
3) Loop through all points, filtering in all the points that are inside that rectangle. (include edge points0

4)Loop through that filtered set, finding the point closest to the Top Left of the Rectangle.
5)Loop through the filtered set (less the Top Left point) and find the point closest to the Bottom Right of the Rectangle
6)Loop through the filtered set (less, TL and BR points) and find the point closest to the Top Right.

Done.

(Since there may not be a point precisely at the corners, it does the best it can from the available points)

This involves two loops through all the points, one loop of 27 to find the size of the rectangle, and the three final loops through the filtered set (significantly smaller than the set of all points).


The attached implementation could be tightened up considerably, but it shows the method.

You can either:
1) Press the "Place Points" button. This will plot the points (up to 40).
The plot is based on the brown circle, which is the unit circle centered at (0,0). The user can move or resize the circle as desired.
(the labeling of the drawn points is a bit crude, adjusting column widths may help clarity)
2) Press "Button 4". The user will be promoted to enter the name of a point. The smallest rectangle.... will be drawn and a message giving the four corner points returned.

OR
Select a cell (or cells) that contain the name of a Bottom Left cell. (like F2:F5) and run the macro FindOtherCorners, by pressing the button.
The coordinates of the (closest to) other corners will be put in the adjacent cells.

ronjon65
10-13-2015, 08:37 PM
I have to look into these solutions...you guys went way out of your way! That is too much to ask really.

My solution seems to work OK after I improved the speed, so I just went with that. But I do have some more complex scenarios which may help be good for that.