Author Topic: Creating grid from irregular spaced points  (Read 349 times)

0 Members and 1 Guest are viewing this topic.

sdunn

  • Newt
  • Posts: 83
Creating grid from irregular spaced points
« on: May 26, 2022, 11:30:24 AM »
I am working with a "grid" of points and I need to assign a designation to each point based on its location within the grid.  The points locations appear in a grid, but the locations are not exact and may vary slightly.  The variations are usually within %10 of the overall grid spacing.  When the points generally follow the x and y axis, I can account for the variations by rounding the coordinates to the nearest whole unit and determine each points location relative to the grid based on their coordinates

The issue I am running into is when the columns within the grid generally follows the Y axis, but the rows are skewed off the x axis.  There is enough of a deviation from the axis that my current method fails for the easternmost points.  I am trying to resolve this without user interaction, but I currently don't see a way to determine if a point is on a row without asking the user to pick points to define the angle to the x axis.  I can then check to see if the point is on the line created from the west point along the user defined bearing. 

Each grid may have 1000 points in it and there are generally 100+ grids to process, so not having user interaction would be preferred.  Does anyone have a better way to tackle this?

Thank you,
Stacy


It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7320
  • AKA Daniel
Re: Creating grid from irregular spaced points
« Reply #1 on: May 26, 2022, 07:17:55 PM »
Its not clear to me how you are creating the grid, haven't had my coffee yet.  :laugh:

Maybe create AcGeCircArc3d objects from your points, with the radius being some allowed tolerance, or its max size before it intersects with another
If the gridline intersects, then consider it on the gridline.

Can you post a sample drawing of points and maybe a before and after shot?

Retired

sdunn

  • Newt
  • Posts: 83
Re: Creating grid from irregular spaced points
« Reply #2 on: May 27, 2022, 11:59:40 AM »
I didn't do a great job of explaining my problem.  The image I included is just a simplified example of my situation.  I don't actually draw the grid. 

Each of the points will receive a designation based on their location within the "grid".  The first point on the left (from north to south) would be designated R2-1-A.  The next point to the south would be R2-1-B and so on. 

kdub

  • Mesozoic keyThumper
  • SuperMod
  • Swamp Rat
  • Posts: 1463
  • class keyThumper<T>:ILazy<T>
Re: Creating grid from irregular spaced points
« Reply #3 on: May 27, 2022, 03:24:42 PM »
Stacy,
You'll still need to provide more information.

But first :
I'd rethink the concept of grid lines.
I'd be thinking of 'zones' . The labelling could be the same as your proposal.
The 'Zone' could be the space between imaginary dividing lines that contain each point.
You could draw the dividing lines to assist with visual checking of the process.

I'd assume you have a minimum / maximum space in mind ?? ( not critical, but it would help )

You'd need to select [ all ] the points to determine the extents of the collection.

The complexity of the sorting algorithm will depend on the regularity of the arrangement.
How will you handle 'stray' points ?

Would the naming convention be consistent ?

You may need to provide X and Y axis markers for the spacing direction, to guide the sorting. A rotated block marker would work. The block could be located at one of the predetermined (say bottom-left ) extreme corners of the arrangement perhaps.

I assume the objects would be 'POINTS' .

What action would the function perform, other than determining the naming designations. ?
add data ?
return a list of names >
return a list of names and points ?
write (what) data to a file ?

Regards,


called Kerry in my other life

Sometimes the question is more important than the answer.

I don't really work crazy hours . . I just live at UTC + 12.00
#ridesober

sdunn

  • Newt
  • Posts: 83
Re: Creating grid from irregular spaced points
« Reply #4 on: May 27, 2022, 04:55:50 PM »
Kerry,

Quote
But first :
I'd rethink the concept of grid lines.
I'd be thinking of 'zones' . The labelling could be the same as your proposal.
The 'Zone' could be the space between imaginary dividing lines that contain each point.
You could draw the dividing lines to assist with visual checking of the process.

It looks like your approach is similar to what I have seen while searching for a better algorithm.  In their approach they created a grid of tiles and checked for points within.  If found, the point was modified.

Quote
I'd assume you have a minimum / maximum space in mind ?? ( not critical, but it would help )

  • The column spacing is usually consistent, but the row spacing can vary. 
  • There are instances where a column may not have the same number of points. 
  • There is a maximum number of points that can reside in each column.  This is what is used to define each section.
  • The sections may or may not have extra space between them. 

Quote
You'd need to select [ all ] the points to determine the extents of the collection.

Each group of points is in a block. The block is defined by a polyline boundary drawn by hand.  I currently use this polyline to select the points within it.

Quote
The complexity of the sorting algorithm will depend on the regularity of the arrangement.
How will you handle 'stray' points ?

So far, the point irregularity is less than half of the grid spacing in either direction. 

Quote
Would the naming convention be consistent ?

For each project, yes.  There are some variances between clients that require changes in the names.  For the attached image, the names would be Block-Section-Column-Row (104-1-2-A). 

Quote
You may need to provide X and Y axis markers for the spacing direction, to guide the sorting. A rotated block marker would work. The block could be located at one of the predetermined (say bottom-left ) extreme corners of the arrangement perhaps.

I currently ask the user to select complete columns of points across all sections.  These are used to determine the row spacing. 

I will start with a list of point objects inside of the block polyline.  I then take the list of user selected points and get the Y value at the limits of each section.  I use these to get the points within that section.

I then sort the points (W to E, N to S) and then iterate the list to add the names.  When I get to the bottom of the column (based on Y coordinate), I reset the name counters.

Quote
I assume the objects would be 'POINTS' .

What action would the function perform, other than determining the naming designations. ?
add data ?

There may be a need to correct the irregularities and align the points to a grid.

return a list of names >
return a list of names and points ?
write (what) data to a file ?

For our usage, changing the name of the Civil 3D cogopoint and adding the individual designations to user defined properties is needed.  The attached image is of an actual drawing and not overly simplified like my first post.  My goal with this post is to see if there is a better approach to accomplish this.  I would also like to eliminate as much user interaction as possible.

Thank you for your feedback.

Stacy

« Last Edit: May 27, 2022, 05:11:43 PM by sdunn »

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 7320
  • AKA Daniel
Re: Creating grid from irregular spaced points
« Reply #5 on: May 27, 2022, 09:11:05 PM »
If Im understanding this correctly, Id start by

Collect all the points.
Create a tolerance for X, Sort by X, maybe use the average of the Xs divided by some value (3)

Create a class GridPoint, with members objectId and a AcGeCircArc3d.
Construct the AcGeCircArc3d from the point coordinates and use the tolerance for X as the radius.

I used a point monitor to visualize,
for each AcGeCircArc3d in AcGeCircArc3dList if X of the cursor intersects

So for the math you can use your X +- tolerance to see if it fits in a bin. (create Y bins if needed)

I have no idea how youd go about creating that blue bin, without some consistent coordinate system   

or am i way off? lol  :mrgreen:

 
« Last Edit: May 27, 2022, 09:24:29 PM by It's Alive! »
Retired

sdunn

  • Newt
  • Posts: 83
Re: Creating grid from irregular spaced points
« Reply #6 on: June 02, 2022, 04:31:27 PM »
You are not too far off.  I haven't had much time to work on automating it this week.  Several of the sites have more non-standard layouts which required me to include more user interaction to define horizontal spacing, assign starting column numbers and section designations.  This eliminates all of the errors from my crappy algorithm, but is a bit slower. 

It isn't pretty, but it ultimately may be the way I handle it.  Thank you both for your input and advice.

Stacy