Author Topic: CHALLENGE: Block Elevations to Contours  (Read 7441 times)

0 Members and 1 Guest are viewing this topic.

Atook

  • Swamp Rat
  • Posts: 1027
  • AKA Tim
CHALLENGE: Block Elevations to Contours
« on: October 12, 2021, 04:07:57 PM »
Hey swampers,
I posted earlier about assigning elevations to blocks based on contour lines. There were some good ideas, but unfortunately, I'm too busy to write the thing. So I thought I'd post it here, and opensource the result. I get the code I want, someone gets paid, future programmers get to use the result. A win for everybody, not to mention this could be fairly entertaining. I decided after the fact to include LISP code, so if this post needs to be moved somewhere different, an admin can do that.

PROBLEMS:
The first problem is isolating what objects to use for the elevation models, and where. if possible I'd like to avoid user interaction here, but it may be that the user needs to be prompted for some elevation layers or something. If the solution requires user interaction, your solution must include the interface to do so.

The second problem is interpolating elevation values from the elevation models and assigning those values to blocks. If the points fall within the bounds of the proposed grade, the elevation should be assigned from the proposed grade. If not, they should be assigned from the existing grade.

Challenge drawing files are here.

CODE:
The code has to be .NET C# or LISP. Try to comment it well. Do not post compiled code, I will not run it (and neither should anybody else). Include your username in a comment at the top of the file. All code posted will be public domain. One entry per user.

.NET: post a complete sln file I can open and compile in VS2019 I'll netload the compiled dll into vanilla AutoCAD 2021.

LISP: Post an uncompiled LISP file.

DRAWINGS AND CHALLENGE
QUALIFY.DWG: Create a command 'RACE'. It will prompt the user to select the layers/or objects for both the existing and proposed contours. Using those contours, calculate and set the elevations for the test blocks in Qualifer.dwg. All blocks should get an elevation within .25' of what I've got shown there (after all, my math could be wrong) Note that the base file in the xref is twisted about and not at 0,0 etc. Sometimes CAD monkeys do weird things, and we gotta accomodate that.

RACE.DWG: If your code qualifies, I'll run it 3 times on this drawing on my machine and average the times. I'll be using AutoCAD 2021 for the test. There is a single xref in this drawing that contains all the contours. Code that produces elevations that do not agree to consensus(within .25') with the rest of the entries will not be eligible for the prize. Include a timer in your project. Start the timer from when the user finishes selection of the layers. Print the elapsed time to the command line once the command is complete.

DEADLINE: October 22, 2021, 5pm MST.

PRIZES:
Paid in paypal, crypto, however I can get it to you.
Fastest .NET Solution: $400
Fastest LISP Solution $400
2nd Fastest (either): $100
Donation to Swamp: $200

If there's questions/clarifications needed, I'll do my best to clear them up before the deadline. I should have results the following week.

Good luck!
« Last Edit: October 13, 2021, 03:54:36 AM by Atook »

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: CHALLENGE: Block Elevations to Contours
« Reply #1 on: October 12, 2021, 04:38:42 PM »
Thank you very much for considering a donation to TheSwamp! Any donation, especially one this size, will help me keep this place open and running.

Good luck everyone.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

BIGAL

  • Swamp Rat
  • Posts: 1398
  • 40 + years of using Autocad
Re: CHALLENGE: Block Elevations to Contours
« Reply #2 on: October 13, 2021, 12:27:50 AM »
I think your approach is wrong, yes you can use plines/lines with a Z elevation to make a TIN surface. Once you have a TIN you have a 3dface network of triangles. So the z can be calculated correctly for any point lying on a 3dface, not rocket science and it is out there as a freebie.

Ok over at Cadtutor triangulation by YMG, TriangV0.5.9.LSP may be helpful.

CIV3D has work out a Z for a point built in, includes using lines.

Now where is that point on 3dface code. https://forums.autodesk.com/t5/visual-lisp-autolisp-and-general/choose-point-on-3dface/td-p/1601829

Do I win ? Or did I just save you $$$$ will try to find time to code pt on 3dface as per link.

Ok if you look at help and look into the CAL functions you find this one ilp(p1,p2,p3,p4,p5) so p1 is xyz in plan z can be 0, p2 is the same xy but a dummy Z above the 3dface, p3,p4,p5 are the 3 points of the 3dface.

The other way is using UCS 3 points and the trans function to work out Z.
« Last Edit: October 13, 2021, 01:28:26 AM by BIGAL »
A man who never made a mistake never made anything

VovKa

  • Water Moccasin
  • Posts: 1626
  • Ukraine
Re: CHALLENGE: Block Elevations to Contours
« Reply #3 on: October 13, 2021, 11:14:44 AM »
Fastest LISP Solution
on my ancient pc it took half an hour to complete the RACE.dwg
i don't think LISP is a good choice (even on faster PC)

Atook

  • Swamp Rat
  • Posts: 1027
  • AKA Tim
Re: CHALLENGE: Block Elevations to Contours
« Reply #4 on: October 13, 2021, 11:52:52 AM »
Quote
on my ancient pc it took half an hour to complete the RACE.dwg
:wideeyed:

I wasn't sure what a dataset like that would take to process. I'm looking forward to finding out.

As far as LISP vs .NET goes I really have no idea. I do know that RJP's LISP code consistently runs circles around my .NET code.  :shifty:

Atook

  • Swamp Rat
  • Posts: 1027
  • AKA Tim
Re: CHALLENGE: Block Elevations to Contours
« Reply #5 on: October 13, 2021, 06:21:06 PM »
Quote from: BigAl
I think your approach is wrong..
:yes:

Yup, I'm almost positive my approach can be improved. That's the reason for the challenge. :)

