| Intersection of polyline curve and polygon in 3D [message #69891] |
Mon, 01 March 2010 05:59 |
syonoun
Messages: 1
Registered: March 2010
|
Junior Member |
|
|
I have, say, N arrays of points that make up N polylines in 3D space.
The points that make up the polylines are reasonably close together
(maybe 0.5 voxel resolution). I also have M sets of points that define
M (possibly overlapping) regions in 3D space. I would like to compute,
for each polyline, which of the M regions it passes through. N can be
up to 1 million, and N can be any number, but the max so far is about
615.
What is the best way to do this with IDL? Below I've outlined a couple
of attempts that I think are somewhat simplistic, and so I'm trying to
figure out a better way. I would appreciate any help and/or criticisms
of my attempts:
1) Use IDLgrROIGroup's containsPoints method on each IDLgrPolyline.
This method seems to work, but it seems slower than (2).
2) Create a (xdim,ydim,zdim,M) byte array, and for each m=1…M,
[*,*,*,m] is a 3D binary mask with 1s where the region is active and 0
otherwise. Then,
region_masks = bytarr(xdim,ydim,zdim,M)
for n = 0, N-1 do begin ;; for each polyline
sz_polyline = n_elements(polyline[n])/3 ;; number of points
describing polyline
temp = lonarr(sz_polyline)
for m = 0, M-1 do begin ;; for each region mask
temp[*] = m
test = region_masks[(polyline[n])[0,*], (polyline[n])[1,*],
(polyline[n])[2,*], temp]
hits = where(test ne 0, n_hits)
if (n_hits ne 0) then begin
;; polyline intersects
endif else begin
;; polyline doesn't intersect
endelse
endfor
endfor
This method seems faster than method 1 but requires much more space.
Both methods can fail in the case where a line segment of the polyline
passes through the region, but the points making up the line segment
do not lie in the region. The resolution of the points makes this
rare, but still it is annoying to know that it can happen.
Thanks for any assistance!
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
