kaivnd/pypolybool

pypolybool

Boolean operations on polygons (union, intersection, difference, xor) (this library is a port for python of polybooljs

thanks to idormenco/PolyBool.Net, make the work much easier

Resources

• View the demo + animation
• Based somewhat on the F. Martinez (2008) algorithm:
  • Paper
  • [Code](https://github.com/akavel/martinez-src

Example

see tests directory

pypolybool's Issues

Submit project to pypi.

Library modules are best if you can include them, which requires being able to download them, which requires that they be uploaded to a library database like pypi.

Needs License

Preferably MIT since that's what the polybooljs is.

Help need! union a list of polygons cound not get the same result like polybooljs

input polygon list like this, ten rectangle

the union result should be like this, one big polygon, and one small rectangle

It took me a day, trying to find where am I doing wrong.

const PolyBool = require('polybooljs');
let polygons = [
	{
		regions: [
			[
				[730.59859751116562, -390.71295523446059],
				[615.35307569431279, -337.12892286830862],
				[612.40179980847529, -343.47636098503529],
				[727.64732162532812, -397.06039335118726],
				[730.59859751116562, -390.71295523446059],
			],
		],
		inverted: false,
	},
	{
		regions: [
			[
				[560.05206094364189, -424.19915270606077],
				[563.24375903933151, -304.39619864558551],
				[556.24624186080405, -304.20977617855698],
				[553.05454376511443, -424.01273023903224],
				[560.05206094364189, -424.19915270606077],
			],
		],
		inverted: false,
	},
	{
		regions: [
			[
				[629.84175141276103, -302.66920925002108],
				[459.49199784501354, -298.13088222522242],
				[459.30557537798506, -305.12839940374988],
				[629.65532894573255, -309.66672642854854],
				[629.84175141276103, -302.66920925002108],
			],
		],
		inverted: false,
	},
	{
		regions: [
			[
				[577.37742051290581, -427.10631958694233],
				[644.72835427262908, -282.25172087080244],
				[638.38091615590247, -279.300444984965],
				[571.02998239617921, -424.15504370110489],
				[577.37742051290581, -427.10631958694233],
			],
		],
		inverted: false,
	},
	{
		regions: [
			[
				[752.24153075264121, -81.325235022248876],
				[705.41226531283348, -182.04298420231274],
				[711.75970342956009, -184.99426008815018],
				[758.58896886936782, -84.276510908086266],
				[752.24153075264121, -81.325235022248876],
			],
		],
		inverted: false,
	},
	{
		regions: [
			[
				[662.66229477345507, -290.59020407690974],
				[711.75970342955986, -184.99426008815007],
				[705.41226531283326, -182.04298420231262],
				[656.31485665672847, -287.6389281910723],
				[662.66229477345507, -290.59020407690974],
			],
		],
		inverted: false,
	},
	{
		regions: [
			[
				[807.37320363014226, -225.59045224691286],
				[642.17510334963617, -148.78069675528539],
				[639.22382746379867, -155.12813487201205],
				[804.42192774430475, -231.93789036363953],
				[807.37320363014226, -225.59045224691286],
			],
		],
		inverted: false,
	},
	{
		regions: [
			[
				[627.32903578534979, -180.71078353343543],
				[530.68339045364303, -135.774864932349],
				[527.73211456780552, -142.12230304907567],
				[624.37775989951228, -187.0582216501621],
				[627.32903578534979, -180.71078353343543],
			],
		],
		inverted: false,
	},
	{
		regions: [
			[
				[594.77577580897571, -259.02599774532706],
				[678.12452555689913, -79.764196545958214],
				[671.77708744017252, -76.812920660120824],
				[588.4283376922491, -256.07472185948961],
				[594.77577580897571, -259.02599774532706],
			],
		],
		inverted: false,
	},
	{
		regions: [
			[
				[474.88089699084082, -207.14004649461958],
				[755.32451908819985, -337.53383435239914],
				[758.27579497403735, -331.18639623567248],
				[477.83217287667833, -200.79260837789292],
				[474.88089699084082, -207.14004649461958],
			],
		],
		inverted: false,
	},
];

// var buildLog = PolyBool.buildLog(true);

let segments = PolyBool.segments(polygons[0]);
for (var i = 1; i < polygons.length; i++) {
	const seg2 = PolyBool.segments(polygons[i]);
	const comb = PolyBool.combine(segments, seg2);
	segments = PolyBool.selectUnion(comb);
}

const res = PolyBool.polygon(segments);
console.log(res.regions);

this will work, the correct. result like this

[
  [
    [ 703.9366273699145, -185.216703260676 ],
    [ 657.7904945996472, -284.465209132709 ],
    [ 596.2514137518945, -255.85227868696367 ],
    [ 642.397546522162, -156.60377281493075 ]
  ],
  [
    [ 807.3732036301423, -225.59045224691286 ],
    [ 804.4219277443048, -231.93789036363953 ],
    [ 710.2840654866411, -188.16797914651343 ],
    [ 664.1379327163738, -287.4164850185464 ],
    [ 758.2757949740374, -331.1863962356725 ],
    [ 755.3245190881998, -337.53383435239914 ],
    [ 643.2527163297103, -285.42543992916575 ],
    [ 618.5267947526761, -338.6045608112273 ],
    [ 730.5985975111656, -390.7129552344606 ],
    [ 727.6473216253281, -397.06039335118726 ],
    [ 615.5755188668387, -344.95199892795404 ],
    [ 577.3774205129058, -427.10631958694233 ],
    [ 571.0299823961792, -424.1550437011049 ],
    [ 624.327938692978, -309.5247981976626 ],
    [ 563.1505478058173, -307.8949572348493 ],
    [ 560.0520609436419, -424.1991527060608 ],
    [ 553.0545437651144, -424.01273023903224 ],
    [ 556.1530306272898, -307.70853476782077 ],
    [ 459.30557537798506, -305.1283994037499 ],
    [ 459.49199784501354, -298.1308822252224 ],
    [ 627.5439449662335, -302.6079928591803 ],
    [ 636.9052782129837, -282.47416404332836 ],
    [ 474.8808969908408, -207.14004649461958 ],
    [ 477.8321728766783, -200.79260837789292 ],
    [ 589.9039756351679, -252.90100280112628 ],
    [ 621.204040841149, -185.5825837072434 ],
    [ 527.7321145678055, -142.12230304907567 ],
    [ 530.683390453643, -135.774864932349 ],
    [ 624.1553167269865, -179.2351455905167 ],
    [ 671.7770874401725, -76.81292066012082 ],
    [ 678.1245255568991, -79.76419654595821 ],
    [ 645.3488224079994, -150.25633469820406 ],
    [ 706.8879032557522, -178.8692651439494 ],
    [ 752.2415307526412, -81.32523502224888 ],
    [ 758.5889688693678, -84.27651090808627 ],
    [ 713.2353413724788, -181.8205410297868 ]
  ]
]

but when it comes to python, something went wrong, I got this result

pypolybool/polybool/__init__.py

Lines 903 to 912 in 19f3988

	def union(*args):
	if len(args) == 1 and isinstance(args[0], list):
	polygons = args[0]
	seg1 = segments(polygons[0])
	for i in range(1, len(polygons)):
	seg2 = segments(polygons[i])
	comb = combine(seg1, seg2)
	seg1 = selectUnion(comb)
	return polygon(seg1)

pypolybool/tests/union_test.py

Lines 61 to 141 in 19f3988

	def test_case_2():
	regions = [
	[
	(730.59859751116562, -390.71295523446059),
	(615.35307569431279, -337.12892286830862),
	(612.40179980847529, -343.47636098503529),
	(727.64732162532812, -397.06039335118726),
	(730.59859751116562, -390.71295523446059),
	],
	[
	(560.05206094364189, -424.19915270606077),
	(563.24375903933151, -304.39619864558551),
	(556.24624186080405, -304.20977617855698),
	(553.05454376511443, -424.01273023903224),
	(560.05206094364189, -424.19915270606077),
	],
	[
	(629.84175141276103, -302.66920925002108),
	(459.49199784501354, -298.13088222522242),
	(459.30557537798506, -305.12839940374988),
	(629.65532894573255, -309.66672642854854),
	(629.84175141276103, -302.66920925002108),
	],
	[
	(577.37742051290581, -427.10631958694233),
	(644.72835427262908, -282.25172087080244),
	(638.38091615590247, -279.300444984965),
	(571.02998239617921, -424.15504370110489),
	(577.37742051290581, -427.10631958694233),
	],
	[
	(752.24153075264121, -81.325235022248876),
	(705.41226531283348, -182.04298420231274),
	(711.75970342956009, -184.99426008815018),
	(758.58896886936782, -84.276510908086266),
	(752.24153075264121, -81.325235022248876),
	],
	[
	(662.66229477345507, -290.59020407690974),
	(711.75970342955986, -184.99426008815007),
	(705.41226531283326, -182.04298420231262),
	(656.31485665672847, -287.6389281910723),
	(662.66229477345507, -290.59020407690974),
	],
	[
	(807.37320363014226, -225.59045224691286),
	(642.17510334963617, -148.78069675528539),
	(639.22382746379867, -155.12813487201205),
	(804.42192774430475, -231.93789036363953),
	(807.37320363014226, -225.59045224691286),
	],
	[
	(627.32903578534979, -180.71078353343543),
	(530.68339045364303, -135.774864932349),
	(527.73211456780552, -142.12230304907567),
	(624.37775989951228, -187.0582216501621),
	(627.32903578534979, -180.71078353343543),
	],
	[
	(594.77577580897571, -259.02599774532706),
	(678.12452555689913, -79.764196545958214),
	(671.77708744017252, -76.812920660120824),
	(588.4283376922491, -256.07472185948961),
	(594.77577580897571, -259.02599774532706),
	],
	[
	(474.88089699084082, -207.14004649461958),
	(755.32451908819985, -337.53383435239914),
	(758.27579497403735, -331.18639623567248),
	(477.83217287667833, -200.79260837789292),
	(474.88089699084082, -207.14004649461958),
	],
	]
	polygons = [pb.Polygon([region]) for region in regions]
	# polygons.reverse()
	res = pb.union(polygons)
	print()
	print(len(res.regions))

[
  [
    [ 703.9366273699145, -185.216703260676 ],
    [ 657.7904945996472, -284.465209132709 ],
    [ 596.2514137518945, -255.85227868696367 ],
    [ 642.397546522162, -156.60377281493075 ]
  ],
]

missing the big one

Too Broad Exception Raised

You throw an Exception classed Exception which is generally too broad of an exception to catch.

                    raise Exception(
                        "PolyBool: Zero-length segment detected; your epsilon is probably too small or too large"
                    )

class PolyBoolException(Exception):
    pass

Then throw that, so that people can catch the exception without catching all exceptions.