/*
Line segment intersection detection library.
Copyright (C) 2021 eadf https://github.com/eadf
This program is free software: you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation, either version 3 of the License, or (at your option) any later
version.
This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with
this program. If not, see .
Also add information on how to contact you by electronic and paper mail.
If the program does terminal interaction, make it output a short notice like
this when it starts in an interactive mode:
intersection2d Copyright (C) 2021 eadf
This program comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
This is free software, and you are welcome to redistribute it under certain
conditions; type `show c' for details.
The hypothetical commands `show w' and `show c' should show the appropriate
parts of the General Public License. Of course, your program's commands might
be different; for a GUI interface, you would use an "about box".
You should also get your employer (if you work as a programmer) or school,
if any, to sign a "copyright disclaimer" for the program, if necessary. For
more information on this, and how to apply and follow the GNU GPL, see .
The GNU General Public License does not permit incorporating your program
into proprietary programs. If your program is a subroutine library, you may
consider it more useful to permit linking proprietary applications with the
library. If this is what you want to do, use the GNU Lesser General Public
License instead of this License. But first, please read .
*/
use fltk::{app, draw, enums, prelude::*, window};
use intersect2d::algorithm::AlgorithmData;
use intersect2d::{scale_to_coordinate, to_lines, IntersectError};
use itertools::Itertools;
use std::cell::RefCell;
use std::rc::Rc;
const DRAW_TEXT: bool = true;
/// combining iterative and non-iterative compute() complicates things a bit..
type AlgoType = Rc<
RefCell<(
AlgorithmData,
Option, Vec)>, IntersectError>>,
)>,
>;
fn main() -> Result<(), IntersectError> {
let app = app::App::default();
let mut wind = window::Window::default()
.with_size(800, 800)
.center_screen()
.with_label("Iterative sweep-line intersection algorithm, press space to step");
wind.set_color(enums::Color::Black);
wind.end();
wind.show();
let alg_data: AlgoType = Rc::from(RefCell::from((AlgorithmData::::default(), None)));
let alg_data_c = alg_data.clone();
add_data(alg_data_c)?;
let alg_data_c = alg_data.clone();
// This is called whenever the window is drawn and redrawn (in the event loop)
wind.draw(move |_| {
let alg_data_b = alg_data_c.borrow();
draw::set_draw_color(enums::Color::White);
if DRAW_TEXT {
let mut astring = String::from("'ignore_end_point_intersections' is ");
if alg_data_b.0.ignore_end_point_intersections {
astring.push_str("true");
} else {
astring.push_str("false");
}
draw::draw_text(astring.as_str(), 30, 30);
draw::draw_text(&"Press space to step".to_string(), 30, 45);
draw::draw_text(&"Press 'c' to complete".to_string(), 30, 60);
}
// draw sweep-line
draw::set_draw_color(enums::Color::Blue);
let sweepline = alg_data_b.0.get_sweepline_pos();
draw::draw_line(0, sweepline.y as i32, 800, sweepline.y as i32);
draw::set_draw_color(enums::Color::White);
for (line_index, line) in alg_data_b.0.get_lines().iter().enumerate() {
if line.end.y > sweepline.y {
draw::set_draw_color(enums::Color::Green);
} else {
draw::set_draw_color(enums::Color::White);
}
draw::draw_line(
line.start.x as i32,
line.start.y as i32,
line.end.x as i32,
line.end.y as i32,
);
if DRAW_TEXT {
let text_coord = scale_to_coordinate(&line.start, &(line.end - line.start), 0.45);
draw::draw_text(
&line_index.to_string(),
text_coord.x as i32 + 7,
text_coord.y as i32 + 7,
);
}
}
// draw end points not handled yet.
draw::set_draw_color(enums::Color::Green);
for (k, _v) in alg_data_b.0.get_site_events().as_ref().unwrap().iter() {
draw::draw_circle(k.pos.x, k.pos.y, 2.0);
}
// draw found intersections
draw::set_draw_color(enums::Color::Yellow);
if let Some(r) = alg_data_b.0.get_results() {
for (k, _v) in r.iter() {
draw::draw_circle(k.pos.x, k.pos.y, 2.0);
}
}
if let Some(Ok(r)) = alg_data_b.1.as_ref() {
for (k, _v) in r.iter() {
draw::draw_circle(k.x, k.y, 2.0);
}
}
// draw found intersections, not reported yet
for (k, _v) in alg_data_b.0.get_site_events().as_ref().unwrap().iter() {
if _v.get_intersections().is_some() {
draw::draw_circle(k.pos.x, k.pos.y, 2.0);
}
}
// draw active lines
draw::set_draw_color(enums::Color::Red);
for line_index in alg_data_b.0.get_active_lines().iter().flatten() {
let line = alg_data_b.0.get_lines()[*line_index];
draw::draw_line(
line.start.x as i32,
line.start.y as i32,
line.end.x as i32,
line.end.y as i32,
);
if DRAW_TEXT {
let text_coord = scale_to_coordinate(&line.start, &(line.end - line.start), 0.45);
draw::draw_text(
&line_index.to_string(),
text_coord.x as i32 + 7,
text_coord.y as i32 + 7,
);
}
}
// draw current position
draw::set_draw_color(enums::Color::Red);
draw::draw_circle(sweepline.x, sweepline.y, 3.0);
draw::set_draw_color(enums::Color::Blue);
draw::draw_circle(sweepline.x, sweepline.y, 4.0);
});
let alg_data_c = Rc::clone(&alg_data);
wind.handle(move |_, ev| match ev {
enums::Event::KeyUp => {
let app_event_txt = &app::event_text() as &str;
if app_event_txt == " " || app_event_txt == "c" {
let done = {
let alg_data_c = Rc::clone(&alg_data_c);
let mut data = alg_data_c.borrow_mut();
if app_event_txt == " " {
match data.0.compute_iterative() {
Ok(done) => {
if done {
match data.0.take_results() {
Ok(rv) => {
// convert the result iterator into a vec
// i don't know why .collect() does not work.
let mut res =
Vec::<(geo::Coordinate, Vec)>::new();
for v in rv {
res.push(v)
}
data.1 = Some(Ok(res));
}
Err(err) => data.1 = Some(Err(err)),
}
}
done
}
Err(some_error) => {
data.1 = Some(Err(some_error));
true
}
}
} else {
// app_event_txt == "c"
match data.0.compute() {
Ok(rv) => {
// convert the result iterator into a vec
// i don't know why .collect() does not work.
let mut res = Vec::<(geo::Coordinate, Vec)>::new();
for v in rv {
res.push(v)
}
data.1 = Some(Ok(res));
}
Err(err) => data.1 = Some(Err(err)),
}
true
}
};
if done {
//let alg_data_clone = Rc::clone(&alg_data_c);
//generate_test(alg_data_clone);
let alg_data_clone = Rc::clone(&alg_data_c);
print_results(alg_data_clone);
}
app::redraw();
};
true
}
enums::Event::Released => {
let event = &app::event_coords();
println!("mouse at {:?}", event);
true
}
_ => false,
});
app.run().unwrap();
Ok(())
}
/// draws a line pivoting around (x,y) with 'angle' in degrees
/// l1 & l2 are lengths
#[allow(dead_code)]
fn pivot(x: f64, y: f64, l1: f64, l2: f64, angle: f64) -> geo::Line {
let l = geo::Line {
start: geo::Coordinate {
x: x + angle.to_radians().cos() * l1,
y: y + angle.to_radians().sin() * l1,
},
end: geo::Coordinate {
x: x + (angle + 180.0).to_radians().cos() * l2,
y: y + (angle + 180.0).to_radians().sin() * l2,
},
};
// nudge the result so that it really pivots at the (x,y) point
let v = l.end - l.start;
let v1 = -v * (l1 / (l1 + l2));
let v2 = v * (l2 / (l1 + l2));
geo::Line {
start: geo::Coordinate {
x: x + v1.x,
y: y + v1.y,
},
end: geo::Coordinate {
x: x + v2.x,
y: y + v2.y,
},
}
}
// add the missing '.' to printed floats
fn float_to_string(value: f64) -> String {
let mut rv = format!("{}", value);
if !rv.contains('.') {
rv.push('.');
}
rv
}
/// generate test code from result. Be careful..
#[allow(dead_code)]
fn generate_test(data: AlgoType) {
let data = data.borrow_mut();
let lines = data.0.get_lines().iter().count();
println!("let _l:[[f64;4];{}]=[", lines);
for (i, l) in data.0.get_lines().iter().enumerate() {
print!(
" [{},{},{},{}]",
float_to_string(l.start.x),
float_to_string(l.start.y),
float_to_string(l.end.x),
float_to_string(l.end.y)
);
if i == lines - 1 {
println!("];");
} else {
println!(",");
}
}
println!("let _l = to_lines(&_l);");
println!("let result = AlgorithmData::::default()");
if data.0.ignore_end_point_intersections {
println!(" .with_ignore_end_point_intersections(true)?");
} else {
println!(" .with_ignore_end_point_intersections(false)?");
}
println!(" .with_lines(_l.iter())?");
println!(" .compute()?;");
if let Some(Ok(results)) = data.1.as_ref() {
println!("let mut iter = result.iter();");
if results.iter().count() == 0 {
println!("//No result!");
println!("assert!(iter.next().is_none());");
}
for r in results.iter() {
println!("let (k, i) = iter.next().unwrap();");
println!(
"let intersection = SiteEventKey::new({},{});",
float_to_string(r.0.x),
float_to_string(r.0.y)
);
print!("let lines =[");
for l in r.1.iter().sorted() {
print!("{},", l);
}
println!("];");
println!("assert_eq!(&intersection, k);");
println!("assert_eq!( i.iter().collect::>().sort(), lines.iter().collect::>().sort());");
println!("assert_eq!(&intersection, k);");
println!("assert_eq!( i.iter().collect::>().sort(), lines.iter().collect::>().sort());");
println!("for lineid_1 in i.iter().rev().skip(1) {{");
println!(" for lineid_2 in i.iter().skip(1) {{");
println!(" if lineid_1 == lineid_2 {{continue}}");
println!(" println!(\"line1:{{}} line2:{{}}\", lineid_1, lineid_2);");
println!(" assert!(_l[*lineid_1].intersects(&_l[*lineid_2]));");
println!(" }}");
println!("}}");
}
}
println!("Ok(())");
}
fn print_results(data: AlgoType) {
let data = data.borrow_mut();
if let Some(Ok(data_1)) = data.1.as_ref() {
let intersections = data_1.iter().map(|x| x.1.iter()).flatten().count() / 2;
for r in data_1.iter() {
print!("Intersection @({:.4},{:.4}) lines:", r.0.x, r.0.y);
for l in r.1.iter() {
print!("{},", l);
}
println!();
}
println!("In total {} unique intersection points.", intersections);
let size = data.0.get_lines().len();
println!(
"Made {} calls to intersect() for {} line segments. Brute force approach would need at least {} calls (n²/2)",
data.0.get_intersection_calls(),
size, size*size/2
);
}
}
/// Add data to the input lines. Populate the event queue
fn add_data(data: AlgoType) -> Result<(), IntersectError> {
let mut data_b = data.borrow_mut();
let _l: [[i32; 4]; 356] = [
[402, 20, 395, 20],
[408, 23, 402, 20],
[476, 27, 469, 26],
[328, 26, 322, 28],
[335, 29, 328, 26],
[481, 33, 476, 27],
[322, 28, 318, 33],
[264, 49, 257, 47],
[548, 50, 540, 47],
[257, 47, 250, 51],
[552, 56, 548, 50],
[395, 20, 370, 57],
[429, 57, 408, 23],
[362, 58, 335, 29],
[469, 26, 438, 58],
[370, 57, 362, 58],
[438, 58, 429, 57],
[495, 69, 481, 33],
[318, 33, 305, 69],
[295, 71, 264, 49],
[540, 47, 504, 71],
[504, 71, 495, 69],
[305, 69, 295, 71],
[198, 82, 191, 82],
[613, 85, 607, 81],
[191, 82, 185, 87],
[393, 87, 404, 87],
[382, 93, 393, 87],
[616, 92, 613, 85],
[404, 87, 415, 94],
[558, 94, 552, 56],
[250, 51, 241, 94],
[241, 94, 233, 98],
[566, 98, 558, 94],
[233, 98, 198, 82],
[607, 81, 566, 98],
[377, 103, 382, 93],
[415, 94, 420, 104],
[615, 107, 616, 92],
[377, 115, 377, 103],
[420, 104, 420, 115],
[615, 120, 615, 107],
[382, 125, 377, 115],
[420, 115, 414, 125],
[451, 124, 471, 128],
[318, 131, 348, 124],
[140, 128, 133, 129],
[667, 130, 660, 128],
[185, 87, 185, 131],
[614, 131, 615, 120],
[392, 131, 382, 125],
[414, 125, 403, 131],
[403, 131, 392, 131],
[670, 134, 667, 130],
[133, 129, 128, 134],
[471, 128, 510, 141],
[185, 131, 177, 136],
[622, 136, 614, 131],
[289, 142, 318, 131],
[177, 136, 140, 128],
[660, 128, 622, 136],
[671, 140, 670, 134],
[262, 155, 289, 142],
[510, 141, 545, 160],
[348, 124, 384, 162],
[237, 172, 262, 155],
[405, 165, 451, 124],
[384, 162, 395, 167],
[395, 167, 405, 165],
[545, 160, 577, 183],
[128, 134, 136, 177],
[663, 177, 671, 140],
[213, 191, 237, 172],
[668, 185, 663, 177],
[136, 177, 131, 185],
[131, 185, 92, 183],
[707, 183, 668, 185],
[713, 186, 707, 183],
[92, 183, 85, 186],
[717, 191, 713, 186],
[85, 186, 82, 191],
[577, 183, 606, 210],
[717, 198, 717, 191],
[82, 191, 82, 198],
[192, 211, 213, 191],
[490, 211, 192, 211],
[501, 213, 490, 211],
[606, 210, 630, 242],
[701, 233, 717, 198],
[82, 198, 98, 233],
[529, 222, 501, 213],
[705, 241, 701, 233],
[98, 233, 94, 241],
[630, 242, 641, 259],
[94, 241, 56, 248],
[743, 248, 705, 241],
[56, 248, 50, 250],
[749, 250, 743, 248],
[50, 250, 47, 257],
[752, 258, 749, 250],
[47, 257, 49, 264],
[750, 264, 752, 258],
[584, 271, 556, 238],
[119, 293, 132, 291],
[666, 292, 677, 294],
[132, 291, 142, 295],
[728, 295, 750, 264],
[49, 264, 71, 295],
[654, 296, 666, 292],
[728, 296, 728, 295],
[172, 296, 211, 296],
[590, 305, 584, 271],
[211, 296, 211, 474],
[641, 259, 622, 304],
[173, 299, 172, 296],
[337, 298, 337, 350],
[337, 298, 432, 298],
[432, 298, 435, 298],
[111, 301, 119, 293],
[677, 294, 686, 302],
[71, 295, 69, 301],
[69, 301, 69, 302],
[150, 305, 142, 295],
[647, 305, 654, 296],
[69, 302, 69, 305],
[730, 305, 728, 296],
[435, 298, 457, 308],
[106, 311, 111, 301],
[686, 302, 690, 312],
[150, 305, 152, 316],
[646, 317, 647, 305],
[69, 305, 33, 318],
[767, 318, 730, 305],
[622, 304, 613, 322],
[108, 323, 106, 311],
[457, 308, 465, 325],
[690, 312, 688, 324],
[33, 318, 27, 323],
[772, 324, 767, 318],
[184, 326, 173, 299],
[152, 316, 147, 326],
[649, 328, 646, 317],
[773, 329, 772, 324],
[27, 323, 26, 330],
[582, 337, 590, 305],
[115, 332, 108, 323],
[613, 322, 613, 333],
[688, 324, 681, 333],
[147, 326, 138, 334],
[659, 335, 649, 328],
[770, 335, 773, 329],
[181, 337, 184, 326],
[126, 336, 115, 332],
[138, 334, 126, 336],
[681, 333, 670, 337],
[465, 325, 458, 340],
[670, 337, 659, 335],
[613, 333, 618, 342],
[174, 344, 181, 337],
[123, 367, 174, 344],
[458, 340, 438, 348],
[438, 348, 428, 350],
[428, 350, 337, 350],
[26, 330, 58, 362],
[742, 362, 770, 335],
[618, 342, 675, 369],
[742, 369, 742, 362],
[548, 374, 582, 337],
[675, 369, 676, 369],
[742, 370, 742, 369],
[58, 362, 57, 370],
[533, 383, 548, 374],
[121, 387, 123, 367],
[57, 370, 23, 391],
[742, 370, 776, 391],
[550, 397, 533, 383],
[780, 396, 776, 391],
[23, 391, 20, 397],
[558, 405, 550, 397],
[780, 402, 780, 396],
[20, 397, 20, 404],
[562, 410, 558, 405],
[776, 408, 780, 402],
[565, 416, 562, 410],
[676, 369, 677, 418],
[569, 422, 565, 416],
[123, 423, 121, 387],
[677, 418, 647, 418],
[647, 418, 645, 420],
[337, 425, 411, 425],
[337, 476, 337, 425],
[411, 425, 417, 426],
[742, 429, 776, 408],
[20, 404, 57, 429],
[574, 438, 569, 422],
[417, 426, 434, 434],
[645, 420, 644, 442],
[742, 438, 742, 429],
[57, 429, 58, 438],
[126, 449, 123, 423],
[434, 434, 450, 456],
[450, 456, 453, 463],
[644, 442, 637, 463],
[580, 462, 574, 438],
[58, 438, 29, 464],
[770, 464, 742, 438],
[132, 474, 126, 449],
[588, 470, 580, 462],
[773, 471, 770, 464],
[29, 464, 26, 471],
[637, 463, 623, 473],
[211, 474, 132, 474],
[605, 475, 588, 470],
[623, 473, 605, 475],
[406, 476, 337, 476],
[771, 477, 773, 471],
[26, 471, 28, 478],
[407, 478, 406, 476],
[766, 481, 771, 477],
[730, 495, 766, 481],
[28, 478, 69, 495],
[728, 504, 730, 495],
[69, 495, 71, 504],
[453, 463, 464, 515],
[464, 515, 467, 527],
[71, 504, 49, 535],
[752, 540, 728, 504],
[49, 535, 47, 541],
[47, 541, 50, 548],
[749, 548, 752, 540],
[467, 527, 485, 552],
[50, 548, 56, 552],
[743, 552, 749, 548],
[705, 558, 743, 552],
[56, 552, 94, 558],
[407, 560, 407, 478],
[485, 552, 502, 562],
[407, 561, 407, 560],
[502, 562, 506, 562],
[405, 562, 407, 561],
[621, 562, 624, 562],
[175, 562, 405, 562],
[506, 562, 621, 562],
[94, 558, 98, 566],
[701, 566, 705, 558],
[255, 581, 200, 590],
[548, 581, 537, 583],
[711, 588, 701, 566],
[265, 585, 255, 581],
[624, 562, 600, 590],
[537, 583, 529, 590],
[200, 590, 175, 562],
[600, 590, 598, 592],
[270, 593, 265, 585],
[598, 592, 548, 581],
[98, 566, 82, 601],
[717, 601, 711, 588],
[717, 609, 717, 601],
[82, 601, 82, 609],
[227, 609, 238, 610],
[558, 611, 571, 610],
[714, 613, 717, 609],
[82, 609, 86, 613],
[216, 615, 227, 609],
[571, 610, 581, 616],
[238, 610, 248, 617],
[86, 613, 92, 616],
[707, 616, 714, 613],
[92, 616, 131, 614],
[668, 614, 707, 616],
[549, 618, 558, 611],
[666, 617, 668, 614],
[131, 614, 136, 622],
[663, 622, 666, 617],
[210, 625, 216, 615],
[581, 616, 587, 626],
[248, 617, 253, 628],
[544, 628, 549, 618],
[209, 637, 210, 625],
[587, 626, 588, 638],
[281, 641, 270, 593],
[253, 628, 252, 639],
[544, 640, 544, 628],
[214, 647, 209, 637],
[588, 638, 582, 648],
[252, 639, 247, 648],
[551, 649, 544, 640],
[283, 649, 281, 641],
[291, 653, 283, 649],
[529, 590, 514, 650],
[224, 653, 214, 647],
[236, 654, 247, 648],
[582, 648, 572, 654],
[561, 655, 551, 649],
[236, 654, 224, 653],
[572, 654, 561, 655],
[136, 622, 128, 659],
[514, 650, 478, 664],
[329, 666, 291, 653],
[671, 665, 663, 622],
[128, 659, 129, 666],
[614, 668, 622, 663],
[177, 663, 185, 668],
[666, 670, 671, 665],
[129, 666, 134, 671],
[478, 664, 439, 672],
[622, 663, 659, 671],
[659, 671, 666, 670],
[134, 671, 177, 663],
[368, 673, 329, 666],
[439, 672, 419, 674],
[389, 675, 368, 673],
[419, 674, 389, 675],
[558, 705, 566, 701],
[233, 701, 241, 705],
[185, 668, 183, 707],
[614, 712, 614, 668],
[183, 707, 186, 713],
[198, 717, 233, 701],
[566, 701, 601, 717],
[609, 717, 614, 712],
[186, 713, 191, 718],
[191, 718, 198, 717],
[601, 717, 609, 717],
[495, 730, 504, 728],
[295, 728, 305, 730],
[241, 705, 248, 743],
[552, 743, 558, 705],
[362, 742, 370, 742],
[429, 742, 438, 742],
[549, 749, 552, 743],
[248, 743, 251, 749],
[504, 728, 535, 750],
[542, 752, 549, 749],
[251, 749, 259, 752],
[259, 752, 295, 728],
[535, 750, 542, 752],
[305, 730, 318, 766],
[481, 766, 495, 730],
[438, 742, 464, 770],
[334, 771, 362, 742],
[318, 766, 322, 771],
[476, 772, 481, 766],
[464, 770, 470, 773],
[322, 771, 327, 773],
[327, 773, 334, 771],
[470, 773, 476, 772],
[370, 742, 391, 776],
[404, 779, 429, 742],
[391, 776, 397, 780],
[397, 780, 404, 779],
[556, 238, 529, 222],
[134, 520, 423, 706],
[423, 706, 735, 105],
[735, 105, 415, 586],
[415, 586, 134, 520],
];
data_b.0.with_ref_lines(to_lines(&_l).iter())?;
data_b.0.with_ignore_end_point_intersections(true)?;
Ok(())
}