Geom.intersect_line_line question

Brett McAllister

Thanks for the reply and suggestion Tig.
For some reason I thought if you use two point3d's to form a line, you created a line segment, instead of an infinite line.
The dangers of coding when your tired.

Regards

Brett

TIG

@brett mcallister said:

Thanks for the reply and suggestion Tig.
For some reason I thought if you use two point3d's to form a line, you created a line segment, instead of an infinite line.
The dangers of coding when your tired.

Regards

Brett

When you specify an edge by two points [confusingly it IS referred to as a 'line' in entities.add_line(pt0,pt1) ] then what you get IS an edge [or a 'line-segment' as you call it]... BUT when you get that edge's 'line' with edge.line then it becomes as infinitely long 'thing' - a vector through a fixed point... that could intersect with other 'lines' - to get 'physical' intersections of edges use a method like I outlined..........

honkinberry

Here's my confusion with the Geom.intersect_line_line --
when I'm processing a large file, that seems to be a huge amount of additional processing, with it always assuming the two lines are infinite.
In particular,


Geom.intersect_line_line(edge1.line,edge2.line)

I can appreciate why it treats them as infinite, but what about this:


Geom.intersect_line_line(edge1.vertices,edge2.vertices)

If it's going to accept the vertices as parameters, why can't it treat them as fixed length?

Put that on my wishlist.

--J

TIG

A 3 item array, and the special kinds of arrays - i.e. a point and a vector both have xyz values.
Many of Sketchup tools also accept a vertex as if it were a point, doing the vertex.position conversion for you.
You can confuse Sketchup by passing something other than a the correct 'types' as a 'line' and thereby having it think it is one.
A 'line' is a two item array containing a point and a vector [or the equivalent arrays for these].
Every edge has a 'line' consisting of its start vertex position [point] and the vector from that point to its end vertex position.
A 'line' in geometry is considered infinite.
So two 'lines' might intersect and return a point, but that intersection-point may well not be on either of the edges that own those 'lines'...
An edge has two vertices - so edge.vertices is effectively returning an array of two xyz arrays [vertex, vertex].
This array of two vertices could be confused as the [point, vector] needed to define that 'line' BUT the second element is a NOT a vector, or anything equivalent to the edge's vector, so the result will be wrong !
If you want to intersect the 'lines' of two edges and find out if its intersection-point [if successful] is physically on one [or both] of those two edges then there are several examples of code to do that. Rick Wilson did one to check if such a point was between the two points defined by the edge's start.position and end.position - i.e. it was on the edge, will additional flags for ignoring/accepting if the point were exactly at a start/end position...
You don't have the right kind of arrays passed from two 'edge.vertices' to get a meaningful intersection with another pair of 'edge.vertices' - there is no vector information in there - that's why edge.line was invented ! It is relatively straightforward to get the two edges' lines, see if they intersect, and then see if the intersection-point falls on neither, one or two of the edges, even checking for start/end-point being coincident with it as valid or not...

honkinberry

Thanks for clarifying a bit.
It's just difficult for the likes of me, coming from a strong background in the CAD realm (AutoCAD and Revit).
In AutoCAD, you have intersect(p1, p2, p3, p4, INF), where INF is the flag to treat the line segments as infinite.
Further, you can very quickly build a selection of all objects within certain bounds.
So coming from that experience, it just feels like I'm having to needlessly iterate through all entities in a model to perform some simple intersection checking.
I've got a routine that does exactly what you describe, but with 1,500 edges in a model (which seems like a ridiculously small set), checking them all against each other just seems to take too long.

--J

thomthom

@honkinberry said:

I've got a routine that does exactly what you describe, but with 1,500 edges in a model (which seems like a ridiculously small set), checking them all against each other just seems to take too long.

What is that routine? Ruby is slow and it behaves in strange ways that I've often find surprising ways to optimize code. If you have a snippet we can have a look and have a stab at it.

honkinberry

So given an array of edges 'elist' (imported from AutoCAD), I'm checking for intersections.


