Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

header-only implementation of intersection #765

Closed
3 tasks done
Tracked by #648
isVoid opened this issue Oct 31, 2022 · 0 comments · Fixed by #852
Closed
3 tasks done
Tracked by #648

header-only implementation of intersection #765

isVoid opened this issue Oct 31, 2022 · 0 comments · Fixed by #852
Assignees
Labels
0 - Backlog In queue waiting for assignment
Milestone

Comments

@isVoid
Copy link
Contributor

isVoid commented Oct 31, 2022

Implement header only API for intersection_count and intersection.

template<typename Range1, typename Range2, typename OutputIt>
OutputIt pairwise_linestring_intersection(Range1 multilinestrings1, Range2 multilinestring2, OutputIt output_begin, stream);

template<typename Range1, typename Range2, typename OutputIt>
OutputIt pairwise_linestring_intersection_count(Range1 multilinestring1, Range2 multilinestring2, OutputIt output_begin, stream);

Depending on #763 and #764. With the help of these primitive and data structures, I posturizes that the kernel should be parallelized on 1-segment per thread and iterate on the multilinestring in the other multilinestring.

Kernel pseudo code without needing to write indices

__global__ void intersection_count_kernel(range1, range2, output):
	tidx = get_threadidx()
	Segment seg1 = range1.segment(tidx)
	For (mls : range2)
		For (seg2 : mls)
			Point_opt, line_opt = segment_intersection(seg1, seg2)
			If (point_opt != nullopt)
				atomicInc(Output[tidx].num_intersecting_points)
			If (line_opt != nullopt)
				atomicInc(Output[tidx].num_overlapping_segments)
__global__ void intersection_kernel(range1, range2, temp_storage, output):
	tidx = get_threadidx()
	Segment seg1 = range1.segment(tidx)
	For (mls : range2)
		For (seg2 : mls)
			point_opt, line_opt = segment_intersection(seg1, seg2)
			If (point_opt != nullopt)
				Npoint = atomicReadAndInc(temp_storage.npoint)
				Output[npoint] = point_opt.value()
			If (line_opt != nullopt)
				NLine  = atomicReadAndInc(temp_storage.nline)
				Output[nLine] = line_opt.value()

[UPDATE: 11-8]
count API is only counting the upper bound of the number of intersection/overlaps - it does not give any promises to the number of results. So count will not be exposed as a public API.

#765 (comment)

@isVoid isVoid self-assigned this Oct 31, 2022
@isVoid isVoid added the 0 - Backlog In queue waiting for assignment label Oct 31, 2022
@isVoid isVoid added this to the DE-9IM milestone Oct 31, 2022
@isVoid isVoid changed the title header-only implementation of intersection_count/intersection header-only implementation of intersection Nov 9, 2022
rapids-bot bot pushed a commit that referenced this issue Dec 14, 2022
…851)

#813 adds a struct to hold the intermediate result from `linestring_intersection_with_duplicates`. After discovering the duplicates from the result, we need a way to remove these geometries from the struct, as well as updating the offsets and look-back ids. This PR adds a `remove_if` function to the struct, which models after `thrust::remove_if` that accepts a range of flags, and removes the geometries in the intermediates where the flag is set to 1.

Closes #853 
Depends on #813. Contributes to #765.

Authors:
  - Michael Wang (https://github.com/isVoid)

Approvers:
  - Mark Harris (https://github.com/harrism)
  - H. Thomson Comer (https://github.com/thomcom)

URL: #851
@rapids-bot rapids-bot bot closed this as completed in #852 Dec 16, 2022
rapids-bot bot pushed a commit that referenced this issue Dec 16, 2022
This PR adds header only API `pairwise_linestring_intersection`. Closes #765 .

Depends on #813 #818 #819 #851

Authors:
  - Michael Wang (https://github.com/isVoid)

Approvers:
  - Mark Harris (https://github.com/harrism)
  - H. Thomson Comer (https://github.com/thomcom)

URL: #852
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
0 - Backlog In queue waiting for assignment
Projects
Status: Done
Development

Successfully merging a pull request may close this issue.

1 participant