To be clear: I know I'm out of my league here, if you see a better way to extract the data out of the drawings than I suggested, code it up and show us all.  If there's some special way of doing this that's more efficient and works in vanilla CAD, that's what I'm trying to find out. Maybe it's TIN surfaces, maybe it's the Buckminster transform dot multiplied across a unicorn matrix, I really don't know. I expect most/all of the entries will be more efficient than what I would do. Heck, I'm not even sure my math is right, that's why I'm giving a .25 fuzz factor on the elevation answers.

I'm looking forward to learning how the wizards in the community would do this.

BIGAL

  • Swamp Rat
  • Posts: 1398
  • 40 + years of using Autocad
Re: CHALLENGE: Block Elevations to Contours
« Reply #6 on: October 14, 2021, 07:18:10 PM »
The dwgs provided look like they have come from say CIV3D or similar, so getting a TIN as well would make life so much easier. Using just contour lines is not really a good idea unless you convert to a TIN, again though not as good as original TIN.

This is a page from CIV3D help https://knowledge.autodesk.com/support/civil-3d/learn-explore/caas/CloudHelp/cloudhelp/2016/ENU/Civil3D-UserGuide/files/GUID-FDBDB4BD-86C1-4A01-9EC3-FEAEF7DF0A97-htm.html

Ok so (command "cal" "ilp(p1,p2,p3,p4,p5)") will return a point XYZ of intersection of 3dface, p3 p4 p5, with a line p1 p2, p1 would have say z = 0 and p2 z =10000.

So I would take a point do a ssget 3Dfaces around it using a range, dwg may have 10,000 triangles, so maybe get only 20 3dfaces, and do the ILP with no 3dfaces from you no code. Would be very fast as not looking at all 3dfaces .

Some test code but need your dwg with 3dfaces before I continue.