elist.each do |e1|
	# so given this line, we look for intersections, to amend [p1,p2] to [p1,px,pn,p2]
	p1 = e1.start.position
	p2 = e1.end.position
	plist = [p1,p2]
	line1 = e1.line # [point . vector]

	# for this line segment, compare to all other edges
	elist.each do |e2|
		if ( e1 != e2 ) # only if not the same edge of course
			line2 = e2.line # [point . vector]
			v1 = line1[1] # vector
			v2 = line2[1] # vector
					
			if ( v1 != v2 ) # if vectors are differnet, they aren't parallel
				int = Geom.intersect_line_line(line1,line2) # but assumes infinite!
				if ( int ) # make sure it's on both lines, and not an endpoint of line1
					z1 = e2.start.position
					z2 = e2.end.position

					if ( !plist.include?(int) ) # not end point or already found
						if ( pointonline(int,p1,p2) ) # and on line1
							if ( pointonline(int,z1,z2) ) # and on line2
								# so adding our intersection to line 1
								plist << int
							end # if co-linear2
						end # if co-linear1
					end # if not end point
				end # if intersection
			end # if not parallel

		end # if not same segment
	end # subloop

	# ... do stuff with amended plist ...
end # entity loop

Missing is a standard helper function 'pointonline' which checks if given point falls on the given line segment.
Given about 1,500 edges, it seems it can easily take 30 seconds, which just feels far too long for my taste.
Many thanks if you have any tips to optimize it!

--J

TIG

As I thought I explained...
Rick Wilson already made a function called something like
point.between_points?(pt1, pt2, cond)
So to see if a point on a an edge use that passing the edge.start.position and edge.end.position as the arguments - returns true or false: the ' cond' determines if the point that is 'exactly on' the edge's start/end is be be regarded as 'between' the given points...

I posted an example of this three years ago!
http://sketchucation.com/forums/viewtopic.php?p=243509#p243509

Note that changing/adding-to the built-in API class methods is probably not the best way to do it... BUT you can easily use the principal to make your own equivalent of this method, wrapped in your own module/class/methods...

thomthom

Here's my version of it: https://bitbucket.org/thomthom/tt-library-2/src/56b237cae78615e19712faf22980293879916793/TT_Lib2/point3d.rb?at=Version%202.8#cl-28

honkinberry

Sorry, guess I wasn't clear.
I have the pointonline function, and yes, that's easy, hence why I didn't bother including it.
My issue, is that in a model with 1,500 edges, the afore posted routine takes over 30 seconds to complete.
What I was hoping to do, was to optimize that routine if possible. As near as I can tell, I have to iterate through all edges, and compare each to all other edges, perform an intersect_line_line, and then check if that point falls on both edges. Correct?
I tried adding some basic coordinate validation, checking the X and Y coordinates of each edge end point first, to see if an intersection might be possible, but just took even more processing time.
I'm about to check the exact processing hit for each of the key tests, to see what is the big hangup, but thought I'd post what I have so far to see if there's any thing that jumps out as slow.

--J

thomthom

Yea, Ruby is so slow that extra checks might just make it slower. Perhaps you can use the BoundingBox class?

In general, try to make the API methods to the most work as then it's performed in C++.

honkinberry

I've tried a few variations now.
added a BoundingBox intersection testing, and if that hits, then do an intersect_line_line.
That ends up taking about 10% more time.
Then on a whim, I even removed the Vector checking, that saves time.
So no matter what I try, indeed, it seems the fastest is to get to the intersect_line_line as quickly as possible, as that's even faster than comparing the vectors first.

The really unfortunate part, now, is that I've found in trying to add a progress bar at the status line, that just seems to add a huge amount of time to the operation. I'd rather have a spinning pinwheel for 30 seconds than a progress bar for 2 minutes. I guess I could try optimizing the progress bar function, it looks like it's updating the status bar text every iteration, regardless of whether the percentage has changed.

Thanks as always for the tips!

--J

thomthom

Then it sounds like moving to an Ruby C Extension is what might give real performance improvements.