Code: [Select]
(defun c:test ( )
(while (setq p1 (getpoint "\npick point"))
(setq p2 (mapcar '+ p1 (list 0.0 0.0 10000.0)))
(setq 3d (entget (car (entsel "\npick 3dface"))))
(setq p3 (cdr (assoc 10 3d)))
(setq p4 (cdr (assoc 11 3d)))
(setq p5 (cdr (assoc 12 3d)))
(setq  zpt  (cal "ilp(p1,p2,p3,p4,p5)"))
(if (= zpt nil)
(princ "\nPoint not on 3dface")
(alert (strcat "\nPoint is X= " (rtos (car zpt) 2 3)  " Y= "  (rtos (cadr zpt) 2 3) " Z= " (rtos (caddr zpt) 2 3)))
)
(setq zpt nil)
)
(princ)
)
(c:test)
« Last Edit: October 14, 2021, 08:07:38 PM by BIGAL »
A man who never made a mistake never made anything

Atook

  • Swamp Rat
  • Posts: 1027
  • AKA Tim
Re: CHALLENGE: Block Elevations to Contours
« Reply #7 on: October 14, 2021, 10:15:39 PM »
The dwgs provided look like they have come from say CIV3D or similar..

I'm looking to use this code in an app for vanilla AutoCAD/BricsCAD. I don't have Civil3D, but we get drawings like this all the time from clients. The app needs to work without Civil3D.

Atook

  • Swamp Rat
  • Posts: 1027
  • AKA Tim
Re: CHALLENGE: Block Elevations to Contours
« Reply #8 on: October 23, 2021, 12:51:31 PM »
Dang! No takers?

How could I have organized this to have more people interested? Suggestions welcome.

huiz

  • Swamp Rat
  • Posts: 913
  • Certified Prof C3D
Re: CHALLENGE: Block Elevations to Contours
« Reply #9 on: October 23, 2021, 05:36:07 PM »
Well, personally I don't understand the chalence. You want to have a function that takes two selection sets of contourlines but then you want that function also run on one set of contourlines.


Also the qualification of reading xrefs and ucs things, what do you actually want? Is that a complete application with just that functionality or rather code that handles a process? In the latter case it is better to focus on issues like how to handle breaklines, contours with curves, crossing contours, given or calculated boundaries, etc.


I do have some code available that creates a triangulation of a series of points and it is not that difficult to calculate the position of a point inside a triangle like Bigal also suggest. But I don't feel the urge to spent a lot of time to write all that other code :-)


But that is a personal feeling.
The conclusion is justified that the initialization of the development of critical subsystem optimizes the probability of success to the development of the technical behavior over a given period.

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #10 on: October 24, 2021, 09:36:01 PM »
Immediately disqualified for two reasons, its compiled, its C++, and it has limitations.

1, I had to hard code a command for each drawing, “Qualify” and “Race”. The drawings are way different in their structure, one has a nested xref, the other does not. So I didn’t bother.

2,  wont adjust block refs that don’t fall inside a triangle.

3, my TIN is pretty slow, I’ll try to improve this

4, I will share the source, but now it’s a hack and embarrassing 

5, it may crash and burn down your office

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #11 on: October 24, 2021, 09:37:00 PM »
Immediately disqualified for two reasons, its compiled, its C++, and it has limitations.

see! I can't even count

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #12 on: October 25, 2021, 01:51:21 AM »
this one is like wicked fast! changed to using this https://github.com/delfrrr/delaunator-cpp
I had to modify it to make it 3d.

Race went from 12 seconds to 0.249 seconds


It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #13 on: October 25, 2021, 02:55:18 AM »
Here’s the source for inspiration.

Steps.
Collect points from polylines using the elevation as Z;
Transform the points by blocktransform of the xref;
Run Delaunay triangulation
If the block is inside of a triangle, convert the triangle to a AcDbSurface, then AcGeSurface, then getClosestPointTo AcGePointOnSurface using the block position
Move the block

Notes Selecting the blocks to move would be easier if they were on their own layer, so they can be moved all at once.

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #14 on: October 25, 2021, 03:51:46 AM »
the delaunator is really fast, here's the output for a quality check. couple weird spots so I don't know if its good enough for this challenge

Atook

  • Swamp Rat
  • Posts: 1027
  • AKA Tim
Re: CHALLENGE: Block Elevations to Contours
« Reply #15 on: October 25, 2021, 04:04:27 PM »
@huiz: the intent was to end up with a command that would assign elevations from contours in an xref. The drawing was messy (twisted xrefs, etc) because I wanted to correctly work with messy drawings received from clients. Perhaps in the future I'll make more simple single pointed challenges.

@Daniel: I'll have to check out your code, looks like you got the gist of it! I'm curious to look at the delaunator code to see what speeded up the triangulation so much. Thanks for posting.

EDIT: Wow that second version is fast! Maybe I'll have to look at how to call C++ code from my .NET app..
« Last Edit: October 25, 2021, 04:17:09 PM by Atook »

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #16 on: October 25, 2021, 06:16:12 PM »
There’s a C# version https://github.com/nol1fe/delaunator-sharp
Not sure if it’s the same behavior, the rest of my code should be easy to port to .net, I mean if what I have gives the correct behavior.
I don’t know how to handle blocks that fall outside the TIN though.


It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #17 on: October 25, 2021, 08:45:36 PM »
I used the .net port in Acad and Bcad and its crazy fast too!
I've attached a solution. Delaunator is 2d, just save a container of the Zs to add back in.


It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #18 on: October 26, 2021, 12:14:00 AM »
I’ve ported everything except the command qualify. Some times for the race command in milliseconds. My C# is very rusty, so maybe someone can optimize it. There’s still the issue of the edge cases that need to be solved.

C++ac = 21244
C#ac =   37463
C#bc =  36435

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #19 on: October 26, 2021, 05:41:27 AM »
Got the c++ version cooking, my C# still sucks,  I changed the method of finding the point on the triangle, seems it has much better accuracy ,
I need to do a QAULIFY command to test, but I did test with the C++ version

C++ac  =  6140ms
C#ac  =   16045ms
C#ac   = 14529ms
   

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #20 on: October 26, 2021, 08:49:21 AM »
Wrapped everything inside of parallel foreach, now the time is:
AcC# MgdTestAcad_04.dll = Total Time in Milliseconds = 2944;
BcC# MgdTestAcad_04.dll = Total Time in Milliseconds = 2862;

well need some sort of a unit test to make sure im not breaking stuff

« Last Edit: October 27, 2021, 08:17:54 AM by It's Alive! »

Atook

  • Swamp Rat
  • Posts: 1027
  • AKA Tim
Re: CHALLENGE: Block Elevations to Contours
« Reply #21 on: October 26, 2021, 02:10:14 PM »
Daniel, thanks so much for posting and translating your solutions!

I've awarded you one of the 1st place ($400) prizes, which you kindly directed to be donated directly to the swamp.

Looking forward, if I run any future challenges, I'll work on breaking it down into single tasks to make participation easier.

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: CHALLENGE: Block Elevations to Contours
« Reply #22 on: October 26, 2021, 03:42:07 PM »
*shocked!* I'm speechless! Thank you very much you guys! We have this years bills for the swamp paid. Thank you, very much.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #23 on: October 27, 2021, 04:36:37 AM »
Moved function static pointInTriangle to a local function, which really helped. I think I’ve squeezed about all the performance out of it.

Race MgdTestBcad_06.dll, Total Time in Milliseconds = 1763

I’m not sure how nested XREFs store block transformations, I’ll look into this next, to easily handle drawings like QUALIFY.
Also, I’ll think of a way to catch these outside cases that are outside the TIN, maybe generate a convex hull and use the elevation of the nearest segment ..?..

edit, added method maketin, to create the triangles, for testing that the routine is correct

« Last Edit: October 27, 2021, 08:17:39 AM by It's Alive! »

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #24 on: October 27, 2021, 05:31:27 AM »
I don't think its correct now, testing, fixing

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #25 on: October 27, 2021, 07:15:43 AM »
I don't think its correct now, testing, fixing

whew, fixed it, projecting the point on to the triangle was wrong.. i'll post after more testing

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #26 on: October 27, 2021, 08:22:21 AM »
Fixed the projecting the point onto the triangle, so the math “should” be correct.
I’ll work on the block transformations next, the interface should be, select the xref, select the blocks to move and let’r rip. 

Atook

  • Swamp Rat
  • Posts: 1027
  • AKA Tim
Re: CHALLENGE: Block Elevations to Contours
« Reply #27 on: October 27, 2021, 12:46:09 PM »
Also, I’ll think of a way to catch these outside cases that are outside the TIN, maybe generate a convex hull and use the elevation of the nearest segment ..?..

I was going to just interpolate the outside points to the nearest two points. My guess is the math works out close or equal to the convex hull approach..

Thanks for noodling into this Daniel, it's fun to watch you solve things way beyond my level.. :)

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #28 on: October 27, 2021, 10:20:06 PM »
I have it running where, just select a polyline, select all the blocks to move and it will rip, the nested transformations seems correct on both race and qualify drawings.
But I found an issue. Drawing Civil base has extra geometry at a far different elevation, these polylines are included and screw up the math. So we’d need a way to filter.

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #29 on: October 27, 2021, 10:47:02 PM »
This one should work on any drawing that has an xref that contains polylines.
the command are race and maketin.

race, select a polyline that's in the xref, window all the refs to move and press enter.

run race, then run maketin to verify the triangles are aligned, you can iterate the face vertexes in the properties panel.

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #30 on: October 28, 2021, 06:16:24 AM »
BTW Let me know if something doesn’t work. I’m out of quarantine this weekend, I’ll be at the beach redoing my tan  :laugh:

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #31 on: October 28, 2021, 07:03:52 PM »
I think the convex hull idea will work fine, I tried to convert gile’s 2d version to just carry along the Z value, but I messed up somewhere. But it’s a proof of concept
https://www.theswamp.org/index.php?topic=31865.msg429538#msg429538

here's a before and after. I added a new command "makehull" to have a visual test


It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #32 on: October 28, 2021, 07:09:30 PM »
hull works here, so something may just need minor corrections  :laugh:

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #33 on: October 28, 2021, 08:43:20 PM »
Found a fast hull routine here https://stackoverflow.com/a/46371357
BlockRefs modified = 2816, BlockRefs not modified = 0 :
Total Time in Milliseconds = 1866

But I don’t think the accuracy will be as good as if the hull contains each segment.
So.. more proof of concept  :laugh:


It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #34 on: October 29, 2021, 06:09:10 AM »
convex hull is not the correct tool, we're looking for a alpha shape or concave hull

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #35 on: November 15, 2021, 05:03:08 AM »
modified the concave hull routine here,  https://www.theswamp.org/index.php?topic=57135.0
I'm not brave enough to port it to .NET though, maybe someone here can. there's also a java script version it might be easier to port from.
link is in the code;

I think this would be a better tool to get the blocks that are outside the TIN, and also it may be useful to cleanup the TIN, I.e. if an edge is outside the hull, don't create the triangle.

tough task  :mrgreen:

Atook

  • Swamp Rat
  • Posts: 1027
  • AKA Tim
Re: CHALLENGE: Block Elevations to Contours
« Reply #36 on: November 15, 2021, 11:44:26 AM »
tough task  :mrgreen:

Yeah, it's interesting to me when I look at these these types of problems, how something that looks simple can be so complex.

My take on it was pull each block out of the collection when it was found inside of a triangle. Once all the blocks inside triangles had been processed take the remainder of the collection, and interpolate them between the nearest two points of the TIN.

I haven't had time to program recently  :cry: so I'll have to wait to give this a shot.

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #37 on: November 16, 2021, 04:02:00 AM »
Possible inspiration, with a constrained TIN (c++ source
https://www.theswamp.org/index.php?topic=57122.msg607079#msg607079 )

It may be possible to run the tin inside the boundary, and again on the outside, but include the position of the blocks in the outside tin. It may make finding the triangles attached to the block easier, combined with mojo to guesstimate the Z from the other two points


It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: CHALLENGE: Block Elevations to Contours
« Reply #38 on: November 24, 2021, 05:39:49 AM »
https://www.theswamp.org/index.php?topic=57122.0
I posted an algorithm, that if it works for the project should be able to be fairly easy to port to .NET
In function Createctin2.
1, generate the tin, save the triangles
2, filter triangles by angle to remove the outside edges, save these triangles.
3, iterate all the filtered triangle edges. Edges the don’t have a match are outside edges. I used a dictionary for this.
4, iterate all the outside triangles and order them clockwise.
5, iterate the outside edges, add the points to the polyline.
6, using the original tin, if the center of the triangle is inside the polyline, keep it.

I actually spent time trying to port Createctin to .NET, I tried to hand roll a R-tree and priority_queue classes but failed.

Atook

  • Swamp Rat
  • Posts: 1027
  • AKA Tim
Re: CHALLENGE: Block Elevations to Contours
« Reply #39 on: November 24, 2021, 12:20:24 PM »
Thanks Daniel!